注：文章由博主同步发布于：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)

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

通过STM32F103寄存器点亮一盏LED
通过STM32F103寄存器点亮一盏LED首先我们需要配置GPIO的寄存器才能去控制GPIO,学习单片机我建议用通过动手去配置寄存器去学习比操作库更好地去明白学习单片机的原理。函数库的本质就是把配置好的寄存器封装起来，我们学习操作寄存器才是真正掌握单片机。 GPIO寄存器的一共有…...
2024/5/1 8:53:48
数据结构（一）初识数据
数据结构（一）初识数据作者：秋名撰写时间：2020 年 6 月 10 日如果说语言是开发的工具，那算法就是开发的灵魂。 1、数据：数据项、数据元素、数据对象2、数据结构：逻辑结构，存储结构2.1逻辑结构：线性结构和非线性结构2.1.0线性结构（一对一）2.1.1非线性结构（树：一对…...
2024/4/20 11:37:14
关于使用QT creator遇到 obj/main.o: Relocations in generic ELF (EM: 3)错误
做实验的时候遇到的问题记录一下。搜索网上得到的答案是进入工程文件之后，使用命令行#make clean -w但是继续编译仍然报错。考虑到可能先前错误编译可能有影响，于是我们先前编译得到的文件删了（下图的WirelessAlarm-build-desktop）。重新编译问题得到解决。...
2024/4/15 4:30:37
Kafka数据存储
目录Kafka文件存储机制Kafka数据的存储方式Kafka如何通过offset查找message附 Kafka文件存储机制- Topic：一类消息，例如page view日志、click日志等都可以以topic的形式存在，Kafka集群能够同时负责多个topic的分发- Partition：topic物理上的分组，一个topic可以分为多个par…...
2024/5/7 9:20:21
凌姗说币：6.10比特币,以太坊晚间行情分析及操作建议
前言：投资，就好比就像一场舞会，教会你最初舞步的人却很少能陪你走到散场!东西若丢，不过方圆百里;信心若丢，则是天涯海角!【行情回顾】今日白盘就是从早间下跌100多美金后，一直处于小幅的区间震荡，行情枯燥无味，来回波动不到100点，多空之战愈演愈烈，暴风雨即将来临。【…...
2024/4/15 4:30:34
mongodb-node
参考文档 https://segmentfault.com/a/1190000002973153 https://www.cnblogs.com/jayruan/p/5123754.html https://www.jianshu.com/p/8af0552831f6 node连接mongodb方式一 http://www.runoob.com/nodejs/nodejs-mongodb.html node连接mongodb方式二什么是mongoose? 基于node…...
2024/4/29 2:22:04
7-5（选做）一帮一 (15分)C语言
7-5（选做）一帮一 (15分) “一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后…...
2024/5/7 13:48:12
杰林码检错纠错算法的核心数理部分（王杰林）
设信源生成长度为n(n=1,2,…)n(n = 1,2,\ldots)n(n=1,2,…)的二进制伯努利序列X=(X1,X2,…,Xi,…,Xn)X\mathbf{=}\left(X_{1},X_{2},\ldots,X_{i},\ldots,X_{n} \right)X=(X1,X2,…,Xi,…,Xn)。下面分析两种检错方法及其检错概率。 2.1.1 检错方法一给定一个整数t=1,2…...
2024/5/1 7:01:08
kali虚拟机连接网络
kali虚拟机连接网络 1.版本选择 Ubuntu 别安装kali64什么的，有的包是坏的，记住配不了网，我没搞成功勾勾选对了就好了首先我用的是VM,其次额，我想说2020年之后你下载的镜像安装好之后网络是可以使用的，无需额外配置，哈哈哈（我想你定是看到时间不对，其实时间本来就不同…...
2024/5/1 8:49:10
Linux进程间通信——信号量
Linux进程间通信——信号量 Linux提供了多种进程间通信的方法，常见有管道（匿名）、FIFO（有名管道）、消息队列、信号量、共享内存，socket通信。 4.信号量信号量（semaphore）是一种用于提供不同进程之间或者一个给定的不同线程间同步手段的原语。信号量多用于进程间的同步…...
2024/5/1 13:36:49
树莓派语音控制智能家居天气预报邮件
使用的是树莓派3B+，淘宝买个麦克风，再买个音响来也可以用耳机。要去找找配置snowboy的一个环境，然后去百度语音平台申请账号密匙， snowboy的一些参考网站添加链接描述添加链接描述语音收发邮件的一些参考内容可以看看这篇博客以及这个smtp协议添加链接描述语音播放天气…...
2024/5/1 14:55:49
【基础】三报文握手与四报文挥手详解以及 Q&A
概念三报文握手：客户端与服务器通过传输三条报文建立连接四报文挥手：客户端与服务器通过传输四条报文断开连接标识符说明先看下图图中的 A1 - B2 表示报文代号（方便后续说明），一个箭头表示一条报文，报文上的标识符依次为：SYN：表示建立连接标志，发起建立连接请求时，其…...
2024/5/1 13:20:04
P1652 圆
题目描述给出 n 个圆,保证任意两个圆都不相交。然后给出两个点 (x1,y1),(x2,y2 )，保证均不在某个圆上，要从 (x1,y1 )→(x2,y2) 画条曲线，问这条曲线最少穿过多少次圆的边界？输入格式第一行为一个整数 n，表示圆的个数；第二行是 n 个整数，表示 n 个圆的 x 坐标；第三…...
2024/5/1 13:51:07
二叉树的遍历(非递归)
#include<stdio.h> #include<malloc.h> #define MAXSIZE 100 typedef char Elemtype; typedef struct BiTreeNode{Elemtype value;BiTreeNode *lchild,*rchild;int tag;//tag 为0代表第一次访问为1代表第二次访问 }*BiTree,BiTreeNode; BiTree CreateTree(); void…...
2024/5/1 15:40:35
面试官：能跟我说一下rm删除文件之后，空间都发生了什么吗？
但凡知道Linux指令的，相信一定听过这样的一行命令：rm -rf /*，哪怕不知道这行命令，总听过一句话，删库跑路吧，那么，rm删除一个文件之后，就是单纯的把文件删除然后释放空间吗产生一个指定大小的随机内容文件我们先看一下当前各个挂载目录的空间大小：$ df -h /dev/sda11 …...
2024/5/1 13:39:20
H04-HDFS读写流程
写操作文件A大小100M，client将A写入到HDFS上 HDFS按照默认配置， HDFS分布在三个机架上Rack1，Rack2，Rack3 写流程 A. client将A按照64M分块。分成两块：block1、block2 B. client向NameNode发送写数据请求，如图蓝色虚线① C.NameNode节点记录block信息。并返回可用DataNode…...
2024/5/1 15:03:04
SpringBoot中同时有yml和properties两种配置文件，springboot会加载哪个？
我们来试一下就知道了当前只有一个yml配置文件如果我再加一个properties配置文件，会是什么情况呢？启动一下看看结果是8082 删掉properties文件内容，端口会是8080还是加载yml的配置呢？事实是properties如果为空，会加载yml的配置内容，如果都为空，则默认8080...
2024/5/1 17:10:25
宠物的生长
现在要开发一个系统，对宠物的生长状态进行管理。给出下面的一个基类框架 class Pet { protected:string name;//姓名 int length;//身长 int weight;//体重 int current;//当前日期 public: virtual void display(int day)=0;//输出目标日期的身长和体重 } 以Pet为基类，构建…...
2024/5/1 20:22:08
mooc游戏设计基础（自学）5
mooc自学网址： https://www.icourse163.org/learn/CUC-1450328379?tid=1450742649#/learn/content?type=detail&id=1216695336&sm=1 第五章第五个小游戏是制作博德曼分形集合，根据博德曼公式进行迭代，然后将收敛区域部分绘制成黑色，发散区域绘制成白色。(分形指…...
2024/5/1 12:43:18
Java学生管理系统GUI图形界面V1.0
不细说了，这会要去改进美化界面了，代码中用了很多笨方法，总算是实现了这个程序，源码如下：（温馨提示：左侧应该有导航栏，其实我刚刚发现） Main：主函数&Filew：文件操作 package student;import java.io.*; import java.util.ArrayList; import java.util.List;impo…...
2024/5/1 13:05:32

STL 容器、迭代器、算法小结

标准模板库

1 容器（Container）

1.1 序列式容器（Sequence container）

1.2 关联式容器（Asociative container）

1.3 无序容器（Unordered container）

2 迭代器（Iterator）

2.1 用法汇总

2.2 迭代器辅助函数

3 算法（Algorithm）

3.1 分类

相关文章

最新文章