STL 容器、迭代器、算法归纳整理

2023-05-16

注：文章由博主同步发布于：STL 容器、迭代器、算法小结

标准模板库

内容主要源自C++ Standard Library 与 C++ Primer。

STL是C++标准库的核心，是一个泛型（generic）程序库，内部的所有组件都由模板构成，所以其元素可以是任意类型。

STL组件（Component）：

容器
迭代器
算法

1 容器（Container）

用来管理各种类对象的集合。容器分为三类：

序列式容器
关联式容器
无序容器

1.1 序列式容器（Sequence container）

序列式容器是一种有序（ordered）集合，其内每个元素都有确切位置，该位置取决于插入时间和地点，与元素的值无关。STL提供了5个定义好的序列式容器：

vector：可变大小数组。支持随机访问。在尾部插入、删除速度快，在尾部之外的位置插入、删除元素慢。
deque：双端队列。支持快速随机访问。在首、尾插入、删除速度快，在中间位置插入元素费时。
list：双向链表。支持双向顺序访问。在任何位置插入、删除元素都很快。
forword_list：单向链表。支持单向顺序访问。在任何位置插入、删除元素都很快。
array：固定大小数组。支持快速随机访问。不能添加、删除元素。

Tips：通常，使用vector是最佳选择。

heap 由 vector 实现
priority_queue 由 heap 实现
stack 和 queue 由 deque 实现

1.1.1 共有操作（重要）

初始化
C c;	默认构造函数
C c1 (c2)	c1 初始化为 c2 的拷贝。c1 和 c2 的类型（包括容器类型和元素类型）必须相同。对于 array 类型，两者大小也要相同
C c {a, b, c ...} C c ({a, b, c ...}) C c = {a, b, c ...}	c 初始化为初值列中元素的拷贝。列表中元素类型必须与 C 元素类型等同。对于 array 类型，初值列元素数应<= array 大小
C c (b, e)	c 初始化为迭代器 b 和 e 范围内的元素的拷贝（不适用于 array 类型）。范围内元素类型需要等同于 C 中元素类型
只有顺序容器（不包括 array）的构造函数才能接受大小参数
C seq (n)	seq 包含 n 个元素，这些元素进行了值初始化；此构造函数是 explicit 的
C seq (n, t)	seq 包含 n 个元素，值为 t
赋值和 swap
c1 = c2	将 c1 的所有元素替换为 c2 中元素的拷贝。c1 和 c2 的类型（包括容器类型和元素类型）必须相同
c = { a, b, c ...}	将 c1中元素替换为初始化列表中元素的拷贝（不适用于 array）
c1.swap (c2) swap (c1, c2)	交换c1 与 c2 中存放的元素。c1 和 c2 的类型必须相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快
assign 操作不适用于关联容器和 array
c.assign (b, e)	重新设置 c 的元素：将迭代器 b 和 e 标记的范围内所有的元素复制到 c 中。b 和 e 必须不是指向 c 中元素的迭代器
c.assign (n, t)	将容器 c 重新设置为存储 n 个值为 t 的元素
c.assign (i_l)	将容器 c 重新设置为存储初始化列表中 i_l 的元素
begin () 和 end () 成员
c.begin ()	返回一个迭代器，它指向容器 c 的第一个元素
c.end ()	返回一个迭代器，它指向容器 c 的最后一个元素的下一位置
c.cbegin ()	返回一个常量迭代器，它指向容器 c 的第一个元素
c.cend ()	返回一个常量迭代器，它指向容器 c 的最后一个元素的下一位置
c.rbegin ()	返回一个逆序迭代器，它指向容器 c 的最后一个元素
c.rend ()	返回一个逆序迭代器，它指向容器 c 的第一个元素前面的位置
c.crbegin ()	返回一个常量逆序迭代器，它指向容器 c 的最后一个元素
c.crend ()	返回一个常量逆序迭代器，它指向容器 c 的第一个元素前面的位置
array 不能增删元素，故以下都不支持 forward_list 有自己的 insert、emplace forward_list 不支持push_back、emplace_back vector 和 string 不支持push_front、emplace_front
c.push_back (t) c.emplace_back (args)	在容器 c 的尾部添加值为 t 的元素（值拷贝）。返回 void 类型在容器 c 的尾部构造值为 args 的元素（调用 c 类型的构造函数，构造函数参数为args）。返回 void 类型
c.push_front (t) c.emplace_front (args)	在容器 c 的前端添加值为 t 的元素（值拷贝）。返回 void 类型在容器 c 的首部构造值为 args 的元素（调用 c 类型的构造函数，构造函数参数为args）。返回 void 类型
c.emplace (p, args)	在容器 c 的首部构造值为 args 的元素（调用 c 类型的构造函数，构造函数参数为args）。返回新元素迭代器
c.insert (p, t)	在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器
c.insert (p, n, t)	在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素。返回新添加的第一个元素的迭代器，若 n 为0返回 p
c.insert (p, b, e)	在迭代器 p 所指向的元素前面插入由迭代器 b 和 e 标记的范围内的元素。返回新添加的第一个元素的迭代器，若范围为空，返回 p
c.insert (p, i_l)	i_l是由花括号包围的元素值列表。将列表中的元素插入到迭代器 p 之前。返回新添加的第一个元素的迭代器，若列表为空，返回 p
获取、调整容器大小
c.size ()	返回容器 c 中的元素个数。返回类型为 c::size_type
c.max_size ()	返回容器 c 可容纳的最多元素个数，返回类型为 c::size_type
c.empty ()	返回标记容器大小是否为 0 的布尔值
c.resize (n)	调整容器 c 的长度大小，使其能容纳 n 个元素，如果 n < c.size()，则删除多出来的元素；否则，添加采用值初始化的新元素
c.resize (n, t)	调整容器 c 的长度大小，使其能容纳 n 个元素。所有新添加的元素值都为 t
at 和下标操作只适用于string、vector、deque 和 array back 不适用于 forward_list
c.back ()	返回容器 c 的最后一个元素的引用。如果 c 为空，则该操作未定义
c.front ()	返回容器 c 的第一个元素的引用。如果 c 为空，则该操作未定义
c [n]	返回下标为 n 的元素的引用。如果 n <0 或 n >= c.size()，则该操作未定义
c.at (n)	返回下标为 n 的元素的引用。如果下标越界，则该操作未定义
不适用于 array，因为这些操作会改变容器大小
c.erase (p)	删除迭代器 p 所指向的元素。返回一个迭代器，它指向被删除元素后面的元素。如果 p 指向尾元素，则返回尾后迭代器（end）。如果 p 本身是尾后迭代器，则该函数未定义
c.erase(b,e)	删除迭代器 b 和 e 所标记的范围内所有的元素。返回一个迭代器，它指向被删除元素段后面的元素。如果 e 本身就是尾后迭代器，则返回尾后迭代器
c.clear()	删除容器 c 内的所有元素。返回 void
c.pop_back()	删除容器 c 的最后一个元素。返回 void。如果 c 为空容器，则该函数未定义
c.pop_front()	删除容器 c 的第一个元素。返回 void。如果 c 为空容器，则该函数未定义

