====== STL - 常用算法 ======

**概述：**
  * 算法主要是由头文件 ''<algorithm>'' ''<functional>'' ''<numeric>'' 组成。
  * ''<algorithm>'' 是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等。
  * ''<numeric>'' 体积很小，只包括几个在序列上面进行简单数学运算的模板函数。
  * ''<functional>'' 定义了一些模板类,用以声明函数对象。

=====  常用遍历算法 =====

**学习目标：**
  * 掌握常用的遍历算法

**算法简介：**
  * ''for_each'' // 遍历容器
  * ''transform'' // 搬运容器到另一个容器中

==== for_each ====

**功能描述：**
  * 实现遍历容器

**函数原型：**
<code cpp>
for_each(iterator beg, iterator end, _func);
// 遍历算法 遍历容器元素
// beg 开始迭代器
// end 结束迭代器
// _func 函数或者函数对象
</code>

==== transform ====

**功能描述：**
  * 搬运容器到另一个容器中

**函数原型：**
<code cpp>
transform(iterator beg1, iterator end1, iterator beg2, _func);
// beg1 源容器开始迭代器
// end1 源容器结束迭代器
// beg2 目标容器开始迭代器
// _func 函数或者函数对象
</code>

===== 常用查找算法 =====

**学习目标：**
  * 掌握常用的查找算法

**算法简介：**
  * ''find'' // 查找元素
  * ''find_if'' // 按条件查找元素
  * ''adjacent_find'' // 查找相邻重复元素
  * ''binary_search'' // 二分查找法
  * ''count'' // 统计元素个数
  * ''count_if'' // 按条件统计元素个数

====  find ====

**功能描述：**
  * 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

**函数原型：**
<code cpp>
find(iterator beg, iterator end, value);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
</code>

==== find_if ====

**功能描述：**
  * 按条件查找元素

**函数原型：**
<code cpp>
find_if(iterator beg, iterator end, _Pred);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数或者谓词（返回bool类型的仿函数）
</code>

==== adjacent_find ====

**功能描述：**
  * 查找相邻重复元素

**函数原型：**
<code cpp>
adjacent_find(iterator beg, iterator end);
// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
// beg 开始迭代器
// end 结束迭代器
</code>

**总结：** 面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法

====  binary_search ====

**功能描述：**
  * 查找指定元素是否存在

**函数原型：**
<code cpp>
bool binary_search(iterator beg, iterator end, value);
// 查找指定的元素，查到 返回true 否则false
// 注意: 在无序序列中不可用
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
</code>

==== count ====

**功能描述：**
  * 统计元素个数

**函数原型：**
<code cpp>
count(iterator beg, iterator end, value);
// 统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// value 统计的元素
</code>

==== count_if ====

**功能描述：**
  * 按条件统计元素个数

**函数原型：**
<code cpp>
count_if(iterator beg, iterator end, _Pred);
// 按条件统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词
</code>

===== 常用排序算法 =====

**学习目标：**
  * 掌握常用的排序算法

**算法简介：**
  * ''sort'' // 对容器内元素进行排序
  * ''random_shuffle'' // 洗牌 指定范围内的元素随机调整次序
  * ''merge'' // 容器元素合并，并存储到另一容器中
  * ''reverse'' // 反转指定范围的元素

==== sort ====

**功能描述：**
  * 对容器内元素进行排序

**函数原型：**
<code cpp>
sort(iterator beg, iterator end, _Pred);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词
</code>

**总结：** sort属于开发中最常用的算法之一，需熟练掌握

==== random_shuffle ====

**功能描述：**
  * 洗牌 指定范围内的元素随机调整次序

**函数原型：**
<code cpp>
random_shuffle(iterator beg, iterator end);
// 指定范围内的元素随机调整次序
// beg 开始迭代器
// end 结束迭代器
</code>

====  merge ====

**功能描述：**
  * 两个容器元素合并，并存储到另一容器中

**函数原型：**
<code cpp>
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 容器元素合并，并存储到另一容器中
// 注意: 两个容器必须是有序的
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
</code>

====  reverse ====

**功能描述：**
  * 将容器内元素进行反转

