C++STL

2 常用容器

2.1 内容总览

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

• 顺序容器

  • [ ]array

  • [x]vector

  • [ ]deque

  • [ ] forward_list

  • [ ]list

• 关联容器

  • [x]set
  • [x]map
  • [ ]multiset
  • [ ]multimap

• 无序关联容器

  • [ ]unordered_set
  • [ ]unordered_map
  • [ ]unordered_multiset
  • [ ]unordered_multimap

• 容器适配器

  • [x]stack
  • [x]queue
  • [x]priority_queue
  • [ ] flat_set
  • [ ] flat_map
  • [ ] flat_multiset
  • [ ] flat_multimap

• 字符串

  • [x]string(basic_string<char>)

• 对与元组

  • [x]pair
  • [ ]tuple

2.2 向量 vector

#include <vector>

长度可变的数组

2.2.1 常用方法

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

注意二维vector的构造

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

尾接 & 尾删.push_back(元素)：在 vector 尾接一个元素，数组长度 .//.pop_back()：删除 vector 尾部的一个元素，数组长度

获取长度.size()

清空.clear()

判空.empty()

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

修改 vector 的长度

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

//原本数组1 2 3 q.resize(5);//1 2 3 0 0默认增加的值为0 q.resize(5,3);//1 2 3 3 3 q.resize(2);//1 2

2.2.3 注意事项

提前指定长度时不用vector

当心 size_t 溢出

.size()返回值类型为size_t，具体数据范围根据不同编译器来定

2.3 栈 stack--先进后出

#include <stack>

2.3.3 注意事项

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

for (int i = 0; i < stk.size(); i++) cout << stk[i] << endl; for (auto ele : stk) cout << stk << endl;

2.4 队列 queue--先进先出

#include <queue>

2.4.3 注意事项

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

for (int i = 0; i < que.size(); i++) cout << que[i] << endl; for (auto ele : que) cout << ele << endl;

2.5 二叉堆 priority_queue--优先队列

2.5.1 适用情形

每次从队列里取出大小最小/最大的元素

2.5.2 常用方法

构造

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

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

其他

2.5.3 注意事项

仅堆顶可读

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

cout << pque[1] << endl;

所有元素不可写

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

pque[1] = 2; pque.top() = 1;

2.6 集合 set

#include <set>

2.6.1 常用方法

构造

set<类型, 比较器> s

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

遍历

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

for (auto &ele : st) cout << ele << endl;

其他

2.6.3 注意事项

不存在下标索引

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

cout << st[0] << endl;

元素只读

元素是只读的，不可修改其值。如果要改，需要先 erase 再 insert.下面是错误用法：

2.7 映射 map

#include <map>

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

映射：

2.7.1 常用方法

构造

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

map<int, int> mp1; // int->int 的映射（键从小到大） map<int, int, greater<int>> st2; // int->int 的映射（键从大到小） map<string , vector<int>> mp2; mp1[2]=1; //赋值

遍历

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

for (auto &pr : mp) cout << pr.first << ' ' << pr.second << endl;

其他

2.7.3 注意事项

中括号访问时默认值

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

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(); // 错误！不可相减得到下标。

2.8 字符串 string

#include <string>

2.8.1 常用方法

构造

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

string s1; // 构造字符串，为空 string s2 = "awa!"; // 构造字符串，并赋值awa! string s3(10, '6'); // 构造字符串，通过构造函数构造为6666666666

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

2.8.2 适用情形

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

2.8.3 注意事项

尾接字符串一定要用+=

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()方法的复杂度

该方法实现为暴力实现，时间复杂度为 .

不要幻想 STL 内置了个 的 KMP 算法

2.9 二元组 pair

#include <utility>

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

2.9.1 常用方法

构造

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

2.9.2 适用场景

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

2.9.3 注意事项

无

3 迭代器简介

3.1 迭代器是什么？

不搞抽象，直接举例。

对于一个 vector，我们可以用下标遍历：

for (int i = 0; i < a.size(); i++) cout << a[i] << endl;

我们同时也可以用迭代器来遍历：

for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) cout << *it << endl;

• a.begin()是一个迭代器，指向的是第一个元素
• a.end()是一个迭代器，指向的是最后一个元素再后面一位
• 上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
• 迭代器与指针相似，如果对它使用解引用运算符，即*it，就能取到对应值了