1.2 关联式容器（Asociative container）

关联式容器是一种已排序（sorted）集合，元素位置取决于元素的值，和插入次序无关。STL提供了4种关联式容器（均由 RB-tree 实现）：

set
multiset
map
multimap

1.2.1 共有操作（重要）

关联容器额外的类型别名
key_type	此容器类型的关键字类型
mapped_type	每个关键字关联的类型。只适用于 map 系列
value_type	对于 set 与 key_type 相同；对于 map，为 pair<const key_type, mapped_type>
添加元素（v 是 value_type 类型的对象，args 用来构造一个元素）（仅指出与顺序容器操作不同的地方）
c.insert (v) c.emplace (args)	同。返回一个 pair，包含一个迭代器，指向具有该关键字的元素，以及一个 bool 值指示插入成功与否
c.insert (b, e) c.insert (i_l)	同。返回 void
c.insert (p, v) c.emplace (p, args)	迭代器 p 仅仅作为提示，指出从哪里开始搜索新元素应该储存的位置。实际上以STL为准。返回一个迭代器，指向具有给定关键字的元素
下标操作（仅对于 map 系列）
c [k]	返回关键字为 k 的元素。如果 k 不在 c 中，添加一个关键字为 k 的元素，并对其进行初始化
c.at (k)	返回关键字为 k 的元素，带参数检查。若 k 不在 c 中，抛出一个 out_of_range 异常
访问元素（非常适合无序容器）
c.find (k)	返回一个迭代器，指向第一个关键字为 k 的元素，若 k 不在 c 中，则返回尾后迭代器
c.count (k)	返回关键字为 k 的元素的数量（非常适合在 multixxx 中寻找元素）
c.lower_bound (k)	返回一个迭代器，指向第一个关键字不小于 k 的元素（非常适合在 multixxx 中寻找元素）
c.upper_bound (k)	返回一个迭代器，指向第一个关键字大于 k 的元素（非常适合在 multixxx 中寻找元素）
c.equal_range (k)	返回一个迭代器 pair，表示关键字等于 k 的元素的范围。若 k 不存在，pair 两个成员均为 c.end() （非常适合在 multixxx 中寻找元素）
删除元素
c.erase (k)	删除键值为 k 的元素。返回一个size_type，它等于被删除元素的个数
c.erase (b, e)	删除迭代器 b 和 e 所标记的范围内所有的元素。返回 void

1.3 无序容器（Unordered container）

无序容器是一种无序集合（unordered collection），其内每个元素的位置无关紧要，唯一重要的是某特定元素是否位于此集合内。STL包含4个无序容器（均由 hashtable（由 vector + link_list 实现）实现）：

unordered_set
unordered_multiset
unordered_map
unordered_multimap

1.3.1 共用操作

