C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件 —— 算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

示例：

• 算法： sort(a.begin(), a.end())
• 容器： priority_queue<int> pque
• 仿函数： greater<int>()
• 迭代器： vector<int>::iterator it = a.begin()

# 前言

STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间，这一点不仅是由于可以直接调用，还是因为它封装良好，可以让代码的可读性变高，解题思路更清晰，调试过程 往往 更顺利。

不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能，它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此，STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此，在实际比赛中要权衡 STL 的利弊，不过这一点就得靠经验了。

接下来，我会分享在算法竞赛中常用的 STL 容器和算法，对于函数和迭代器，就不着重展开讲了。

# 常用容器

# 内容总览

打勾的是本次将会详细讲解的，加粗的是算法竞赛中有必要学习的。

• 顺序容器

  • array

  • vector

  • deque

  • forward_list

  • list

• 关联容器

  • set
  • map
  • multiset
  • multimap

• 无序关联容器

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap

• 容器适配器

  • stack
  • queue
  • priority_queue
  • flat_set
  • flat_map
  • flat_multiset
  • flat_multimap

• 字符串

  • string (basic_string<char>)

• 对与元组

  • pair
  • tuple

# 向量 vector

#include <vector>

连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

# 常用方法

# 构造

vector<类型> arr(长度, [初值])

时间复杂度：$O(n)$

常用的一维和二维数组构造示例，高维也是一样的（就是会有点长）.

vector<int> arr;         // 构造 int 数组

vector<int> arr(100);    // 构造初始长 100 的 int 数组

vector<int> arr(100, 1); // 构造初始长 100 的 int 数组，初值为 1

vector<vector<int>> mat(100, vector<int> ());       // 构造初始 100 行，不指定列数的二维数组

vector<vector<int>> mat(100, vector<int> (666, -1)) // 构造初始 100 行，初始 666 列的二维数组，初值为 - 1

构造二维数组的奇葩写法，千万别用：

vector<int> arr[100];         // 正确，构造初始 100 行，不指定列数的二维数组，可用于链式前向星存图

vector<int> arr[100](100, 1); // 语法错误！

vector<int> arr(100, 1)[100]; // 语法错误！

vector<int> arr[100] <!--swig0-->; // 正确但奇葩，使用列表初始化

# 尾接 & 尾删

• .push_back(元素) ：在 vector 尾接一个元素，数组长度 $+1$.
• .pop_back() ：删除 vector 尾部的一个元素，数组长度 $-1$

时间复杂度：均摊 $O(1)$

// init: arr = []

arr.push_back(1);

// after: arr = [1]

arr.push_back(2);

// after: arr = [1, 2]

arr.pop_back();

// after: arr = [1]

arr.pop_back();

// after: arr = []

# 中括号运算符

和一般数组一样的作用

时间复杂度：$O(1)$

# 获取长度

.size()

获取当前 vector 的长度

时间复杂度：$O(1)$

for (int i = 0; i < arr.size(); i++)

    cout << a[i] << endl;

# 清空

.clear()

清空 vector

时间复杂度：$O(n)$

# 判空

.empty()

如果是空返回 true 反之返回 false .

时间复杂度：$O(1)$

# 改变长度

.resize(新长度, [默认值])

修改 vector 的长度

• 如果是缩短，则删除多余的值
• 如果是扩大，且指定了默认值，则新元素均为默认值 **（旧元素不变）**

时间复杂度：$O(n)$

# 适用情形

一般情况 vector 可以替换掉普通数组，除非该题卡常。

有些情况普通数组没法解决：$n\times m$ 的矩阵，$1\leq n,m\leq 10^6$ 且 $n\times m \leq 10^6$

• 如果用普通数组 int mat[1000010][1000010] ，浪费内存，会导致 MLE。
• 如果使用 vector<vector<int>> mat(n + 10, vector<int> (m + 10)) ，完美解决该问题。

另外， vector 的数据储存在堆空间中，不会爆栈。

# 注意事项

# 提前指定长度

如果长度已经确定，那么应当直接在构造函数指定长度，而不是一个一个 .push_back() . 因为 vector 额外内存耗尽后的重分配是有时间开销的，直接指定长度就不会出现重分配了。

// 优化前: 522ms

vector<int> a;

for (int i = 0; i < 1e8; i++)

    a.push_back(i);

// 优化后: 259ms

vector<int> a(1e8);

for (int i = 0; i < a.size(); i++)

    a[i] = i;