3.2 为何需要迭代器？

很多数据结构并不是线性的（例如红黑树），对于非线性数据结构，下标是无意义的。无法使用下标来遍历整个数据结构。

迭代器的作用就是定义某个数据结构的遍历方式，通过迭代器的增减，代表遍历到的位置，通过迭代器便能成功遍历非线性结构了。

例如，set 的实现是红黑树，我们是没法用下标来访问元素的。但是通过迭代器，我们就能遍历 set 中的元素了：

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

3.3 迭代器用法

对于 vector 容器，它的迭代器功能比较完整，以它举例：

• .begin()：头迭代器
• .end()：尾迭代器
• .rbegin()：反向头迭代器
• .rend()：反向尾迭代器
• 迭代器+整型：将迭代器向后移动
• 迭代器-整型：将迭代器向前移动
• 迭代器++：将迭代器向后移动 1 位
• 迭代器--：将迭代器向前移动 1 位
• 迭代器-迭代器：两个迭代器的距离
• prev(it)：返回 it 的前一个迭代器
• next(it)：返回 it 的后一个迭代器

对于其他容器，由于其结构特性，上面的功能不一定都有（例如 set 的迭代器是不能相减求距离的）

3.4 常见问题

.end()和.rend()指向的位置是无意义的值

对于一个长度为 10 的数组：for (int i = 0; i < 10; i++)，第 10 位是不可访问的

对于一个长度为 10 的容器：for (auto it = a.begin(); it != a.end(); ++it)，.end 是不可访问的

不同容器的迭代器功能可能不一样

迭代器细化的话有正向、反向、双向，每个容器的迭代器支持的运算符也可能不同，因此不同容器的迭代器细节很有可能是不一样的。

删除操作时需要警惕

为什么 3 没删掉？

vector<int> a{1, 2, 3, 4}; for (auto it = a.begin(); it != a.end(); ++it) if (*it == 2 || *it == 3) a.erase(it); // a = [1, 3, 4]

为啥 RE 了？

vector<int> a{1, 2, 3, 4}; for (auto it = a.begin(); it != a.end(); ++it) if (*it == 4) a.erase(it);

建议：如无必要，别用迭代器操作容器。（遍历与访问没关系）

4 常用算法

4.1 内容总览

打勾的是本次将会详细讲解的，其他的是算法竞赛中建议学习的，不在下表列出的在比赛中基本用不到。

（很多函数的功能很简单，自己都能快速写出来，但是使用函数可以让代码可读性变得更高，这在比赛中是至关紧要的）

• 算法库 Algorithm

  • [ ]count()
  • [ ]find()
  • [ ]fill()
  • [x] swap()
  • [x] reverse()
  • [ ]shuffle()C++11
  • [x] unique()
  • [x] sort()
  • [x] lower_bound() / upper_bound()
  • [x] max() / min()
  • [ ]max_element()/min_element()
  • [ ]prev_permutation()/next_permutation()

• 数学函数 cmath

  • [x] abs()
  • [x] exp()
  • [x] log() /log10()/log2()
  • [x] pow()
  • [x] sqrt()
  • [ ]sin()/cos()/tan()
  • [ ]asin()/acos()/atan()
  • [ ]sinh()/cosh()/tanh()
  • [ ]asinh()/acosh()/atanh()C++11
  • [x] ceil() / floor()
  • [x] round() C++11

• 数值算法 numeric

  • [ ]iota()C++11
  • [ ]accumulate()
  • [x] gcd() C++17
  • [x] lcm() C++17

• 伪随机数生成 random

  • [ ]mt19937
  • [ ]random_device()

4.2swap()

交换两个变量的值

用法示例

template< class T > void swap( T& a, T& b );

int a = 0, b = 1; swap(a, b); // now a = 1, b = 0 int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; swap(arr[4], arr[6]); // now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}

注意事项

这个 swap 参数是引用的，不需要像 C 语言一样取地址。

4.3sort()

使用快速排序给一个可迭代对象排序

默认排序从小到大

vector<int> arr{1, 9, 1, 9, 8, 1, 0}; sort(arr.begin(), arr.end()); // arr = [0, 1, 1, 1, 8, 9, 9]