见上表

2 迭代器（Iterator）

用来在一个对象集合内遍历元素。被定义在头文件 iterator 中。

迭代器分为 5 种：

Input iterator
Output iterator
Forward iterator
Bidirectional iterator
Random-access iterator

重要
迭代器种类	能力	提供者（提供给谁用）
Input 迭代器	向前读取一次	Istream
Output 迭代器	向前写入	Ostream、inserter
Forward 迭代器	向前读取	forward_list、unordered_xxx（无序容器）
Bidirectional 迭代器	向前和向后读取	list、set、multiset、map、multimap
Random-access 迭代器	以随机访问方式读取	array、vector、deque、string、C-Style array（pointer）

每个迭代器读写元素的方式不一样，知悉每种迭代器的用法，以及 STL 容器使用哪些迭代器，有助于更好的使用 STL。

例如：

list<int> ls{1,2,3,4,5,6};
list<int>::iterator it = ls.begin();
//cout << *(it+1) << endl; 错误，list 使用双向迭代器，不提供算数操作
cout << *(++it) <<endl; // 正确

如果知道 list 容器所使用的的迭代器类型，可以帮助我们避免刻板印象造成的错误。

2.1 用法汇总

表达式	效果
为方便总结绘制成一张表，下面的迭代器同样提供上面迭代器的操作
*iter = val	将 val 写入迭代器所指位置
++iter	向前步进（返回新位置）（速度快）
iter++	向前步进（返回旧位置）（速度慢）
TYPE(iter)	赋值迭代器（copy 构造函数）
input 迭代器
*iter	*读取元素（此处不继承 iter = val 操作）**
iter1 == iter2	判断两个迭代器是否相等
iter1 != iter2	判断两个迭代器是否不等
forward （向前）迭代器
TYPE()	创建迭代器（default 构造函数）
iter = iter2	对迭代器赋值
bidirectional （双向）迭代器
--iter	步退（返回新位置）
iter--	步退（返回旧位置）
random-access （随机访问）迭代器
iter[n]	访问索引位置为 n 的元素
iter+=n	前进 n 个元素，若 n 为负数改为回退
iter-=n	回退 n 个元素，若 n 为负数改为前进
iter+n	返回 iter 之后的第 n 个元素（并非访问）
n+iter	返回 iter 之后的第 n 个元素（并非访问）
iter-n	返回 iter 之前的第 n 个元素（并非访问）
iter1-iter2	返回 iter1 与 iter2 之间的距离
iter1<iter2	判断 iter1 是否在 iter2 之后
iter1>iter2	判断 iter1 是否在 iter2 之前
iter1<=iter2	判断 iter1 是否不在 iter2 之后
iter1>=iter2	判断 iter1 是否不在 iter2 之前

2.2 迭代器辅助函数

advance (pos, n)：令 pos 迭代器前进（或后退，若 n 为负数） n 个元素，不检查是否超过 begin() 或者 end()，需要调用者自行确定。
next (p) / next (p, n)：令迭代器前进1（或 n）个位置，若 n 取负数，改为后退 n 个位置，不检查是否超过 begin() 或者 end()，需要调用者自行确定。
prev (p) / prev (p, n)：令迭代器后退1（或 n）个位置，若 n 取负数，改为前进 n 个位置，不检查是否超过 begin() 或者 end()，需要调用者自行确定。
distance (pos1, pos2)：返回 pos1 与 pos2 之间的距离，两个迭代器必须指向同一容器，调用者要确保 pos1 在 pos2 之前或处于同一位置。

3 算法（Algorithm）

用来处理集合内的元素。

定义于头文件 algorithm；某些 STL 算法用于数值处理，因此被定义于头文件 numeric；使用 STL 算法时，经常需要用到 function object 以及 function adapter，它们定义在 funtional 中。

3.1 分类

STL 设计者为算法命名时，引入了两个特殊后缀：

_if：要求传递函数或者 funtion object
_copy：元素不只被操作，还被复制到某区间。

算法具体分为 7 大类：

Nonmodifying algorithms（非更易型算法）
Modifying algorithms（更易型算法）
Removing algorithms（移除型算法）
Mutating algorithms（变序型算法）
Sorting algorithms（排序算法）
Sorted range algorithms（已排序区间算法）
Numeric algorithms（数值算法）

3.1.1 非更易型算法

非更易型算法不改动元素次序，也不改变元素值（使用者不应该让自定义的函数改变元素的值或者次序）。它通过 input 迭代器和 forward 迭代器工作，因此可以用于所有容器上。

名称（InputIterator = II，ForwardIterator = FI，RI = 随访迭代器）

效果

复杂度

for_each (II beg, II end, UnaryProc op)

对 [beg, end) 每个元素执行 op 操作

O(n)

count (II beg, II end, const T& value)

count_if (II beg, II end, UnaryProc op)

返回 [beg, end) 元素值 == value 个数

返回 [beg, end) op 返回 true 个数

O(n)

