Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"Exile_code","updateTime":1706694248000,"title":"算法竞赛stl语法详解","dislikeCnt":0,"content":"转载自[@ChrisKim_ZHT](https://space.bilibili.com/23986264)\n[原文链接](https://run.sh.cn/stlmd)\n[视频](https://www.bilibili.com/video/BV1L8411y7th/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n**C++ 标准模板库 (STL, Standard Template Library)**:包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).\n\n\u003c!--more--\u003e\n\n示例:\n\n- 算法:`sort(a.begin(), a.end())`\n- 容器:`priority_queue\u003cint\u003e pque`\n- 仿函数:`greater\u003cint\u003e()`\n- 迭代器:`vector\u003cint\u003e::iterator it \u003d a.begin()`\n\n\n\n# 1 前言\n\nSTL 作为一个封装良好,性能合格的 C++ 标准库,在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间,这一点不仅是由于可以直接调用,还是因为它封装良好,可以让代码的可读性变高,解题思路更清晰,调试过程 ~~往往~~ 更顺利。\n\n不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能,它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此,STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此,在实际比赛中要权衡 STL 的利弊,不过这一点就得靠经验了。\n\n接下来,我会分享在算法竞赛中常用的 STL 容器和算法,对于函数和迭代器,就不着重展开讲了。\n\n\n\n# 2 常用容器\n\n## 2.1 内容总览\n\n打勾的是本次将会详细讲解的,加粗的是算法竞赛中有必要学习的。\n\n- 顺序容器\n\n - [ ] **array**\n\n - [x] **vector**\n - [ ] **deque**\n - [ ] forward_list\n - [ ] **list**\n- 关联容器\n\n - [x] **set**\n - [x] **map**\n - [ ] **multiset**\n - [ ] **multimap**\n- 无序关联容器\n\n - [ ] **unordered_set**\n - [ ] **unordered_map**\n - [ ] **unordered_multiset**\n - [ ] **unordered_multimap**\n- 容器适配器\n\n - [x] **stack**\n - [x] **queue**\n - [x] **priority_queue**\n - [ ] flat_set\n - [ ] flat_map\n - [ ] flat_multiset\n - [ ] flat_multimap\n- 字符串\n - [x] **string** (basic_string\\\u003cchar\\\u003e)\n\n- 对与元组\n - [x] **pair**\n - [ ] **tuple**\n\n\n\n\n## 2.2 向量 [vector](https://zh.cppreference.com/w/cpp/container/vector)\n\n**`#include \u003cvector\u003e`**\n\n连续的顺序的储存结构(和数组一样的类别),但是有长度可变的特性。\n\n### 2.2.1 常用方法\n\n#### 构造\n\n**`vector\u003c类型\u003e arr(长度, [初值])`**\n\n时间复杂度:$O(n)$\n\n常用的一维和二维数组构造示例,高维也是一样的(就是会有点长).\n\n```cpp\nvector\u003cint\u003e arr; // 构造int数组\nvector\u003cint\u003e arr(100); // 构造初始长100的int数组\nvector\u003cint\u003e arr(100, 1); // 构造初始长100的int数组,初值为1\n\nvector\u003cvector\u003cint\u003e\u003e mat(100, vector\u003cint\u003e ()); // 构造初始100行,不指定列数的二维数组\nvector\u003cvector\u003cint\u003e\u003e mat(100, vector\u003cint\u003e (666, -1)) // 构造初始100行,初始666列的二维数组,初值为-1\n```\n\n构造二维数组的奇葩写法,千万别用:\n\n```cpp\nvector\u003cint\u003e arr[100]; // 正确,构造初始100行,不指定列数的二维数组,可用于链式前向星存图\nvector\u003cint\u003e arr[100](100, 1); // 语法错误!\nvector\u003cint\u003e arr(100, 1)[100]; // 语法错误!\nvector\u003cint\u003e arr[100] {{100, 1}, 这里省略98个 ,{100, 1}}; // 正确但奇葩,使用列表初始化\n```\n\n#### 尾接 \u0026 尾删\n\n- **`.push_back(元素)`**:在 vector 尾接一个元素,数组长度 $+1$.\n- **`.pop_back()`**:删除 vector 尾部的一个元素,数组长度 $-1$\n\n时间复杂度:均摊 $O(1)$\n\n```cpp\n// init: arr \u003d []\narr.push_back(1);\n// after: arr \u003d [1]\narr.push_back(2);\n// after: arr \u003d [1, 2]\narr.pop_back();\n// after: arr \u003d [1]\narr.pop_back();\n// after: arr \u003d []\n```\n\n#### 中括号运算符\n\n和一般数组一样的作用\n\n时间复杂度:$O(1)$\n\n#### 获取长度\n\n**`.size()`**\n\n获取当前 vector 的长度\n\n时间复杂度:$O(1)$\n\n```cpp\nfor (int i \u003d 0; i \u003c arr.size(); i++)\n cout \u003c\u003c a[i] \u003c\u003c endl;\n```\n\n#### 清空\n\n**`.clear()`**\n\n清空 vector\n\n时间复杂度:$O(n)$\n\n#### 判空\n\n**`.empty()`**\n\n如果是空返回 `true` 反之返回 `false`.\n\n时间复杂度:$O(1)$\n\n#### 改变长度\n\n**`.resize(新长度, [默认值])`**\n\n修改 vector 的长度\n\n- 如果是缩短,则删除多余的值\n- 如果是扩大,且指定了默认值,则新元素均为默认值**(旧元素不变)**\n\n时间复杂度:$O(n)$\n\n### 2.2.2 适用情形\n\n一般情况 `vector` 可以替换掉普通数组,除非该题卡常。\n\n有些情况普通数组没法解决:$n\\times m$ 的矩阵,$1\\leq n,m\\leq 10^6$ 且 $n\\times m \\leq 10^6$\n\n- 如果用普通数组 `int mat[1000010][1000010]`,浪费内存,会导致 MLE。\n- 如果使用 `vector\u003cvector\u003cint\u003e\u003e mat(n + 10, vector\u003cint\u003e (m + 10))`,完美解决该问题。\n\n另外,`vector` 的数据储存在堆空间中,不会爆栈。\n\n### 2.2.3 注意事项\n\n#### 提前指定长度\n\n如果长度已经确定,那么应当直接在构造函数指定长度,而不是一个一个 `.push_back()`. 因为 `vector` 额外内存耗尽后的重分配是有时间开销的,直接指定长度就不会出现重分配了。\n\n```cpp\n// 优化前: 522ms\nvector\u003cint\u003e a;\nfor (int i \u003d 0; i \u003c 1e8; i++)\n a.push_back(i);\n// 优化后: 259ms\nvector\u003cint\u003e a(1e8);\nfor (int i \u003d 0; i \u003c a.size(); i++)\n a[i] \u003d i;\n```\n\n#### 当心 size_t 溢出\n\nvector 获取长度的方法 `.size()` 返回值类型为 `size_t`,通常 OJ 平台使用的是 32 位编译器(有些平台例如 cf 可选 64 位),那么该类型范围为 $[0,2^{32})$.\n\n```cpp\nvector\u003cint\u003e a(65536);\nlong long a \u003d a.size() * a.size(); // 直接溢出变成0了\n```\n\n## 2.3 栈 [stack](https://zh.cppreference.com/w/cpp/container/stack)\n\n**`#include \u003cstack\u003e`**\n\n通过二次封装双端队列 (deque) 容器,实现先进后出的栈数据结构。\n\n### 2.3.1 常用方法\n\n| 作用 | 用法 | 示例 |\n| ---------------------- | ----------------- | -------------------- |\n| 构造 | `stack\u003c类型\u003e stk` | `stack\u003cint\u003e stk;` |\n| 进栈 | `.push(元素)` | `stk.push(1);` |\n| 出栈 | `.pop()` | `stk.pop();` |\n| 取栈顶 | `.top()` | `int a \u003d stk.top();` |\n| 查看大小 / 清空 / 判空 | 略 | 略 |\n\n### 2.3.2 适用情形\n\n如果不卡常的话,就可以直接用它而不需要手写栈了。\n\n另外,vector 也可以当栈用,vector 的 `.back()` 取尾部元素,就相当于取栈顶,`.push_back()` 相当于进栈,`.pop_back()` 相当于出栈。\n\n### 2.3.3 注意事项\n\n不可访问内部元素!**下面都是错误用法**\n\n```cpp\nfor (int i \u003d 0; i \u003c stk.size(); i++)\n cout \u003c\u003c stk[i] \u003c\u003c endl;\nfor (auto ele : stk)\n cout \u003c\u003c stk \u003c\u003c endl;\n```\n\n## 2.4 队列 [queue](https://zh.cppreference.com/w/cpp/container/queue)\n\n**`#include \u003cqueue\u003e`**\n\n通过二次封装双端队列 (deque) 容器,实现先进先出的队列数据结构。\n\n### 2.4.1 常用方法\n\n| 作用 | 用法 | 示例 |\n| ---------------------- | ----------------- | ---------------------- |\n| 构造 | `queue\u003c类型\u003e que` | `queue\u003cint\u003e que;` |\n| 进队 | `.push(元素)` | `que.push(1);` |\n| 出队 | `.pop()` | `que.pop();` |\n| 取队首 | `.front()` | `int a \u003d que.front();` |\n| 取队尾 | `.back()` | `int a \u003d que.back();` |\n| 查看大小 / 清空 / 判空 | 略 | 略 |\n\n### 2.4.2 适用情形\n\n如果不卡常的话,就可以直接用它而不需要手写队列了。\n\n### 2.4.3 注意事项\n\n不可访问内部元素!**下面都是错误用法**\n\n```cpp\nfor (int i \u003d 0; i \u003c que.size(); i++)\n cout \u003c\u003c que[i] \u003c\u003c endl;\nfor (auto ele : que)\n cout \u003c\u003c ele \u003c\u003c endl;\n```\n\n## 2.5 优先队列 [priority_queue](https://zh.cppreference.com/w/cpp/container/priority_queue)\n\n**`#include \u003cqueue\u003e`**\n\n提供常数时间的最大元素查找,对数时间的插入与提取,底层原理是二叉堆。\n\n### 2.5.1 常用方法\n\n#### 构造\n\n**`priority_queue\u003c类型, 容器, 比较器\u003e pque`**\n\n- 类型:要储存的数据类型\n- 容器:储存数据的底层容器,默认为 `vector\u003c类型\u003e`,竞赛中保持默认即可\n- 比较器:比较大小使用的比较器,默认为 `less\u003c类型\u003e`,可自定义\n\n```cpp\npriority_queue\u003cint\u003e pque1; // 储存int的大顶堆\npriority_queue\u003cint, vector\u003cint\u003e, greater\u003cint\u003e\u003e pque2; // 储存int的小顶堆\n```\n\n\u003e 对于需要自定义比较器的情况,涉及一些初学时容易看迷糊的语法(重载小括号运算符 / lambda 表达式),在此就不展开讲了。如果想要了解,可以查阅 cppreference 中的代码示例。\n\n#### 其他\n\n| 作用 | 用法 | 示例 |\n| --------------- | ------------- | -------------------- |\n| 进堆 | `.push(元素)` | `que.push(1);` |\n| 出堆 | `.pop()` | `que.pop();` |\n| 取堆顶 | `.top()` | `int a \u003d que.top();` |\n| 查看大小 / 判空 | 略 | 略 |\n\n进出队复杂度 $O(\\log n)$,取堆顶 $O(1)$.\n\n### 2.5.2 适用情形\n\n持续维护元素的有序性:每次向队列插入大小不定的元素,或者每次从队列里取出大小最小/最大的元素,元素数量 $n$,插入操作数量 $k$.\n\n- 每次插入后进行快速排序:$k\\cdot n\\log n$\n- 使用优先队列维护:$k\\cdot\\log n$\n\n### 2.5.3 注意事项\n\n#### 仅堆顶可读\n\n只可访问堆顶,其他元素都无法读取到。**下面是错误用法:**\n\n```cpp\ncout \u003c\u003c pque[1] \u003c\u003c endl;\n```\n\n#### 所有元素不可写\n\n堆中所有元素是不可修改的。**下面是错误用法:**\n\n```cpp\npque[1] \u003d 2;\npque.top() \u003d 1;\n```\n\n如果你恰好要修改的是堆顶元素,那么是可以完成的:\n\n```cpp\nint tp \u003d pque.top();\npque.pop();\npque.push(tp + 1);\n```\n\n## 2.6 集合 [set](https://zh.cppreference.com/w/cpp/container/set)\n\n**`#include \u003cset\u003e`**\n\n提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。\n\n| 集合三要素 | 解释 | set | multiset | unordered_set |\n| ---------- | ------------------------------ | ------------- | ------------- | ------------- |\n| 确定性 | 一个元素要么在集合中,要么不在 | ✔ | ✔ | ✔ |\n| 互异性 | 一个元素仅可以在集合中出现一次 | ✔ | ❌(任意次) | ✔ |\n| 无序性 | 集合中的元素是没有顺序的 | ❌(从小到大) | ❌(从小到大) | ✔ |\n\n### 2.6.1 常用方法\n\n#### 构造\n\n**`set\u003c类型, 比较器\u003e st`**\n\n- 类型:要储存的数据类型\n- 比较器:比较大小使用的比较器,默认为 `less\u003c类型\u003e`,可自定义\n\n```cpp\nset\u003cint\u003e st1; // 储存int的集合(从小到大)\nset\u003cint, greater\u003cint\u003e\u003e st2; // 储存int的集合(从大到小)\n```\n\n\u003e 对于需要自定义比较器的情况,涉及一些初学时容易看迷糊的语法(重载小括号运算符 / lambda 表达式),在此就不展开讲了。\n\n#### 遍历\n\n可使用迭代器进行遍历:\n\n```cpp\nfor (set\u003cint\u003e::iterator it \u003d st.begin(); it !\u003d st.end(); ++it)\n cout \u003c\u003c *it \u003c\u003c endl;\n```\n\n基于范围的循环(C++ 11):\n\n```cpp\nfor (auto \u0026ele : st)\n cout \u003c\u003c ele \u003c\u003c endl;\n```\n\n#### 其他\n\n| 作用 | 用法 | 示例 |\n| ---------------------- | --------------- | ----------------------- |\n| 插入元素 | `.insert(元素)` | `st.insert(1);` |\n| 删除元素 | `.erase(元素)` | `st.erase(2);` |\n| 查找元素 | `.find(元素)` | `auto it \u003d st.find(1);` |\n| 判断元素是否存在 | `.count(元素)` | `st.count(3);` |\n| 查看大小 / 清空 / 判空 | 略 | 略 |\n\n增删查时间复杂度均为 $O(\\log n)$\n\n### 2.6.2 适用情形\n\n- 元素去重:$[1,1,3,2,4,4]\\to[1,2,3,4]$\n- 维护顺序:$[1,5,3,7,9]\\to[1,3,5,7,9]$\n- 元素是否出现过:元素大小 $[-10^{18},10^{18}]$,元素数量 $10^6$,vis 数组无法实现,通过 set 可以完成。\n\n### 2.6.3 注意事项\n\n#### 不存在下标索引\n\nset 虽说可遍历,但仅可使用迭代器进行遍历,它不存在下标这一概念,无法通过下标访问到数据。**下面是错误用法:**\n\n```cpp\ncout \u003c\u003c st[0] \u003c\u003c endl;\n```\n\n#### 元素只读\n\nset 的迭代器取到的元素是只读的(因为是 const 迭代器),不可修改其值。如果要改,需要先 erase 再 insert. **下面是错误用法:**\n\n```cpp\ncout \u003c\u003c *st.begin() \u003c\u003c endl; // 正确。可读。\n*st.begin() \u003d 1; // 错误!不可写!\n```\n\n#### 不可用迭代器计算下标\n\nset 的迭代器不能像 vector 一样相减得到下标。**下面是错误用法:**\n\n```cpp\nauto it \u003d st.find(2); // 正确,返回2所在位置的迭代器。\nint idx \u003d it - st.begin(); // 错误!不可相减得到下标。\n```\n\n## 2.7 映射 [map](https://zh.cppreference.com/w/cpp/container/map)\n\n**`#include \u003cmap\u003e`**\n\n提供对数时间的有序键值对结构。底层原理是红黑树。\n\n映射:\n$$\n\\begin{matrix}\n1\u0026\\to\u00262\\\\\n2\u0026\\to\u00262\\\\\n3\u0026\\to\u00261\\\\\n4\u0026\\to\u00265\\\\\n\u0026\\vdots\n\\end{matrix}\n$$\n\n| 性质 | 解释 | map | multimap | unordered_map |\n| ------ | ---------------------------- | ------------- | ------------- | ------------- |\n| 互异性 | 一个键仅可以在映射中出现一次 | ✔ | ❌(任意次) | ✔ |\n| 无序性 | 键是没有顺序的 | ❌(从小到大) | ❌(从小到大) | ✔ |\n\n### 2.7.1 常用方法\n\n#### 构造\n\n**`map\u003c键类型, 值类型, 比较器\u003e mp`**\n\n- 键类型:要储存键的数据类型\n- 值类型:要储存值的数据类型\n- 比较器:键比较大小使用的比较器,默认为 `less\u003c类型\u003e`,可自定义\n\n```cpp\nmap\u003cint, int\u003e mp1; // int-\u003eint 的映射(键从小到大)\nmap\u003cint, int, greater\u003cint\u003e\u003e st2; // int-\u003eint 的映射(键从大到小)\n```\n\n\u003e 对于需要自定义比较器的情况,涉及一些初学时容易看迷糊的语法(重载小括号运算符 / lambda 表达式),在此就不展开讲了。\n\n#### 遍历\n\n可使用迭代器进行遍历:\n\n```cpp\nfor (map\u003cint, int\u003e::iterator it \u003d mp.begin(); it !\u003d mp.end(); ++it)\n cout \u003c\u003c it-\u003efirst \u003c\u003c \u0027 \u0027 \u003c\u003c it-\u003esecond \u003c\u003c endl;\n```\n\n基于范围的循环(C++ 11):\n\n```cpp\nfor (auto \u0026pr : mp)\n cout \u003c\u003c pr.first \u003c\u003c \u0027 \u0027 \u003c\u003c pr.second \u003c\u003c endl;\n```\n\n结构化绑定 + 基于范围的循环(C++17):\n\n```cpp\nfor (auto \u0026[key, val] : mp)\n cout \u003c\u003c key \u003c\u003c \u0027 \u0027 \u003c\u003c val \u003c\u003c endl;\n```\n\n#### 其他\n\n| 作用 | 用法 | 示例 |\n| ---------------------- | -------------- | ----------------------- |\n| 增 / 改 / 查元素 | 中括号 | `mp[1] \u003d 2;` |\n| 查元素(返回迭代器) | `.find(元素)` | `auto it \u003d mp.find(1);` |\n| 删除元素 | `.erase(元素)` | `mp.erase(2);` |\n| 判断元素是否存在 | `.count(元素)` | `mp.count(3);` |\n| 查看大小 / 清空 / 判空 | 略 | 略 |\n\n增删改查时间复杂度均为 $O(\\log n)$\n\n### 2.7.2 适用情形\n\n需要维护映射的场景可以使用:输入若干字符串,统计每种字符串的出现次数。(`map\u003cstring, int\u003e mp`)\n\n### 2.7.3 注意事项\n\n#### 中括号访问时默认值\n\n如果使用中括号访问 map 时对应的键不存在,那么会新增这个键,并且值为默认值,因此中括号会影响键的存在性。\n\n```cpp\nmap\u003cchar, int\u003e mp;\ncout \u003c\u003c mp.count(\u0027a\u0027) \u003c\u003c endl; // 0\nmp[\u0027a\u0027]; // 即使什么都没做,此时mp[\u0027a\u0027]\u003d0已经插入了\ncout \u003c\u003c mp.count(\u0027a\u0027) \u003c\u003c endl; // 1\ncout \u003c\u003c mp[\u0027a\u0027] \u003c\u003c endl; // 0\n```\n\n#### 不可用迭代器计算下标\n\nmap 的迭代器不能像 vector 一样相减得到下标。**下面是错误用法:**\n\n```cpp\nauto it \u003d mp.find(\u0027a\u0027); // 正确,返回2所在位置的迭代器。\nint idx \u003d it - mp.begin(); // 错误!不可相减得到下标。\n```\n\n## 2.8 字符串 [string](https://zh.cppreference.com/w/cpp/string)\n\n**`#include \u003cstring\u003e`**\n\n顾名思义,就是储存字符串的。\n\n### 2.8.1 常用方法\n\n#### 构造\n\n构造函数:`string(长度, 初值)`\n\n```cpp\nstring s1; // 构造字符串,为空\nstring s2 \u003d \"awa!\"; // 构造字符串,并赋值awa!\nstring s3(10, \u00276\u0027); // 构造字符串,通过构造函数构造为6666666666\n```\n\n#### 输入输出\n\nC++\n\n```cpp\nstring s;\ncin \u003e\u003e s;\ncout \u003c\u003c s;\n```\n\nC\n\n```cpp\nstring s;\nchar buf[100];\nscanf(\"%s\", \u0026buf);\ns \u003d buf;\nprintf(\"%s\", s.c_str());\n```\n\n#### 其他\n\n| 作用 | 用法 | 示例 |\n| ---------------------- | ----------------------------- | ------------------------------- |\n| 修改、查询指定下标字符 | `[]` | `s[1] \u003d \u0027a\u0027;` |\n| 是否相同 | `\u003d\u003d` | `if (s1 \u003d\u003d s2) ...` |\n| 字符串连接 | `+` | `string s \u003d s1 + s2;` |\n| 尾接字符串 | `+\u003d` | `s +\u003d \"awa\";` |\n| 取子串 | `.substr(起始下标, 子串长度)` | `string sub \u003d s.substr(2, 10);` |\n| 查找字符串 | `.find(字符串, 起始下标)` | `int pos \u003d s.find(\"awa\");` |\n\n#### 数值与字符串互转(C++11)\n\n| 源 | 目的 | 函数 |\n| ---------------------------------------------- | ----------- | ----------- |\n| int / long long / float / double / long double | string | to_string() |\n| string | int | stoi() |\n| string | long long | stoll() |\n| string | float | stof() |\n| string | double | stod() |\n| string | long double | stold() |\n\n### 2.8.2 适用情形\n\n非常好用!~~建议直接把字符数组扔了,赶快投入 string 的怀抱。~~\n\n### 2.8.3 注意事项\n\n#### 尾接字符串一定要用 `+\u003d`\n\nstring 的 +\u003d 运算符,将会在原字符串原地尾接字符串。而 + 了再 \u003d 赋值,会先生成一个临时变量,在复制给 string.\n\n通常字符串长度可以很长,如果使用 + 字符串很容易就 TLE 了。\n\n```cpp\n// 优化前: 15139ms\nstring s;\nfor (int i \u003d 0; i \u003c 5e5; i++)\n s \u003d s + \"a\";\n\n// 优化后: \u003c 1ms (计时器显示0)\nstring s;\nfor (int i \u003d 0; i \u003c 5e5; i++)\n s +\u003d \"a\";\n```\n\n#### `.substr()` 方法的奇葩参数\n\n一定要注意,C++ string 的取子串的第一个参数是**子串起点下标**,第二个参数是**子串长度**。\n\n第二个参数不是子串终点!不是子串终点!要与 java 等其他语言区分开来。\n\n#### `.find()` 方法的复杂度\n\n该方法实现为暴力实现,时间复杂度为 $O(n^2)$.\n\n~~不要幻想 STL 内置了个 $O(n)$ 的 KMP 算法~~\n\n## 2.9 二元组 [pair](https://zh.cppreference.com/w/cpp/utility/pair)\n\n**`#include \u003cutility\u003e`**\n\n顾名思义,就是储存二元组的。\n\n### 2.9.1 常用方法\n\n#### 构造\n\n**`pair\u003c第一个值类型, 第二个值类型\u003e pr`**\n\n- 第一个值类型:要储存的第一个值的数据类型\n- 第二个值类型:要储存的第二个值的数据类型\n\n```cpp\npair\u003cint, int\u003e p1;\npair\u003cint, long long\u003e p2;\npair\u003cchar, int\u003e p3;\n// ...\n```\n\n#### 赋值\n\n老式\n\n```cpp\npair\u003cint, char\u003e pr \u003d make_pair(1, \u0027a\u0027);\n```\n\n列表构造 C++11\n\n```cpp\npair\u003cint, char\u003e pr \u003d {1, \u0027a\u0027};\n```\n\n#### 取值\n\n直接取值\n\n- 取第一个值:`.first`\n- 取第二个值:`.second`\n\n```cpp\npair\u003cint, char\u003e pr \u003d {1, \u0027a\u0027};\nint awa \u003d pr.first;\nchar bwb \u003d pr.second;\n```\n\n结构化绑定 C++17\n\n```cpp\npair\u003cint, char\u003e pr \u003d {1, \u0027a\u0027};\nauto \u0026[awa, bwb] \u003d pr;\n```\n\n#### 判同\n\n直接用 `\u003d\u003d` 运算符\n\n```cpp\npair\u003cint, int\u003e p1 \u003d {1, 2};\npair\u003cint, int\u003e p2 \u003d {1, 3};\nif (p1 \u003d\u003d p2) { ... } // false\n```\n\n### 2.9.2 适用场景\n\n所有需要二元组的场景均可使用,效率和自己定义结构体差不多。\n\n### 2.9.3 注意事项\n\n无\n\n\n\n# 3 迭代器简介\n\n## 3.1 迭代器是什么?\n\n不搞抽象,直接举例。\n\n对于一个 vector,我们可以用下标遍历:\n\n```cpp\nfor (int i \u003d 0; i \u003c a.size(); i++)\n cout \u003c\u003c a[i] \u003c\u003c endl;\n```\n\n我们同时也可以用迭代器来遍历:\n\n```cpp\nfor (vector\u003cint\u003e::iterator it \u003d a.begin(); it !\u003d a.end(); ++it)\n cout \u003c\u003c *it \u003c\u003c endl;\n```\n\n- `a.begin()` 是一个迭代器,指向的是第一个元素\n- `a.end()` 是一个迭代器,指向的是最后一个元素**再后面一位**\n- 上述迭代器具有自增运算符,自增则迭代器向下一个元素移动\n- 迭代器与指针相似,如果对它使用解引用运算符,即 `*it`,就能取到对应值了\n\n## 3.2 为何需要迭代器?\n\n很多数据结构并不是线性的(例如红黑树),对于非线性数据结构,下标是无意义的。无法使用下标来遍历整个数据结构。\n\n迭代器的作用就是定义某个数据结构的遍历方式,通过迭代器的增减,代表遍历到的位置,通过迭代器便能成功遍历非线性结构了。\n\n例如,set 的实现是红黑树,我们是没法用下标来访问元素的。但是通过迭代器,我们就能遍历 set 中的元素了:\n\n```cpp\nfor (set\u003cint\u003e::iterator it \u003d st.begin(); it !\u003d st.end(); ++it)\n cout \u003c\u003c *it \u003c\u003c endl;\n```\n\n## 3.3 迭代器用法\n\n对于 vector 容器,它的迭代器功能比较完整,以它举例:\n\n- `.begin()`:头迭代器\n- `.end()`:尾迭代器\n- `.rbegin()`:反向头迭代器\n- `.rend()`:反向尾迭代器\n- 迭代器 `+` 整型:将迭代器向后移动\n- 迭代器 `-` 整型:将迭代器向前移动\n- 迭代器 `++`:将迭代器向后移动 1 位\n- 迭代器 `--`:将迭代器向前移动 1 位\n- 迭代器 `-` 迭代器:两个迭代器的距离\n- `prev(it)`:返回 it 的前一个迭代器\n- `next(it)`:返回 it 的后一个迭代器\n\n对于其他容器,由于其结构特性,上面的功能不一定都有(例如 set 的迭代器是不能相减求距离的)\n\n## 3.4 常见问题\n\n**`.end()` 和 `.rend()` 指向的位置是无意义的值**\n\n对于一个长度为 10 的数组:`for (int i \u003d 0; i \u003c 10; i++)`,第 10 位是不可访问的\n\n对于一个长度为 10 的容器:`for (auto it \u003d a.begin(); it !\u003d a.end(); ++it)`,.end 是不可访问的\n\n**不同容器的迭代器功能可能不一样**\n\n迭代器细化的话有正向、反向、双向,每个容器的迭代器支持的运算符也可能不同,因此不同容器的迭代器细节很有可能是不一样的。\n\n**删除操作时需要警惕**\n\n为什么 3 没删掉?\n\n```cpp\nvector\u003cint\u003e a{1, 2, 3, 4};\nfor (auto it \u003d a.begin(); it !\u003d a.end(); ++it)\n if (*it \u003d\u003d 2 || *it \u003d\u003d 3)\n a.erase(it);\n// a \u003d [1, 3, 4]\n```\n\n为啥 RE 了?\n\n```cpp\nvector\u003cint\u003e a{1, 2, 3, 4};\nfor (auto it \u003d a.begin(); it !\u003d a.end(); ++it)\n if (*it \u003d\u003d 4)\n a.erase(it);\n```\n\n\u003ccenter\u003e\u003cb\u003e建议:如无必要,别用迭代器操作容器。(遍历与访问没关系)\u003c/b\u003e\u003c/center\u003e\n\n\n\n# 4 常用算法\n\n## 4.1 内容总览\n\n打勾的是本次将会详细讲解的,其他的是算法竞赛中建议学习的,不在下表列出的在比赛中基本用不到。\n\n(很多函数的功能很简单,自己都能快速写出来,但是使用函数可以让代码可读性变得更高,这在比赛中是至关紧要的)\n\n- 算法库 Algorithm\n\n - [ ] `count()`\n - [ ] `find()`\n - [ ] `fill()`\n - [x] [`swap()`](https://zh.cppreference.com/w/cpp/algorithm/swap)\n - [x] [`reverse()`](https://zh.cppreference.com/w/cpp/algorithm/reverse)\n - [ ] `shuffle()` C++11\n - [x] [`unique()`](https://zh.cppreference.com/w/cpp/algorithm/unique)\n - [x] [`sort()`](https://zh.cppreference.com/w/cpp/algorithm/sort)\n - [x] [`lower_bound()`](https://zh.cppreference.com/w/cpp/algorithm/lower_bound) / [`upper_bound()`](https://zh.cppreference.com/w/cpp/algorithm/upper_bound)\n - [x] [`max()`](https://zh.cppreference.com/w/cpp/algorithm/max) / [`min()`](https://zh.cppreference.com/w/cpp/algorithm/min)\n - [ ] `max_element()` / `min_element()`\n - [ ] `prev_permutation()` / `next_permutation()`\n- 数学函数 cmath\n - [x] [`abs()`](https://zh.cppreference.com/w/cpp/numeric/math/fabs)\n - [x] [`exp()`](https://zh.cppreference.com/w/cpp/numeric/math/exp)\n - [x] [`log()`](https://zh.cppreference.com/w/cpp/numeric/math/log) / `log10()` / `log2()`\n - [x] [`pow()`](https://zh.cppreference.com/w/cpp/numeric/math/pow)\n - [x] [`sqrt()`](https://zh.cppreference.com/w/cpp/numeric/math/sqrt)\n - [ ] `sin()` / `cos()` / `tan()`\n - [ ] `asin()` / `acos()` / `atan()`\n - [ ] `sinh()` / `cosh()` / `tanh()`\n - [ ] `asinh()` / `acosh()` / `atanh()` C++11\n - [x] [`ceil()`](https://zh.cppreference.com/w/cpp/numeric/math/ceil) / [`floor()`](https://zh.cppreference.com/w/cpp/numeric/math/floor)\n - [x] [`round()`](https://zh.cppreference.com/w/cpp/numeric/math/round) C++11\n- 数值算法 numeric\n - [ ] `iota()` C++11\n - [ ] `accumulate()`\n - [x] [`gcd()`](https://zh.cppreference.com/w/cpp/numeric/gcd) C++17\n - [x] [`lcm()`](https://zh.cppreference.com/w/cpp/numeric/lcm) C++17\n- 伪随机数生成 random\n - [ ] `mt19937`\n - [ ] `random_device()`\n\n## 4.2 `swap()`\n\n交换两个变量的值\n\n**用法示例**\n\n```cpp\ntemplate\u003c class T \u003e\nvoid swap( T\u0026 a, T\u0026 b );\n```\n\n```cpp\nint a \u003d 0, b \u003d 1;\nswap(a, b);\n// now a \u003d 1, b \u003d 0\n\nint arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};\nswap(arr[4], arr[6]);\n// now arr \u003d {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}\n```\n\n**注意事项**\n\n这个 swap 参数是引用的,不需要像 C 语言一样取地址。\n\n## 4.3 `sort()`\n\n使用快速排序给一个可迭代对象排序\n\n**用法示例**\n\n```cpp\ntemplate\u003c class RandomIt, class Compare \u003e\nvoid sort( RandomIt first, RandomIt last, Compare comp );\n```\n\n默认排序从小到大\n\n```cpp\nvector\u003cint\u003e arr{1, 9, 1, 9, 8, 1, 0};\nsort(arr.begin(), arr.end());\n// arr \u003d [0, 1, 1, 1, 8, 9, 9]\n```\n\n如果要从大到小,则需要传比较器进去。\n\n```cpp\nvector\u003cint\u003e arr{1, 9, 1, 9, 8, 1, 0};\nsort(arr.begin(), arr.end(), greater\u003cint\u003e());\n// arr \u003d [9, 9, 8, 1, 1, 1, 0]\n```\n\n如果需要完成特殊比较,则需要手写比较器。\n\n比较器函数返回值是 bool 类型,传参是需要比较的两个元素。记我们定义的该比较操作为 $\\star$:\n\n- 若 $a\\star b$,则比较器函数应当返回 `true`\n- 若 $a\\not\\star b$,则比较器函数应当返回 `false`\n\n**注意:**如果 $a\u003db$,比较器函数必须返回 `false`\n\n```cpp\nbool cmp(pair\u003cint, int\u003e a, pair\u003cint, int\u003e b)\n{\n if (a.second !\u003d b.second)\n return a.second \u003c b.second;\n return a.first \u003e b.first;\n}\n\nint main()\n{\n vector\u003cpair\u003cint, int\u003e\u003e arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};\n\tsort(arr.begin(), arr.end(), cmp);\n // arr \u003d [(0, 0), (8, 1), (2, 9), (1, 9)]\n}\n```\n\n## 4.4 `lower_bound()` / `upper_bound()`\n\n在**已升序排序**的元素中,应用二分查找检索指定元素,返回对应元素迭代器位置。**找不到则返回尾迭代器。**\n\n- `lower_bound()`: 寻找 $\\geq x$ 的第一个元素的位置\n- `upper_bound()`: 寻找 $\u003ex$ 的第一个元素的位置\n\n怎么找 $\\leq x$ / $\u003c x$ 的第一个元素呢?\n\n- $\u003ex$ 的第一个元素的前一个元素(如果有)便是 $\\leq x$ 的第一个元素\n- $\\geq x$ 的第一个元素的前一个元素(如果有)便是 $\u003cx$ 的第一个元素\n\n返回的是迭代器,如何转成下标索引呢?减去头迭代器即可。\n\n**用法示例**\n\n```cpp\ntemplate\u003c class ForwardIt, class T \u003e\nForwardIt lower_bound( ForwardIt first, ForwardIt last, const T\u0026 value );\n```\n\n```cpp\nvector\u003cint\u003e arr{0, 1, 1, 1, 8, 9, 9};\nvector\u003cint\u003e::iterator it \u003d lower_bound(arr.begin(), arr.end(), 7);\nint idx \u003d it - arr.begin();\n// idx \u003d 4\n```\n\n我们通常写成一行:\n\n```cpp\nvector\u003cint\u003e arr{0, 1, 1, 1, 8, 9, 9};\nidx \u003d lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4\nidx \u003d lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4\nidx \u003d upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4\nidx \u003d upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5\n```\n\n## 4.5 `reverse()`\n\n反转一个可迭代对象的元素顺序\n\n**用法示例**\n\n```cpp\ntemplate\u003c class BidirIt \u003e\nvoid reverse( BidirIt first, BidirIt last );\n```\n\n```cpp\nvector\u003cint\u003e arr(10);\niota(arr.begin(), arr.end(), 1);\n// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\nreverse(arr.begin(), arr.end());\n// 10, 9, 8, 7, 6, 5, 4, 3, 2, 1\n```\n\n## 4.6 `max()` / `min()`\n\n返回最大值 / 最小值的**数值**\n\n**用法示例**\n\n```cpp\nint mx \u003d max(1, 2); // 2\nint mn \u003d min(1, 2); // 1\n```\n\n在 C++11 之后,可以使用列表构造语法传入一个列表,这样就能一次性给多个元素找最大值而不用套娃了:\n\n```cpp\n// Before C++11\nint mx \u003d max(max(1, 2), max(3, 4)); // 4\nint mn \u003d min(min(1, 2), min(3, 4)); // 1\n\n// After C++11\nint mx \u003d max({1, 2, 3, 4}); // 4\nint mn \u003d min({1, 2, 3, 4}); // 1\n```\n\n## 4.7 `unique()`\n\n消除数组的重复**相邻**元素,数组长度不变,但是有效数据缩短,返回的是有效数据位置的结尾迭代器。\n\n例如:$[1,1,4,5,1,4]\\to[1,4,5,1,4,\\underline?]$,下划线位置为返回的迭代器指向。\n\n```cpp\ntemplate\u003c class ForwardIt \u003e\nForwardIt unique( ForwardIt first, ForwardIt last );\n```\n\n**用法示例**\n\n单独使用 unique 并不能达成去重效果,因为它只消除**相邻**的重复元素。但是如果序列有序,那么它就能去重了。\n\n但是它去重后,序列尾部会产生一些无效数据:$[1,1,2,4,4,4,5]\\to[1,2,4,5,\\underline?,?,?]$,为了删掉这些无效数据,我们需要结合 erase.\n\n最终,给 vector 去重的写法便是:\n\n```cpp\nvector\u003cint\u003e arr{1, 2, 1, 4, 5, 4, 4};\nsort(arr.begin(), arr.end());\narr.erase(unique(arr.begin(), arr.end()), arr.end());\n```\n\n## 4.8 数学函数\n\n所有函数参数均支持 `int` / `long long` / `float` / `double` / `long double`\n\n| 公式 | 示例 |\n| ----------------------- | ------------ |\n| $f(x)\u003d\\lvert x\\rvert$ | `abs(-1.0)` |\n| $f(x)\u003de^x$ | `exp(2)` |\n| $f(x)\u003d\\ln x$ | `log(3)` |\n| $f(x,y)\u003dx^y$ | `pow(2, 3)` |\n| $f(x)\u003d\\sqrt x$ | `sqrt(2)` |\n| $f(x)\u003d\\lceil x\\rceil$ | `ceil(2.1)` |\n| $f(x)\u003d\\lfloor x\\rfloor$ | `floor(2.1)` |\n| $f(x)\u003d\\left\u003cx\\right\u003e$ | `rount(2.1)` |\n\n**注意事项**\n\n由于浮点误差,有些的数学函数的行为可能与预期不符,导致 WA。如果你的操作数都是整型,那么用下面的写法会更稳妥。\n\n\u003e 原文地址:https://codeforces.com/blog/entry/107717\n\n- $\\lfloor\\frac{a}{b}\\rfloor$\n - 别用:`floor(1.0 * a / b)`\n - 要用:`a / b`\n- $\\lceil\\frac{a}{b}\\rceil$\n - 别用:`ceil(1.0 * a / b)`\n - 要用:`(a + b - 1) / b` ($\\lceil\\frac{a}{b}\\rceil\u003d\\lfloor\\frac{a+b-1}{b}\\rfloor$)\n- $\\lfloor\\sqrt a\\rfloor$\n - 别用:`(int) sqrt(a)`\n - 要用:二分查找 https://io.zouht.com/7.html\n- $a^b$\n - 别用:`pow(a, b)`\n - 要用:快速幂 https://io.zouht.com/18.html\n- $\\lfloor\\log_2 a\\rfloor$\n - 别用:`log2(a)`\n - 要用:`__lg` (不规范,但是这是竞赛)/ `bit_width`(C++20 可用)\n\n## 4.9 `gcd()` / `lcm()`\n\n(C++17)返回最大公因数 / 最小公倍数\n\n```cpp\nint x \u003d gcd(8, 12); // 4\nint y \u003d lcm(8, 12); // 24\n```\n\n如果不是 C++17,但是是 GNU 编译器(g++),那么可以用内置函数 `__gcd()`.\n\n当然,`gcd` / `lcm` 函数也挺好写,直接写也行(欧几里得算法):\n\n```cpp\nint gcd(int a, int b)\n{\n if (!b)\n return a;\n return gcd(b, a % b);\n}\n\nint lcm(int a, int b)\n{\n return a / gcd(a, b) * b;\n}\n```\n","threadId":181138,"likeCnt":4,"createTime":1706694248000,"isWorkbook":false,"viewCnt":370,"openness":2,"fav":false,"id":4534,"trustable":false}