如果要从大到小，则需要传比较器进去。

vector<int> arr{1, 9, 1, 9, 8, 1, 0}; sort(arr.begin(), arr.end(), greater<int>()); // arr = [9, 9, 8, 1, 1, 1, 0]

如果需要完成特殊比较，则需要手写比较器。

比较器函数返回值是 bool 类型，传参是需要比较的两个元素。记我们定义的该比较操作为 ：

• 若 ，则比较器函数应当返回true
• 若 ，则比较器函数应当返回false

**注意：**如果 ，比较器函数必须返回false

bool cmp(pair<int, int> a, pair<int, int> b) { if (a.second != b.second) return a.second < b.second; return a.first > b.first; } int main() { vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}}; sort(arr.begin(), arr.end(), cmp); // arr = [(0, 0), (8, 1), (2, 9), (1, 9)] }

4.4lower_bound()/upper_bound()

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。

• lower_bound(): 寻找 大于等于x的第一个元素的位置
• upper_bound(): 寻找 大于x的第一个元素的位置

怎么找 / 的第一个元素呢？

• 大于x的第一个元素的前一个元素（如果有）便是小于等于x的第一个元素
• 大于等于x的第一个元素的前一个元素（如果有）便是 小于x的第一个元素

返回的是迭代器，如何转成下标索引呢？减去头迭代器即可。

用法示例

template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

vector<int> arr{0, 1, 1, 1, 8, 9, 9}; vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7); int idx = it - arr.begin(); // idx = 4

我们通常写成一行：

vector<int> arr{0, 1, 1, 1, 8, 9, 9}; idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4 idx = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4 idx = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4 idx = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5

4.5reverse()

反转一个可迭代对象的元素顺序

用法示例

template< class BidirIt > void reverse( BidirIt first, BidirIt last );

vector<int> arr(10); iota(arr.begin(), arr.end(), 1); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 reverse(arr.begin(), arr.end()); // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

4.6max()/min()

返回最大值 / 最小值的数值

用法示例

int mx = max(1, 2); // 2 int mn = min(1, 2); // 1

在 C++11 之后，可以使用列表构造语法传入一个列表，这样就能一次性给多个元素找最大值而不用套娃了：

// Before C++11 int mx = max(max(1, 2), max(3, 4)); // 4 int mn = min(min(1, 2), min(3, 4)); // 1 // After C++11 int mx = max({1, 2, 3, 4}); // 4 int mn = min({1, 2, 3, 4}); // 1

4.7unique()

消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的结尾迭代器。

例如：，下划线位置为返回的迭代器指向。

template< class ForwardIt > ForwardIt unique( ForwardIt first, ForwardIt last );

用法示例

单独使用 unique 并不能达成去重效果，因为它只消除相邻的重复元素。但是如果序列有序，那么它就能去重了。

但是它去重后，序列尾部会产生一些无效数据：，为了删掉这些无效数据，我们需要结合 erase.

最终，给 vector 去重的写法便是：

vector<int> arr{1, 2, 1, 4, 5, 4, 4}; sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end());

4.8 数学函数

所有函数参数均支持int/long long/float/double/long double

注意事项

由于浮点误差，有些的数学函数的行为可能与预期不符，导致 WA。如果你的操作数都是整型，那么用下面的写法会更稳妥。

原文地址：https://codeforces.com/blog/entry/107717

• • 别用：floor(1.0 * a / b)
  • 要用：a / b
• • 别用：ceil(1.0 * a / b)
  • 要用：(a + b - 1) / b（）
• • 别用：(int) sqrt(a)
  • 要用：二分查找 https://io.zouht.com/7.html
• • 别用：pow(a, b)
  • 要用：快速幂 https://io.zouht.com/18.html
• • 别用：log2(a)
  • 要用：__lg（不规范，但是这是竞赛）/bit_width（C++20 可用）

4.9gcd()/lcm()

（C++17）返回最大公因数 / 最小公倍数

int x = gcd(8, 12); // 4 int y = lcm(8, 12); // 24

如果不是 C17，但是是 GNU 编译器（g），那么可以用内置函数__gcd().

当然，gcd/lcm函数也挺好写，直接写也行（欧几里得算法）：

int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a, b) * b; }