FI min_element (FI beg, FI end)

FI min_element (FI beg, FI end, CompFunc op)

FI max_element (FI beg, FI end)

FI max_element (FI beg, FI end, CompFunc op)

minmax_element (FI beg, FI end)

minmax_element (FI beg, FI end, CompFunc op)

返回 [beg, end) 元素最小值位置

返回 [beg, end) op 排序规则下的最小值位置

返回 [beg, end) 元素最大值位置

返回 [beg, end) op 排序规则下的最大值位置

返回 [beg, end) 元素最小值最大值位置组成的 pair

返回 [beg, end) op 排序规则下元素最小、大值位置组成的 pair

O(n)

II find (II beg, II end, const T& value)

II find_if (II beg, II end, UnaryPredicate op)

II find_if_not (II beg, II end, UnaryPredicate op)

search_n (FI beg, FI end, Size count, const T& val)

search_n (FI beg, FI end, Size count, const T& val, BinaPred op)

返回 [beg, end) 元素值 == value 的元素位置

返回 [beg, end) op 返回 true 的元素位置

返回 [beg, end) 第一个元素使 op 返回 false 的元素位置

返回 [beg, end) 连续 count 个元素值 == value 的第一个元素的位置

返回 [beg, end) 连续 count 个元素值造成 op 返回 true 的第一个元素的位置

O(n)

adjacent_find (FI beg, FI end)

adjacent_find (FI beg, FI end, BinaPred op)

返回 [beg, end) 内第一对“连续两个相等元素”中的第一个元素的位置

返回 [beg, end) 内第一对“连续两个元素造成 op 返回 true”的第一个元素的位置

O(n)

mismatch (II beg, II end, II cmpBeg)

mismatch (II beg, II end, II cmpBeg, BinaPred op)

返回 [beg, end) 和 [cmpBeg) 内第一对“两两相异”的元素 pair

返回 [beg, end) 和 [cmpBeg) 内第一对“造成 op 返回 false”的元素 pair

O(n)

find_first_of (FI beg, FI end, FI searchBeg, FI searchEnd)

find_first_of (FI beg, FI end, FI searchBeg, FI searchEnd, BinaPred op)

返回第一个同时出现于 [beg, end) 和 [searchBeg, searchEnd) 的元素位置

返回第一个位于 [beg, end) 的元素其与 [searchBeg, searchEnd) 中每一个元素 op 都返回 true

O(n)

search (FI beg, FI end, FI searchBeg, FI searchEnd)

search (FI beg, FI end, FI searchBeg, FI searchEnd, BinaPred op)

find_end (FI beg, FI end, FI searchBeg, FI searchEnd)

find_end (FI beg, FI end, FI searchBeg, FI searchEnd, BinaPred op)

返回 [beg, end) 内和 [searchBeg, searchEnd) 完全吻合的第一个子区间内第一个元素位置

返回 [beg, end) 内和 [searchBeg, searchEnd) 造成 op 返回 true 第一个子区间内第一个元素位置

返回 [beg, end) 内和 [searchBeg, searchEnd) 完全吻合的最后一个子区间内第一个元素位置

返回 [beg, end) 内和 [searchBeg, searchEnd) 造成 op 返回 true 最后一个子区间内第一个元素位置

O(n)

equal (II beg, II end, II cmpBeg)

equal (II beg, II end, II cmpBeg, BinaPred op)

[beg, end) 内元素是否和以 cmpBeg 开头的区间内的元素相同（cmpBeg区间要足够）

[beg, end) 内元素是否和以 cmpBeg 开头的区间内的对应元素使 op 返回 true（要求同上）

O(n)

is_permutation (FI beg, FI end, FI beg2)

is_permutation (FI beg, FI end, FI beg2, CompFunc op)

顺序无所谓的情况下 [beg, end) 内元素是否和以 cmpBeg 开头的区间内的元素相同

顺序无所谓的情况下 [beg, end) 内元素是否和以 cmpBeg 开头的区间内的元素令 op 都返回 true

O(n^2)

lexicographcal_compare (II beg, II end, II beg2, II beg2)

lexicographcal_compare (II beg, II end, II beg2, II beg2, CompFunc op)

判断 [beg, end) 内元素是否都小于 [beg2, end2) 内元素（不满足则立即返回 false，不继续比较）

判断 [beg, end) 和 [beg2, end2) 内元素是否都使 op 返回 true（同上）

O(n)

is_sorted (FI beg, FI end, FI beg2)

is_sorted (FI beg, FI end, FI beg2, CompFunc op)

is_sorted_until (FI beg, FI end, FI beg2)

is_sorted_until (FI beg, FI end, FI beg2, CompFunc op)

判断 [beg, end) 内元素是否已按照 < 排序

判断 [beg, end) 内元素是否已按照 op 排序

返回 [beg, end) 内第一个破坏 < 排序的元素

返回 [beg, end) 内第一个破坏 op 排序的元素

O(n)

is_partitioned (II beg, II end, UnaryPredicate op)

