STL 算法组件
- STL算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为
[first, last)，其中last指代要查询或修改的最后元素的后一个元素。 -
include
不修改序列的操作
- 调用函数之后，不会影响序列中本来元素的值
- all_of 所有都满足条件时返回true
- any_of 只要有一个满足条件即返回true
- none_of 当所有都不满足条件时返回true
- for_each 遍历区间元素，用每一个元素都当作实参去调用一元谓词
- count 返回指定元素的个数
- count_if 返回满足条件的元素个数
- mismatch 查找首不"相等"的 pair<IT,IT>
- find 查找指定元素 找不到 尾迭代器 last
- 元素比较时默认是用 operator ==
- find_if 查找满足某个条件(一元谓词)的元素
- find_if_not 查找不满足条件的元素
- find_end
[first, last)中搜索序列[s_first, s_last)的最后一次出现- 默认是operator ==
- 二元谓词比较
- find_first_of 在范围
[first, last)中搜索范围[s_first, s_last)中的任何元素 - adjacent_find 在范围
[first, last)中搜索二个相继的相等元素。- 用
operator==比较元素。 - 用给定的二元谓词
p比较元素
- 用
- search 搜索范围
[first, last - (s_last - s_first))中元素子序列[s_first, s_last)的首次出现。 - search_n 在范围
[first, last)中搜索 count 个等同元素的序列，每个都等于给定的值 value 。
修改序列操作
- 需要注意的事项是
- 被修改的迭代范围要有元素
- copy 将某一范围的元素复制到一个新的位置 把新位置原来的元素覆盖掉
- copy_if 将某一范围内满足条件的元素复制到一个新的位置
- copy_n 将一定数目的元素复制到一个新的位置
- copy_backward 复制来自
[first, last)所定义范围的元素，到终于d_last的范围。以逆序复制元素（首先复制末元素），但保持其相对顺序 - move 将某一范围的元素移动到一个新的位置 现象复制
- 此操作后被移动范围中的元素将仍然含有适合类型的合法值，但不必与移动前的值相同。
- move_backward
- fill 填充指定元素 将一个给定值复制赋值给一个范围内的每个元素
- fill_n 将一个给定值复制赋值给一个范围内的 N 个元素
- transform 将一个函数应用于某一范围的各个元素，并在目标范围存储结果
- generate 将相继的函数调用结果赋值给一个范围中的每个元素
- generate_n 将相继的函数调用结果赋值给一个范围中的 N 个元素
- remove 移除满足特定的元素 移除实际上是用后面的元素覆盖前面的元素 并不会真正把元素从容器中删除，不会使得容器元素个数减少
- remove_if 移除满足特定判别标准的元素
- 容器中的erase成员函数真正删除了元素 使用元素个数减少
- remove全局函数移除是用后面的元素覆盖
- remove_copy 复制一个范围的元素，忽略满足特定判别标准的元素
- remove_copy_if
- replace 将所有满足特定判别标准的值替换为另一个值
- replace_if 将所有满足条件的值替换为另一个值
- replace_copy 复制一个范围内的元素，并将满足特定判别标准的元素替换为另一个值
- replace_copy_if 复制一个范围内的元素，并将满足特定判别标准的元素替换为另一个值
- swap 交换两个对象的值
- 注意，在operator=运算符重载函数中不能用swap来交换本类类型的对象
- 因为在swap中一定是调用类类型成员的operator=
- swap_range 交换两个范围的元素
- iter_swap 交换两个迭代器所指向的元素
- reverse 转范围中的元素顺序 迭代器要求必须是双向迭代
- reverse_copy
- rotate 旋转范围中的元素顺序 左旋转
- rotate_copy
- random_shuffle 随机重排范围中的元素 打乱元素的顺序
- sample 从一个序列中随机选择 n 个元素
- unique 移除(用后面元素覆盖)范围内的连续重复(连续的)元素
- unique_copy
划分操作
- is_partitioned 若范围
[first, last)中的所有满足p的元素都出现在所有不满足的元素前则返回 true 。若[first, last)为空亦返回 true - partition 将范围中的元素分为两组
- partition_copy
- stable_partition 将元素分为两组，同时保留其相对顺序
- partition_point 定位已划分范围的划分点 找到不满足条件的迭代器
排序
- is_sorted 检查范围是否已按指定规则排列
- is_sorted_until 找出已排序的最大范围 返回最后一个已排序元素的下一个迭代器
- sort 按照指定规则进行排序 默认是用operator<进行比较
- partial_sort 部分排序 [first,last)区间 [first,temp)排序 找top
- partial_sort_copy
- stable_sort 稳定排序
- nth_element 将给定的范围部分排序，确保其按给定元素划分
- partial_sort 前面有序
- nth_element 后面有序
二分搜索
- 迭代范围元素有序 元素默认要支持 operator < 或者提供 Compare
- lower_bound 返回指向第一个不"小于"给定值的元素的迭代器
- upper_bound 返回指向第一个"大于"给定值的元素的迭代器
- binary_search 二分查找
- equal_range 查找相等元素的范围
- lower_bound/upper_bound/equal_range 是关联容器中有的
其它有关排序的操作
-
merge 合并 两个容器合并到第三个容器 只是传递的是迭代器
- 可以无序，但无序合并依然无序
-
inplace_merge 内部合并 一个容器
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ); void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );
集合操作（在已排序范围上）
- 排序规则
- includes 若一个序列是另一个的子列则返回 true
- set_difference 计算两个集合的差集
- set_intersection 交集
- set_symmetric_difference 对称差
- set_union 并集
堆操作
- 大根堆 /小根堆
- 物理结构上：顺序存储 逻辑结构上：完全二叉树
- is_heap 检查给定范围是否为一个最"大"堆
- is_heap_until 找出堆的最大范围
- make_heap 创建堆
- push_heap 往堆中压入一个元素保持堆的特性 要保证要空间存储该元素
- pop_heap 从最大堆中移除最"大"元素 用后面的元素逐一往前覆盖
- sort_heap 堆排序
最大值最小值
- max
- min
- max_element
- min_element
- minmax
- minmax_element
比较
- equal 确定两个元素集合是否是相同的
排列操作
- is_permutation 是否是一个排列
- next_permutation 产生某个元素范围的按字典顺序的下一个较大的排列
- prev_permutation 产生某个元素范围的按字典顺序的下一个较小的排列
数值运算
-
include
- itoa 用从起始值开始连续递增的值填充一个范围
- acumulate 对一个范围内的元素求和
- inner_product 对应位置相乘累加和
- adjacent_difference 计算范围内各相邻元素之间的差
- partial_sum 计算范围内元素的部分和
未初始化内存上的操作
- uninitialized_copy 将范围内的对象复制到未初始化的内存区域
- uninitialized_copy_n 将指定数量的对象复制到未初始化的内存区域
- uninitialized_fill 复制一个对象到以范围定义的未初始化内存区域
- uninitialized_fill_n 复制一个对象到以起点和计数定义的未初始化内存区域