C++ STL标准库概览
400 Words | Read in about 2 Min | View times
STL的核心是三大组件：容器、迭代器和算法。本文通过一个概览图展示一下整个STL三大组件的逻辑关系。
本系列文章将包括以下领域：
本章其他内容请见 《现代C++》
容器
STL容器分为四类：顺序容器、关联容器、无序容器和容器适配器。
| 容器类型 |
描述 |
| array |
固定大小，可随机访问元素 |
| vector |
向后快速插入，支持删除，可随机访问元素 |
| deque |
向前或后快速插入，支持删除，可随机访问元素 |
| forward_list |
单链表，任意位置快速插入和删除 |
| list |
双向链表，任意位置快速插入和删除 |
按键顺序保存元素
| 容器类型 |
描述 |
| set |
快速查找，不重复 |
| map |
一对一映射，键值快速查找，不重复 |
| multiset |
快速查找，可重复 |
| multimap |
一对一映射，键值快速查找，可重复 |
元素无序
| 容器类型 |
描述 |
| unordered_set |
快速查找，不重复 |
| unordered_map |
一对一映射，键值快速查找，不重复 |
| unordered_multiset |
快速查找，可重复 |
| unordered_multimap |
一对一映射，键值快速查找，可重复 |
在顺序容器基础上做条件约束
| 容器类型 |
描述 |
| stack |
后进先出 |
| queue |
先进先出 |
| priority_queue |
堆，优先级最高先出 |
迭代器
| 迭代器类型 |
描述 |
支持的容器类型 |
| 随机访问迭代器 |
可向前或向后跳转任意个元素 |
array, vector, deque |
| 双向访问迭代器 |
在前向迭代器基础上增加向后移动 |
list, set, map, multiset, multimap, unordered_set, unordered_map, unordered_multiset, unordered_multimap |
| 前向访问迭代器 |
输出迭代器+输入迭代器 |
forward_list |
| 输出迭代器 |
将元素写入容器，每次只能前向一个元素 |
forward_list |
| 输入迭代器 |
将元素读出容器，每次只能前向一个元素 |
forward_list |
容器适配器stack、queue、priority_queue不支持迭代器。
| 预定义迭代器 |
++方向 |
读写 |
| iterator |
前 |
读写 |
| const_iterator |
前 |
读 |
| reverse_iterator |
后 |
读写 |
| const_reverse_iterator |
后 |
读 |
| 适用所有迭代器的操作 |
描述 |
| ++p |
前置自增迭代器 |
| p++ |
后置自增迭代器 |
| p = p1 |
迭代器赋值 |
| 适用输入迭代器的操作 |
描述 |
| *p |
引用一个迭代器 |
| p->m |
通过迭代器访问对象成员m |
| p == p1 |
判断迭代器是否相等 |
| p != p1 |
判断迭代器是否不相等 |
| 适用双向迭代器的操作 |
描述 |
| –p |
前置自减迭代器 |
| p– |
后置自减迭代器 |
| 适用随机访问迭代器的操作 |
描述 |
| p += i |
迭代器p前进i个位置 |
| p -= i |
迭代器p后退i个位置 |
| p + i |
迭代器p前进i的位置 |
| p - i |
迭代器p后退i的位置 |
| p - p1 |
两个迭代器的距离 |
| p[i] |
返回与p距离i的元素 |
| p < p1 |
判断迭代器p是否在p1之前 |
| p <= p1 |
判断迭代器p是否在p1之前或相等 |
| p > p1 |
判断迭代器p是否在p1之后 |
| p >= p1 |
判断迭代器p是否在p1之后或相等 |
算法
| 查找算法 |
描述 |
| adjacent_find |
在范围内查找2个连续相等的元素 |
| binary_search |
查找范围内是否包含某个目标元素 |
| count |
范围内查找相等的元素个数 |
| count_if |
范围内查找条件通过的元素个数 |
| equal_range |
范围内查找相等元素的范围迭代器对 |
| find |
范围内查找目标元素的位置 |
| find_end |
在序列A中查找序列B最后一次出现的位置 |
| find_first_of |
在序列A中，查找序列B在序列A中第一次出现任意元素的位置 |
| find_if |
查找匹配条件的首个元素的位置 |
| find_if_not |
查找不匹配条件的首个元素的位置 |
| lower_bound |
在范围内查找不小于目标值的首个元素 |
| upper_bound |
在范围内查找大于目标值的首个元素 |
| search |
在序列A中查找序列B第一次出现的位置 |
| search_n |
在范围内查找第一个符合要求的子序列 |
| 排序和通用算法 |
描述 |
| inplace_merge |
将这2个优需序列合并为1个升序序列，且新序列仍存储在同一个容器 |
| merge |
将2个有序序列合并为1个有序序列，这2个有序序列的排序规则相同 |
| nth_element |
对序列进行排序，并返回第n小元素，默认是升序排序，改为降序排序后是返回第n大元素 |
| partial_sort |
对范围内提取部分数据进行排序 |
| partial_sort_copy |
对范围内提取部分数据进行排序后存入新容器 |
| partition |
根据筛选条件对数据进行分组，第一组符合条件，不关心分组后各元素的具体位置 |
| random_shuffle |
随机打乱序列 |
| reverse |
反转序列 |
| reverse_copy |
反转序列并存入新容器 |
| rotate |
旋转序列，第二个参数称为序列的起始，返回指向原始第一个元素的新位置 |
| rotate_copy |
旋转序列存入新容器，其余与rotate一致 |
| sort |
对序列进行排序，不稳定排序 |
| is_sorted |
判断序列是否已经排序 |
| statble_sort |
对序列进行排序，稳定排序 |
| stable_partion |
根据筛选条件对数据进行分组，第一组符合条件，分组后各元素具体位置保持相对位置不变 |
| 删除和替换算法 |
描述 |
| copy |
复制序列 |
| copy_if |
满足条件的元素复制到新序列 |
| copy_n |
复制n个元素到新序列 |
| copy_backward |
从最后一个元素往前开始复制到新序列，新序列也从后往前存储 |
| iter_swap |
交换迭代器的值 |
| remove |
在范围内移除指定元素 |
| remove_copy |
在范围内将非指定元素的元素复制到新序列 |
| remove_if |
在范围内移除满足条件的元素 |
| remove_copy_if |
在范围内将不满足条件的元素复制到新序列 |
| replace |
在范围内替换和指定元素匹配的元素 |
| replace_copy |
在范围内替换和指定元素匹配的元素，结果存入新序列 |
| replace_if |
在范围内替换满足条件的元素 |
| replace_copy_if |
在范围内替换满足条件的元素，结果存入新序列 |
| swap |
交换两个元素 |
| swap_range |
交换两个序列 |
| unique |
在序列中原地移除重复元素 |
| unique_copy |
在序列中移除重复元素，结果存入新序列 |
| move |
将元素移动到新序列 |
| move_backward |
从最后一个元素往前开始移动到新序列，新序列也从后往前存储 |
| 排列组合算法 |
描述 |
| next_permutation |
生成一个序列的重排列，它是所有可能的字典序中的下一个排列 |
| prev_permutation |
生成一个序列的重排列，它是所有可能的字典序中的上一个排列 |
| 算术算法 |
描述 |
| accumulate |
序列求和 |
| partial_sum |
创建一个新序列，每个新值代表指定范围内该位置前所有元素之和 |
| inner_product |
两个序列内积 |
| adjacent_difference |
创建一个新序列，每个新值代表当前元素与上一个元素的差 |
| 生成和异变算法 |
描述 |
| fill |
用指定值填充序列 |
| fill_n |
以给定起始迭代器及往后n个元素为范围填充序列 |
| for_each |
在范围内迭代操作 |
| generate |
在范围内迭代操作，无法在函数内访问序列元素，只会保存函数为序列每个元素返回的值 |
| generate_n |
以给定起始迭代器及往后n个元素为范围进行与generate一样的操作 |
| transform |
将函数应用到序列的元素上，并将这个函数返回的值保存到另一个序列中 |
| iota |
从给定的起始数值，逐个元素+1赋值给序列 |
| 关系算法 |
描述 |
| equal |
判断是否相等 |
| includes |
判断序列A的所有元素是否都在序列B中 |
| lexicographical_compare |
比较两个序列的字典序 |
| max |
返回两个元素较大值 |
| min |
返回两个元素较小值 |
| max_element |
返回范围中最大值 |
| min_element |
返回范围中最小值 |
| minmax_element |
返回范围中最大最小值迭代器组成的pair |
| mismatch |
并行比较两个序列，返回第一个不匹配的位置 |
| 条件判断算法 |
描述 |
| all_of |
判断范围中是否所有元素满足条件 |
| any_of |
判断范围中是否有任意元素满足条件 |
| none_of |
判断范围中是否没有元素满足条件 |
| 集合算法 |
描述 |
| set_union |
合并两个集合所有元素到新序列，不重复 |
| set_intersection |
两个集合的交集 |
| set_difference |
两个集合的差集，包含s1存在s2不存在的元素 |
| set_symmetric_difference |
两个集合的对称差集，包含s1存在s2不存在，以及s2存在s1不存在的元素 |
| 堆算法 |
描述 |
| make_heap |
生成堆 |
| pop_heap |
将堆顶与末尾交换，重新堆排序 |
| push_heap |
在末尾加入新元素，重新堆排序 |
| sort_heap |
在范围内堆排序 |
| is_heap |
判断序列是否堆 |