C++ 标准模板库 (STL, Standard Template Library)
2.2.1 常用方法
构造
.
尾接 & 尾删
- ：在 vector 尾接一个元素，数组长度 .
- ：删除 vector 尾部的一个元素，数组长度
清空
清空 vector
判空
如果是空返回 反之返回 .
时间复杂度：
改变长度
修改 vector 的长度
- 如果是缩短，则删除多余的值
- 如果是扩大，且指定了默认值，则新元素均为默认值**（旧元素不变）**
时间复杂度：
2.2.2 适用情形
一般情况 可以替换掉普通数组，除非该题卡常。
有些情况普通数组没法解决： 的矩阵， 且
- 如果用普通数组 ，浪费内存，会导致 MLE。
- 如果使用 ，完美解决该问题。
另外， 的数据储存在堆空间中，不会爆栈。
2.2.3 注意事项
提前指定长度
如果长度已经确定，那么应当直接在构造函数指定长度，而不是一个一个 . 因为 额外内存耗尽后的重分配是有时间开销的，直接指定长度就不会出现重分配了。
当心 size_t 溢出
vector 获取长度的方法 返回值类型为 ，通常 OJ 平台使用的是 32 位编译器（有些平台例如 cf 可选 64 位），那么该类型范围为 .
通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。
2.3.1 常用方法
2.3.2 适用情形
如果不卡常的话，就可以直接用它而不需要手写栈了。
另外，vector 也可以当栈用，vector 的 取尾部元素，就相当于取栈顶， 相当于进栈， 相当于出栈。
2.3.3 注意事项
不可访问内部元素！(cout<<)
通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。
2.4.1 常用方法
2.4.2 适用情形
如果不卡常的话，就可以直接用它而不需要手写队列了。
2.4.3 注意事项
不可访问内部元素！
提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。
2.5.1 常用方法
构造
- 类型：要储存的数据类型
- 容器：储存数据的底层容器，默认为 ，竞赛中保持默认即可
- 比较器：比较大小使用的比较器，默认为 ，可自定义
其他
进出队复杂度 ，取堆顶 .
2.5.2 适用情形
持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列里取出大小最小/最大的元素，元素数量 ，插入操作数量 .
- 每次插入后进行快速排序：
- 使用优先队列维护：
2.5.3 注意事项
仅堆顶可读
只可访问堆顶，其他元素都无法读取到。下面是错误用法：
所有元素不可写
堆中所有元素是不可修改的。下面是错误用法：
如果你恰好要修改的是堆顶元素，那么是可以完成的：
提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。
2.6.1 常用方法
构造
- 类型：要储存的数据类型
- 比较器：比较大小使用的比较器，默认为 ，可自定义
遍历
可使用迭代器进行遍历：
基于范围的循环（C++ 11）：
其他
增删查时间复杂度均为
2.6.2 适用情形
- 元素去重：
- 维护顺序：
- 元素是否出现过：元素大小 ，元素数量 ，vis 数组无法实现，通过 set 可以完成。
2.6.3 注意事项
不存在下标索引
set 虽说可遍历，但仅可使用迭代器进行遍历，它不存在下标这一概念，无法通过下标访问到数据。下面是错误用法：
元素只读
set 的迭代器取到的元素是只读的（因为是 const 迭代器），不可修改其值。如果要改，需要先 erase 再 insert. 下面是错误用法：
不可用迭代器计算下标
set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：
提供对数时间的有序键值对结构。底层原理是红黑树。
映射：
2.7.1 常用方法
构造
- 键类型：要储存键的数据类型
- 值类型：要储存值的数据类型
- 比较器：键比较大小使用的比较器，默认为 ，可自定义
对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。
遍历
可使用迭代器进行遍历：
基于范围的循环（C++ 11）：
结构化绑定 + 基于范围的循环（C++17）：
示例
其他
增删改查时间复杂度均为
2.7.2 适用情形
需要维护映射的场景可以使用：输入若干字符串，统计每种字符串的出现次数。()
2.7.3 注意事项
中括号访问时默认值
如果使用中括号访问 map 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。
不可用迭代器计算下标
map 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：
顾名思义，就是储存字符串的。
2.8.1 常用方法
构造
构造函数：
输入输出
C++
C
其他
数值与字符串互转（C++11）
2.8.3 注意事项
尾接字符串一定要用
string 的 += 运算符，将会在原字符串原地尾接字符串。而 + 了再 = 赋值，会先生成一个临时变量，在复制给 string.
通常字符串长度可以很长，如果使用 + 字符串很容易就 TLE 了。
方法的奇葩参数
一定要注意，C++ string 的取子串的第一个参数是子串起点下标，第二个参数是子串长度。
第二个参数不是子串终点！不是子串终点！要与 java 等其他语言区分开来。
方法的复杂度
该方法实现为暴力实现，时间复杂度为 .
顾名思义，就是储存二元组的。
2.9.1 常用方法
构造
- 第一个值类型：要储存的第一个值的数据类型
- 第二个值类型：要储存的第二个值的数据类型
赋值
老式
列表构造 C++11
取值
直接取值
- 取第一个值：
- 取第二个值：
排序定义
结构化绑定 C++17
判同
直接用 运算符
2.9.2 适用场景
所有需要二元组的场景均可使用，效率和自己定义结构体差不多。
对于一个 vector，我们可以用下标遍历：
我们同时也可以用迭代器来遍历：
- 是一个迭代器，指向的是第一个元素
- 是一个迭代器，指向的是最后一个元素再后面一位
- 上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
- 迭代器与指针相似，如果对它使用解引用运算符，即 ，就能取到对应值了
通过迭代器，我们就能遍历 set 中的元素了：
对于 vector 容器，它的迭代器功能比较完整，以它举例：
- ：头迭代器
- ：尾迭代器
- ：反向头迭代器
- ：反向尾迭代器
- 迭代器 整型：将迭代器向后移动
- 迭代器 整型：将迭代器向前移动
- 迭代器 ：将迭代器向后移动 1 位
- 迭代器 ：将迭代器向前移动 1 位
- 迭代器 迭代器：两个迭代器的距离
- ：返回 it 的前一个迭代器
- ：返回 it 的后一个迭代器
对于其他容器，由于其结构特性，上面的功能不一定都有（例如 set 的迭代器是不能相减求距离的）
和 指向的位置是无意义的值
对于一个长度为 10 的数组：，第 10 位是不可访问的
对于一个长度为 10 的容器：，.end 是不可访问的
不同容器的迭代器功能可能不一样
迭代器细化的话有正向、反向、双向，每个容器的迭代器支持的运算符也可能不同，因此不同容器的迭代器细节很有可能是不一样的。
删除操作时需要警惕
在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。
- : 寻找 的第一个元素的位置
- : 寻找 的第一个元素的位置
怎么找 / 的第一个元素呢？
- 的第一个元素的前一个元素（如果有）便是 的第一个元素
- 的第一个元素的前一个元素（如果有）便是 的第一个元素
返回的是迭代器，如何转成下标索引呢？减去头迭代器即可。
用法示例
我们通常写成一行：
反转一个可迭代对象的元素顺序
用法示例
返回最大值 / 最小值的数值
用法示例
在 C++11 之后，可以使用列表构造语法传入一个列表，这样就能一次性给多个元素找最大值而不用套娃了：
消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的结尾迭代器。
例如：，下划线位置为返回的迭代器指向。
用法示例
单独使用 unique 并不能达成去重效果，因为它只消除相邻的重复元素。但是如果序列有序，那么它就能去重了。
但是它去重后，序列尾部会产生一些无效数据：，为了删掉这些无效数据，我们需要结合 erase.
最终，给 vector 去重的写法便是：
所有函数参数均支持 / / / /
注意事项
由于浮点误差，有些的数学函数的行为可能与预期不符，导致 WA。如果你的操作数都是整型，那么用下面的写法会更稳妥。
-
- 别用：
- 要用：
-
- 别用：
- 要用： （）
-
- 别用：
- 要用：二分查找
-
- 别用：
- 要用：快速幂
-
- 别用：
- 要用： （不规范，但是这是竞赛）/ （C++20 可用）
（C++17）返回最大公因数 / 最小公倍数
如果不是 C++17，但是是 GNU 编译器（g++），那么可以用内置函数 .
当然， / 函数也挺好写，直接写也行（欧几里得算法）：
