**这是本文档旧的修订版!**
STL - 常用算法
概述:
- 算法主要是由头文件
<algorithm><functional><numeric>组成。 <algorithm>是所有STL头文件中最大的一个,范围涉及到比较、交换、查找、遍历操作、复制、修改等等。<numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数。<functional>定义了一些模板类,用以声明函数对象。
常用遍历算法
学习目标:
- 掌握常用的遍历算法
算法简介:
for_each遍历容器 *transform搬运容器到另一个容器中
for_each
功能描述:
- 实现遍历容器
函数原型:
for_each(iterator beg, iterator end, _func); // 遍历算法 遍历容器元素 // beg 开始迭代器 // end 结束迭代器 // _func 函数或者函数对象
transform
功能描述:
- 搬运容器到另一个容器中
函数原型:
transform(iterator beg1, iterator end1, iterator beg2, _func); // beg1 源容器开始迭代器 // end1 源容器结束迭代器 // beg2 目标容器开始迭代器 // _func 函数或者函数对象
常用查找算法
学习目标:
- 掌握常用的查找算法
算法简介:
find查找元素 *findif求两个容器的并集按条件查找元素 *setunionadjacentfind求两个容器的交集 *查找相邻重复元素 *sortbinarysearch按条件统计元素个数 ==== 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> ===== 常用排序算法 ===== 学习目标: * 掌握常用的排序算法 算法简介: *二分查找法 *countifcount统计元素个数 *对容器内元素进行排序 *mergerandom_shuffle洗牌 指定范围内的元素随机调整次序 *容器元素合并,并存储到另一容器中 *replacereverse反转指定范围的元素 ==== 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容器内指定范围的元素拷贝到另一容器中 *将容器内指定范围的旧元素修改为新元素 *swapreplace_if容器内指定范围满足条件的元素替换为新元素 *互换两个容器的元素 ==== 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计算容器元素累计总和 *setintersectionfill向容器中添加元素 ==== 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_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
功能描述: * 求两个集合的并集
函数原型:
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的并集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
总结: * 求并集的两个集合必须的有序序列 * 目标容器开辟空间需要两个容器相加 * set_union返回值既是并集中最后一个元素的位置
set_difference
功能描述: * 求两个集合的差集
函数原型:
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // 求两个集合的差集 // 注意:两个集合必须是有序序列 // beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
总结: * 求差集的两个集合必须的有序序列 * 目标容器开辟空间需要从两个容器取较大值 * set_difference返回值既是差集中最后一个元素的位置