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

1  标准模板库

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

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

1.1  STL组件(Component)

STL组件中最关键的是:

  • 容器
  • 迭代器
  • 算法

1.1.1  容器(Container)

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

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

序列式容器(Sequence container)

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

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

Tips:通常,使用vector是最佳选择。

  • heap 由 vector 实现
  • priority_queue 由 heap 实现
  • stack 和 queue 由 deque 实现
共有操作(重要

初始化

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 所指向的元素前面插入由迭代器 be 标记的范围内的元素。返回新添加的第一个元素的迭代器,

若范围为空,返回 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 为空容器,则该函数未定义

关联式容器(Asociative container)

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

  • set
  • multiset
  • map
  • multimap
共有操作(重要

关联容器额外的类型别名

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

无序容器(Unordered container)

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

  • unordered_set
  • unordered_multiset
  • unordered_map
  • unordered_multimap
共用操作

见上表

1.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 容器所使用的的迭代器类型,可以帮助我们避免刻板印象造成的错误。

用法汇总

表达式 效果
为方便总结绘制成一张表,下面的迭代器同样提供上面迭代器的操作
*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 之前

迭代器辅助函数

  • 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 之前或处于同一位置。

1.1.3  算法(Algorithm)

用来处理集合内的元素。

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

分类

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

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

算法具体分为 7 大类:

  1. Nonmodifying algorithms(非更易型算法)

  2. Modifying algorithms(更易型算法)

  3. Removing algorithms(移除型算法)

  4. Mutating algorithms(变序型算法)

  5. Sorting algorithms(排序算法)

  6. Sorted range algorithms(已排序区间算法)

  7. Numeric algorithms(数值算法)

非更易型算法

非更易型算法不改动元素次序,也不改变元素值(使用者不应该让自定义的函数改变元素的值或者次序)。它通过 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)
更易型算法(重要

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

  1. 使用迭代器遍历过程中的改动
  2. 将元素从源区间复制到目的区间的改动(加后缀 _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)  
移除型算法

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

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

名称 效果 复杂度

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)
变序型算法
名称(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);  //不可预测
排序算法
名称 效果 复杂度

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)
已排序区间算法

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

名称(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)

数值算法
名称(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)
原文地址:https://www.cnblogs.com/icky1024/p/STL-Summery.html