判断 [beg, end) 内元素是否满足“按 op 排序的在前，不按 op 排序的在后”

O(n)

partition_point (FI beg, FI end, BinaPred op)

返回 [beg, end) 内元素按照 op [有序, 无序) 排列，无序子区间的第一个元素

RI，O(log n)

非RI，O(n)

is_heap (RI beg, RI end)

is_heap (RI beg, RI end, BinaPred op)

is_heap_until (RI beg, RI end)

is_heap_until (RI beg, RI end, BinaPred op)

判断 [beg, end) 内元素是否形成一个 heap（使用 < 比较，意味着 beg 位置为最大元素之一）

判断 [beg, end) 内元素是否形成一个 heap（使用 op 比较）

返回 [beg, end) 内阻止元素形成一个 heap（使用 < 比较，该元素比 beg 还大）的元素位置

返回 [beg, end) 内阻止元素形成一个 heap（使用 op 比较）的元素位置

O(n)

all_of (II beg, II end, UnaryPredicate op)

any_of (II beg, II end, UnaryPredicate op)

nono_of (II beg, II end, UnaryPredicate op)

判断 [beg, end) 内元素是否全部 / 或至少一个 / 或没有任何元素，使 op 返回 true

O(n)

3.1.2 更易型算法（重要）

更易型算法会改变区间内的元素内容，返回被更易的（目标区间）最后一个元素的下一位置，若因为参数问题算法没有运行一般返回源区间 beg。有两种方法更易元素：

使用迭代器遍历过程中的改动
将元素从源区间复制到目的区间的改动（加后缀 _copy）

op 函数对象内部状态不应该有改变，这样会在老旧的编译器上产生未知的结果，因为算法会保留一份关于函数的 copy，也就是说，以相同参数调用函数，返回值不应该改变，例如（不好的函数设计）：

[&](int elem){
    return ++outside_val == elem;  
}

名称（OutputIterator = OI，BidirectionalIterator = BI）	效果	复杂度
for_each (II beg, II end, UnaryProc op)	对 [beg, end) 每个元素执行 op 操作	O(n)
OI copy (II sourceBeg, II sourceEnd, OI destBeg) OI copy_if (II sourceBeg, II sourceEnd, OI destBeg, UnaryPred op) OI copy_n (II sourceBeg, Size num, OI destBeg) BI copy_backward (BI sourceBeg, BI sourceEnd, BI destEnd)	将 [sourceBeg, sourceEnd) 的元素复制到以 destBeg 为起点的区间将 [sourceBeg, sourceEnd) 内使 op 返回 true 的元素复制到以 destBeg 为起点的区间将从 sourceBeg 开始的 n 个元素复制到以 destBeg 为起点的区间将 [sourceBeg, sourceEnd) 的元素复制到以 destEnd 为终点的区间（反向遍历）	O(n)
OI move (II sourceBeg, II sourceEnd, OI destBeg) BI move_backward (BI sourceBeg, BI sourceEnd, BI destEnd)	将 [sourceBeg, sourceEnd) 的元素移动到以 destBeg 为起点的区间将 [sourceBeg, sourceEnd) 的元素移动到以 destEnd 为终点的区间（反向遍历）	O(n)
transform (II sourceBeg, II sourceEnd, OI destBeg, UnaryPred op)	将 [sourceBeg, sourceEnd) 的元素，op(elem) 返回结果写入以 destBeg 为起点的区间	O(n)
merge (II sBeg, II sEnd, II sBeg2, II sEnd2, OI destEnd) merge (II sBeg, II sEnd, II sBeg2, II sEnd2, OI destEnd, BinaPred op)	将 [sBeg, sEnd) 和 [sBeg2, sEnd2) 的元素合并写入以 destBeg 为起点的区间将 [sBeg, sEnd) 和 [sBeg2, sEnd2) 的元素以 op 排序，写入以 destBeg 为起点的区间	O(n)
swap_ranges (FI sBeg, FI sEnd, FI sBeg2)	将 [sBeg, sEnd) 和以 sBeg2 开始的元素对应交换	O(n)
void fill (FI sBeg, FI sEnd, const T& val) void fill_n (FI sBeg, Size num, const T& val)	将 [sBeg, sEnd) 内的元素赋予新值 val 将以 sBeg 开头的 num 个元素赋予新值 val	O(n)
generate (FI sBeg, FI sEnd, Func op) generate_n (FI sBeg, Size num, Func op)	调用 op 产生新值，并将之赋值给 [sBeg, sEnd) 的每个元素调用 op 产生新值，并将之赋值给以 sBeg 开头的 num 个元素	O(n)
void itoa (FI sBeg, FI sEnd, const T& startVal)	将 [sBeg, sEnd) 内的元素赋予递增值 val, val+1, val+2, ...	O(n)
void replace (FI sBeg, FI sEnd, const T& oldVal, const T& newVal) void replace_if (FI sBeg, FI sEnd, UnaryPred op, const T& newVal) replace_copy (II sBeg, II sEnd, OI destBeg, const T& oldVal, const T& newVal) replace_copy_if (II sBeg, II sEnd, OI destBeg, UnaryPred op, const T& newVal)	将 [sBeg, sEnd) 内与 oldVal 相等的元素赋予新值 newVal 将 [sBeg, sEnd) 内令 op 返回 true 的元素赋予新值 newVal 将 [sBeg, sEnd) 内与 oldVal 相等元素赋予新值 newVal,同时复制到以 destBeg 开头区间将 [sBeg, sEnd) 内令 op 返回 true 元素赋予新值 newVal,同时复制以 destBeg 开头区间	O(n)