# 当心 size_t 溢出

vector 获取长度的方法 .size() 返回值类型为 size_t ，通常 OJ 平台使用的是 32 位编译器（有些平台例如 cf 可选 64 位），那么该类型范围为 $[0,2^{32})$.

vector<int> a(65536);

long long a = a.size() * a.size(); // 直接溢出变成 0 了

# 栈 stack

#include <stack>

通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。

# 常用方法

# 适用情形

如果不卡常的话，就可以直接用它而不需要手写栈了。

另外，vector 也可以当栈用，vector 的 .back() 取尾部元素，就相当于取栈顶， .push_back() 相当于进栈， .pop_back() 相当于出栈。

# 注意事项

不可访问内部元素！下面都是错误用法

for (int i = 0; i < stk.size(); i++)

    cout << stk[i] << endl;

for (auto ele : stk)

    cout << stk << endl;

# 队列 queue

#include <queue>

通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。

# 常用方法

# 适用情形

如果不卡常的话，就可以直接用它而不需要手写队列了。

# 注意事项

不可访问内部元素！下面都是错误用法

for (int i = 0; i < que.size(); i++)

    cout << que[i] << endl;

for (auto ele : que)

    cout << ele << endl;

# 优先队列 priority_queue

#include <queue>

提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

# 常用方法

# 构造

priority_queue<类型, 容器, 比较器> pque

• 类型：要储存的数据类型
• 容器：储存数据的底层容器，默认为 vector<类型> ，竞赛中保持默认即可
• 比较器：比较大小使用的比较器，默认为 less<类型> ，可自定义

priority_queue<int> pque1;                            // 储存 int 的大顶堆

priority_queue<int, vector<int>, greater<int>> pque2; // 储存 int 的小顶堆

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 /lambda 表达式），在此就不展开讲了。如果想要了解，可以查阅 cppreference 中的代码示例。

# 其他

进出队复杂度 $O(\log n)$，取堆顶 $O(1)$.

# 适用情形

持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列里取出大小最小 / 最大的元素，元素数量 $n$，插入操作数量 $k$.

• 每次插入后进行快速排序：$k\cdot n\log n$
• 使用优先队列维护：$k\cdot\log n$

# 注意事项

# 仅堆顶可读

只可访问堆顶，其他元素都无法读取到。下面是错误用法：

cout << pque[1] << endl;

# 所有元素不可写

堆中所有元素是不可修改的。下面是错误用法：

pque[1] = 2;

pque.top() = 1;

如果你恰好要修改的是堆顶元素，那么是可以完成的：

int tp = pque.top();

pque.pop();

pque.push(tp + 1);

# 集合 set

#include <set>

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

# 常用方法

# 构造

set<类型, 比较器> st

• 类型：要储存的数据类型
• 比较器：比较大小使用的比较器，默认为 less<类型> ，可自定义

set<int> st1;               // 储存 int 的集合（从小到大）

set<int, greater<int>> st2; // 储存 int 的集合（从大到小）

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 /lambda 表达式），在此就不展开讲了。

# 遍历

可使用迭代器进行遍历：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)

    cout << *it << endl;

基于范围的循环（C++ 11）：

for (auto &ele : st)

    cout << ele << endl;

# 其他

增删查时间复杂度均为 $O(\log n)$

# 适用情形

• 元素去重：$[1,1,3,2,4,4]\to[1,2,3,4]$
• 维护顺序：$[1,5,3,7,9]\to[1,3,5,7,9]$
• 元素是否出现过：元素大小 $[-10^{18},10^{18}]$，元素数量 $10^6$，vis 数组无法实现，通过 set 可以完成。

# 注意事项

# 不存在下标索引

set 虽说可遍历，但仅可使用迭代器进行遍历，它不存在下标这一概念，无法通过下标访问到数据。下面是错误用法：

cout << st[0] << endl;

# 元素只读

set 的迭代器取到的元素是只读的（因为是 const 迭代器），不可修改其值。如果要改，需要先 erase 再 insert. 下面是错误用法：

cout << *st.begin() << endl; // 正确。可读。

*st.begin() = 1;             // 错误！不可写！

# 不可用迭代器计算下标

set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：

auto it = st.find(2);      // 正确，返回 2 所在位置的迭代器。

int idx = it - st.begin(); // 错误！不可相减得到下标。

# 映射 map

#include <map>

提供对数时间的有序键值对结构。底层原理是红黑树。

映射：