**函数原型：**
<code cpp>
reverse(iterator beg, iterator end);
// 反转指定范围的元素
// beg 开始迭代器
// end 结束迭代器
</code>

===== 常用拷贝和替换算法 =====

**学习目标：**
  * 掌握常用的拷贝和替换算法

**算法简介：**
  * ''copy'' // 容器内指定范围的元素拷贝到另一容器中
  * ''replace'' // 将容器内指定范围的旧元素修改为新元素
  * ''replace_if'' // 容器内指定范围满足条件的元素替换为新元素
  * ''swap'' // 互换两个容器的元素

====  copy ====

**功能描述：**
  * 容器内指定范围的元素拷贝到另一容器中

**函数原型：**
<code cpp>
copy(iterator beg, iterator end, iterator dest);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// dest 目标起始迭代器
</code>

====  replace ====

**功能描述：**
  * 将容器内指定范围的旧元素修改为新元素

**函数原型：**
<code cpp>
replace(iterator beg, iterator end, oldvalue, newvalue);
// 将区间内旧元素 替换成 新元素
// beg 开始迭代器
// end 结束迭代器
// oldvalue 旧元素
// newvalue 新元素
</code>

====  replace_if ====

**功能描述：**
  * 将区间内满足条件的元素，替换成指定元素

**函数原型：**
<code cpp>
replace_if(iterator beg, iterator end, _pred, newvalue);
// 按条件替换元素，满足条件的替换成指定元素
// beg 开始迭代器
// end 结束迭代器
// _pred 谓词
// newvalue 替换的新元素
</code>

==== swap ====

**功能描述：**
  * 互换两个容器的元素

**函数原型：**
<code cpp>
swap(container c1, container c2);
// 互换两个容器的元素
// c1容器1
// c2容器2
</code>

===== 常用算术生成算法 =====

**学习目标：**
  * 掌握常用的算术生成算法

**注意：**
  * 算术生成算法属于小型算法，使用时包含的头文件为 ''#include <numeric>''

**算法简介：**
  * ''accumulate'' // 计算容器元素累计总和
  * ''fill'' // 向容器中添加元素

==== accumulate ====

**功能描述：**
  * 计算区间内 容器元素累计总和

**函数原型：**
<code cpp>
accumulate(iterator beg, iterator end, value);
// 计算容器元素累计总和
// beg 开始迭代器
// end 结束迭代器
// value 起始值
</code>

====  fill ====

**功能描述：**
  * 向容器中填充指定的元素

**函数原型：**
<code cpp>
fill(iterator beg, iterator end, value);
// 向容器中填充元素
// beg 开始迭代器
// end 结束迭代器
// value 填充的值
</code>

===== 常用集合算法 =====

**学习目标：**
  * 掌握常用的集合算法

**算法简介：**
  * ''set_intersection'' 求两个容器的交集
  * ''set_union'' 求两个容器的并集
  * ''set_difference''  求两个容器的差集

==== set_intersection ====

**功能描述：**
  * 求两个容器的交集

**函数原型：**
<code cpp>
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 求两个集合的交集
// 注意:两个集合必须是有序序列
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
</code>

**总结：**
  * 求交集的两个集合必须的有序序列
  * 目标容器开辟空间需要从**两个容器中取小值**
  * set_intersection返回值既是交集中最后一个元素的位置

====  set_union ====

**功能描述：**
  * 求两个集合的并集

**函数原型：**
<code cpp>
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 求两个集合的并集
// 注意:两个集合必须是有序序列
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
</code>

**总结：**
  * 求并集的两个集合必须的有序序列
  * 目标容器开辟空间需要**两个容器相加**
  * set_union返回值既是并集中最后一个元素的位置

==== set_difference ====

**功能描述：**
  * 求两个集合的差集

**函数原型：**
<code cpp>
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 求两个集合的差集
// 注意:两个集合必须是有序序列
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
</code>

**总结：**
  * 求差集的两个集合必须的有序序列
  * 目标容器开辟空间需要从**两个容器取较大值**
  * set_difference返回值既是差集中最后一个元素的位置