3.1.3 移除型算法

不能以关联型容器和无序容器为目标区。

函数均返回最后一个没有被移除的元素的下一位置。

名称

效果

复杂度

FI remove (FI beg, FI end, const T& val)

FI remove_if (FI beg, FI end, UnaryPred op)

remove_copy (II sBeg, II sEnd, OI destBeg, const T& val)

remove_copy_if (II sBeg, II sEnd, OI destBeg, UnaryPred op)

移除 [sBeg, sEnd) 内与 val 相等的元素（返回最后一个未被移除元素的下一位置）

移除 [sBeg, sEnd) 内令 op 返回 true 的元素（同上）

复制 [sBeg, sEnd) 内元素到 destEnd 的过程中移除 == val 的元素

复制 [sBeg, sEnd) 内元素到 destEnd 的过程中移除令 op 返回 true 的元素

O(n)

FI unique (FI beg, FI end)

unique (FI beg, FI end, BinaPred op)

unique_copy (II sBeg, II sEnd, OI destBeg)

unique_copy (II sBeg, II sEnd, OI destBeg, BinaPred op)

移除 [sBeg, sEnd) 内与前一个元素相等的元素（有序情况下才能使区间值唯一，与 remove 返回情况相同）

移除 [sBeg, sEnd) 内使 op(e, elem) 返回 true 的 elem 移除

复制 [sBeg, sEnd) 内元素到 destEnd 的过程中移除与前一个元素相等的元素

复制 [sBeg, sEnd) 内元素到 destEnd 的过程中移除使 op(e, elem) 返回 true 的 elem

O(n)

3.1.4 变序型算法

名称（URNG = 均匀分布随机数产生器）

效果

复杂度

void reverse (BI beg, BI end)

reverse_copy (BI sBeg, BI sEnd, OI destBeg)

将 [sBeg, sEnd) 内元素反转

将 [sBeg, sEnd) 内元素复制进 destBeg 的过程中反转

O(n)

FI rotate (FI beg, FI newBeg, FI end)

rotate_copy (FI sBeg, FI newBeg, FI sEnd, OI destBeg)

将 [sBeg, sEnd) 内元素反转，其内的newBeg成为新的第一元素，返回 sBeg 经旋转后所在位置

将 [sBeg, sEnd) 内元素反转，同时复制进 destBeg

O(n)

next_permutation (BI beg, BI end)

next_permutation (BI beg, BI end, BinaPred op)

pre_permutation (BI beg, BI end)

pre_permutation (BI beg, BI end, BinaPred op)

若 [sBeg, sEnd) 内有两连续元素不符合 e1 < e2，返回 true，并使其符合 <

若 [sBeg, sEnd) 内有两连续元素不符合 op，返回 true，并使其符合 op

若 [sBeg, sEnd) 内有两连续元素不符合 e2 < e1，返回 true，并使其符合 <

若 [sBeg, sEnd) 内有两连续元素不符合 op，返回 true，并使其符合 op

O(n)

void shuffle (RI beg, RI end, URNG&& end)

void random_shuffle (RI beg, RI end)

void random_shuffle (RI beg, RI end, RandFunc&& op)

将 [sBeg, sEnd) 内元素重新洗牌，使用随机数引擎 end

将 [sBeg, sEnd) 内元素重新洗牌，使用均匀分布随机数产生器

使用 op 将 [sBeg, sEnd) 内元素重新洗牌，op(max) 应返回一个 (0, max) 的随机数，max=difference_type

O(n)

partition (FI beg, FI end, UnaryPred op)

stable_partition (BI beg, BI end, UnaryPred op)

partition_copy (II sBeg, II sEnd, OI dsTrBeg, OI dsFsBeg, UnaryPred op)

将 [sBeg, sEnd) 内造成 op 返回 true 的元素向前移动

将 [sBeg, sEnd) 内造成 op 返回 true 的元素向前移动，保持元素间的相对次序

将 [sBeg, sEnd) 内造成 op 返回 true 的元素复制入 dsTrBeg，反之复制入 dsFsBeg

O(n)

随机数程序库（于头文件 random）的一般用法：

引擎：是函数对象，能产生随机的无符号值，并均匀分布于一个预定义的最大最小值间（半开区间 [)）
分布：以某种手法将引擎产生的随机值分布于指定的区间