$$\begin{matrix} 1&\to&2\\ 2&\to&2\\ 3&\to&1\\ 4&\to&5\\ &\vdots \end{matrix}$$

# 常用方法

# 构造

map<键类型, 值类型, 比较器> mp

• 键类型：要储存键的数据类型
• 值类型：要储存值的数据类型
• 比较器：键比较大小使用的比较器，默认为 less<类型> ，可自定义

map<int, int> mp1;               //int->int 的映射（键从小到大）

map<int, int, greater<int>> st2; //int->int 的映射（键从大到小）

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 /lambda 表达式），在此就不展开讲了。

# 遍历

可使用迭代器进行遍历：

for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)

    cout << it->first << ' ' << it->second << endl;

基于范围的循环（C++ 11）：

for (auto &pr : mp)

    cout << pr.first << ' ' << pr.second << endl;

结构化绑定 + 基于范围的循环（C++17）：

for (auto &[key, val] : mp)

    cout << key << ' ' << val << endl;

# 其他

增删改查时间复杂度均为 $O(\log n)$

# 适用情形

需要维护映射的场景可以使用：输入若干字符串，统计每种字符串的出现次数。( map<string, int> mp )

# 注意事项

# 中括号访问时默认值

如果使用中括号访问 map 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。

map<char, int> mp;

cout << mp.count('a') << endl; // 0

mp['a'];                       // 即使什么都没做，此时 mp ['a']=0 已经插入了

cout << mp.count('a') << endl; // 1

cout << mp['a'] << endl;       // 0

# 不可用迭代器计算下标

map 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：

auto it = mp.find('a');      // 正确，返回 2 所在位置的迭代器。

int idx = it - mp.begin();   // 错误！不可相减得到下标。

# 字符串 string

#include <string>

顾名思义，就是储存字符串的。

# 常用方法

# 构造

构造函数： string(长度, 初值)

string s1;           // 构造字符串，为空

string s2 = "awa!";  // 构造字符串，并赋值 awa!

string s3(10, '6');  // 构造字符串，通过构造函数构造为 6666666666

# 输入输出

C++

string s;

cin >> s;

cout << s;

C

string s;

char buf[100];

scanf("%s", &buf);

s = buf;

printf("%s", s.c_str());

# 其他

# 数值与字符串互转（C++11）

# 适用情形

非常好用！建议直接把字符数组扔了，赶快投入 string 的怀抱。

# 注意事项

# 尾接字符串一定要用 +=

string 的 += 运算符，将会在原字符串原地尾接字符串。而 + 了再 = 赋值，会先生成一个临时变量，在复制给 string.

通常字符串长度可以很长，如果使用 + 字符串很容易就 TLE 了。

// 优化前: 15139ms

string s;

for (int i = 0; i < 5e5; i++)

    s = s + "a";

// 优化后: < 1ms (计时器显示 0)

string s;

for (int i = 0; i < 5e5; i++)

    s += "a";

# .substr() 方法的奇葩参数

一定要注意，C++ string 的取子串的第一个参数是子串起点下标，第二个参数是子串长度。

第二个参数不是子串终点！不是子串终点！要与 java 等其他语言区分开来。

# .find() 方法的复杂度

该方法实现为暴力实现，时间复杂度为 $O(n^2)$.

不要幻想 STL 内置了个 $O(n)$ 的 KMP 算法

# 二元组 pair

#include <utility>

顾名思义，就是储存二元组的。

# 常用方法

# 构造

pair<第一个值类型, 第二个值类型> pr

• 第一个值类型：要储存的第一个值的数据类型
• 第二个值类型：要储存的第二个值的数据类型

pair<int, int> p1;

pair<int, long long> p2;

pair<char, int> p3;

// ...

# 赋值

老式

pair<int, char> pr = make_pair(1, 'a');

列表构造 C++11

pair<int, char> pr = {1, 'a'};

# 取值

直接取值

• 取第一个值： .first
• 取第二个值： .second

pair<int, char> pr = {1, 'a'};

int awa = pr.first;

char bwb = pr.second;

结构化绑定 C++17

pair<int, char> pr = {1, 'a'};

auto &[awa, bwb] = pr;

# 判同

直接用 == 运算符

pair<int, int> p1 = {1, 2};

pair<int, int> p2 = {1, 3};

if (p1 == p2) { ... } // false

# 适用场景

所有需要二元组的场景均可使用，效率和自己定义结构体差不多。

# 注意事项

无