一般使用的引擎:

std::defult_random_engine dre;

一般使用的分布 :

std::uniform_int_distribution<T> uid (min_rand, max_rand);  // T 为各种整型：short, int, long, long long, 及对应的 unsigned
std::uniform_real_distribution<T> uid (min_rand, max_rand);// T 为各种浮点型：float, double（默认）, long double

组合调用：

std::out << uid ( dre ) << std::endl;  //输出 [min_rand, max_rand) 间的一个随机数

避免使用临时引擎，这样洗牌方式是单一的，可以预测下一步的结果：

std::shuffle (v.begin(), v.end(), std::default_random_engine());  //避免这种调用
//改为这种调用
std::default_random_engine dre;
std::shuffle (v.begin(), v.end(), dre); 
...
std::shuffle (v.begin(), v.end(), dre);  //不可预测

3.1.5 排序算法

名称

效果

复杂度

void sort (RI beg, RI end)

void sort (RI beg, RI end, BinaPred op)

以 < 对 [beg, end) 内元素排序（使用快排，不稳定排序）

以 op 规则对 [beg, end) 内元素排序（同上）

平均 O(n log n)

最差 O(n^2)

void stable_sort (RI beg, RI end)

void stable_sort (RI beg, RI end, BinaPred op)

以 < 对 [beg, end) 内元素排序（使用归并，稳定排序）

以 op 规则对 [beg, end) 内元素排序（同上）

内存够 O(n log n)

内存不够 O(n log n * log n)

partial_sort (RI beg, RI sortEnd, RI end)

partial_sort (RI beg, RI sortEnd, RI end, BinaPred op)

partial_sort_copy (II sBeg, II sEnd, RI dsBeg, RI dsEnd)

partial_sort_copy (II sBeg, II sEnd, RI dsBeg, RI dsEnd, BinaPred op)

以 < 对 [beg, end) 内元素排序，使 [beg, sortEnd) 内元素有序

以 op 对 [beg, end) 内元素排序，使 [beg, sortEnd) 内元素有序

将 [sbeg, send) 内元素复制入 [dsBeg, dsEnd) 并以 < 排序

将 [sbeg, send) 内元素复制入 [dsBeg, dsEnd) 并以 op 排序

O(n log n)

nth_element (RI beg, RI nth, RI end)

nth_element (RI beg, RI nth, RI end, BinaPred op)

使 beg + nth 位置左边值小于之，右边值大于之，不要求全部有序

使 op(leftelem, beg + nth) 返回 true，op(beg + nth,rightelem) 返回 false

O(n)

partition (FI beg, FI end, UnaryPred op)

partition_copy (II sBeg, II sEnd, OI dsBeg, OI dsBeg, UnaryPred op)

将 [beg, end) 内元素造成 op 返回 true 的都向前移动（不稳定排序）

将 [sbeg, send) 内元素复制入 [dsBeg, dsEnd)，并以 op 分割（同上）

O(n)

stable_partition (BI beg, BI end, UnaryPred op)

将 [beg, end) 内元素造成 op 返回 true 的都向前移动（稳定排序）

内存足 O(n)

内存不足 O(n log n)

void make_heap (RI beg, RI end)

void make_heap (RI beg, RI end, BinaPred op)

以 less<T> 规则，将 [beg, end) 内元素转化为 heap（大顶堆）

以 op 规则，将 [beg, end) 内元素转化为 heap

O(n)

void push_heap (RI beg, RI end)

void push_heap (RI beg, RI end, BinaPred op)

void pop_heap (RI beg, RI end)

void pop_heap (RI beg, RI end, BinaPred op)

以 less<T> 规则，将 end - 1 位置元素入 heap，使[beg, end) 内元素成 heap

以 op 规则，将 end - 1 位置元素入 heap，使[beg, end) 内元素成 heap

以 less<T> 规则，将 beg 位置元素移到最后位置，将剩余 [beg-1, end-1] 元素成 heap

以 op 规则，将 beg 位置元素移到最后位置，将剩余 [beg-1, end-1] 元素成 heap

O(log n)

void sort_heap (RI beg, RI end)

void sort_heap (RI beg, RI end, BinaPred op)

以 less<T> 规则，将 heap [beg, end) 转换为一个有序序列（不再是堆 == 堆排序）

以 op 规则，将 heap [beg, end) 转换为一个有序序列（同上）

O(n log n)

3.1.6 已排序区间算法

顾名思义，需要保证区间已经有序的情况下使用此类算法。

名称（IT = 多类型的Iterator）

效果

复杂度

bool binary_search (FI beg, FI end, const T& val)

bool binary_search (FI beg, FI end, const T& val, BF op)

[beg, end) 内包含 == val 的元素，则返回 true，反之则反

以 op 为排序准则，[beg, end) 内包含 == val 的元素，则返回 true，反之则反

RI, O(log n)

非 RI, O(n)

includes (II beg, II end, II searchBeg, II searchEnd)

includes (II beg, II end, II searchBeg, II searchEnd, BF op)

返回 [beg, end) 是否包含 [searchBeg, searchEnd) 的全部元素

以 op 为排序准则，返回 [beg, end) 是否包含 [searchBeg, searchEnd) 的全部元素

O(n)

FI lower_bound (FI beg, FI end, const T& val)

FI lower_bound (FI beg, FI end, const T& val, BF op)

FI upper_bound (FI beg, FI end, const T& val)

FI upper_bound (FI beg, FI end, const T& val, BF op)

pair<FI, FI> equal_range (FI beg, FI end, const T& val)

pair<FI, FI> equal_range (FI beg, FI end, const T& val, BF op)

返回 [beg, end) 内第一个 >= val 的元素位置

以 op 为排序准则（可有可无），返回 [beg, end) 内第一个 >= val 的元素位置

返回 [beg, end) 内第一个 > val 的元素位置

以 op 为排序准则（可有可无），返回 [beg, end) 内第一个 > val 的元素位置

返回 [beg, end) 内 == val 的元素形成的位置区间 pair

以 op 为排序准则（可有可无），返回 [beg, end) 内 == val 的元素形成的位置区间 pair

RI, O(log n)

非 RI, O(n)

merge (II beg, II end, II beg2, II end2, OI dsBeg)

merge (II beg, II end, II beg2, II end2, OI dsBeg, BF op)

inplace_merge (II beg, II end1beg2, II end2)

inplace_merge (II beg, II end1beg2, II end2, BF op)

合并 [beg, end) 和 [beg2, end2) 内元素，写入dsBeg（合并后也有序）

以 op 为排序准则（可有可无），合并 [beg, end) 和 [beg2, end2) 内元素，写入dsBeg

使 [beg1, end2) 容纳的是 [beg, end1beg2) 和 [end1beg2, end2) 的有序合并

可有可无的排序规则（同上）

O(n)

OI set_union (II beg, II end, II beg2, II end2, OI dsBeg)

OI set_union (II beg, II end, II beg2, II end2, OI dsBeg, BF op)

OI set_intersection (II beg, II end, II beg2, II end2, OI dsBeg)

OI set_intersection (II beg, II end, II beg2, II end2, OI dsBeg, BF op)

OI set_difference (II beg, II end, II beg2, II end2, OI dsBeg)

OI set_difference (II beg, II end, II beg2, II end2, OI dsBeg, BF op)

set_symmetric_difference (II beg, II end, II beg2, II end2, OI dsBeg)

set_symmetric_difference (II beg, II end, II beg2, II end2, OI dsBeg, BF op)

将 [beg, end) 和 [beg2, end2) 的并集写入 deBeg

可有可无的排序规则（同上）

将 [beg, end) 和 [beg2, end2) 的交集写入 deBeg

可有可无的排序规则（同上）

将 [beg, end) - [beg2, end2) 的差集写入 deBeg（元素只存在于前者不存在于后者）

可有可无的排序规则（同上）

将 [beg, end) 和 [beg2, end2) 的（元素只存在于前者或只存在于后者）写入 deBeg

可有可无的排序规则（同上）

O(n)

partition_point (FI beg, FI end, BinaPred op)

返回 [beg, end) 内元素按照 op [有序, 无序) 排列，无序子区间的第一个元素

RI O(log n)

非 RI, O(n)

3.1.7 数值算法

名称（BF=BinaryFunction）

效果

复杂度

accumulate (II beg, II end, T iniVal)

accumulate (II beg, II end, T iniVal, BinaFunc op)

计算 iniVal 和 [beg, end) 内每个元素的和（iniVal += elem,返回iniVal）

计算 iniVal 和 [beg, end) 内, iniVal = op(iniVal,elem),返回iniVal

O(n)

inner_product (II beg, II end, II beg2, T iniVal)

inner_product (II beg, II end, II beg2, T iniVal, BF op, BF op2)

计算 [beg, end) 和 beg2 区间每个元素的內积和，iniVal += elem*elem2

iniVal = op ( iniVal, op2 (elem, elem2) )

O(n)

adjacent_difference (II sBeg, II sEnd, OI dsBeg)

adjacent_difference (II sBeg, II sEnd, OI dsBeg, BF op)

计算 [sBeg, sEnd) 相邻元素的差，结果写入 dsBeg（对于 a, b, c 计算 a, b-a, c-b）

计算 [sBeg, sEnd) 相邻元素（对于 a, b, c 计算 a, b op a, c op b），结果写入 dsBeg

O(n)

partial_sum (II sBeg, II sEnd, OI dsBeg)

partial_sum (II sBeg, II sEnd, OI dsBeg, BF op)

计算 [sBeg, sEnd) 每个元素的部分和，结果写入 dsBeg（对于 a,b,c 计算 a,a+b,a+b+c）

计算 [sBeg, sEnd) 每个元素（对于 a,b,c 计算 a,a op b,a op b op c），结果写入 dsBeg

O(n)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)