建议参考：https://cplusplus.com/reference/
AcWing STL 模板
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
1.vector
#include <vector>
vector<int> v;
vector<vector<int> > a(k + 1, vector<int>(n + 1)); //a[k + 1][n + 1]
vector G(N, vector(N, 0)); // vector G(N, vector<int>(N, 0)) //G[N][N]
/* 操作 */
v.clear(); // 清空
v.swap(v1); // 和另一个 vector 进行交换，常数复杂度
v.push_back(k); // 从末尾插入
v.emplace_back(k); // 从末尾插入，更快
v.pop_back(); // 弹出末尾元素
v.insert(pos, k); // 在 pos 之前插入 k
v.emplace(pos, k); // 同上面的 insert，更快，但只能插入一个元素
v.insert(pos, n, k); // 在 pos 之前插入 n 个 k
v.insert(pos, v1.begin(), v1.end()); // 在 pos 之前插入另一个 vector 中的一段（左闭右开）[ )
v.insert(pos, {1, 2, 3, 4, 5}); // 显而易见
v.erase(pos); // 删除 pos 指的元素
v.erase(pos1, pos2); // 删除 [pos1, pos2) 的元素
/* 查询 */
v[k]; // 访问第 k 个元素
v.front(); // 返回首元素
v.back(); // 返回尾元素
v.begin(); // 返回首元素的迭代器
v.end(); // 返回数组尾端占位符的迭代器（空）
v.empty(); // 返回 vector 是否为空
v.size(); // 返回 vector 元素个数
/* 遍历 */
for(int i = 0; i < v.size(); ++i)
v[i];
2.queue
#include<queue>
queue<int> q;
// priority_queue<int> q（从大到小排序）;
q.empty(); // 判断队列是否为空
q.size(); // 返回队列长度
q.push(item); // 对于 queue，在队尾压入一个新元素
// 对于 priority_queue，在基于优先级的适当位置插入新元素
q.pop(); // 弹出队首元素
// queue only:
q.front(); //返回队首元素的值，但不删除该元素
q.back(); //返回队尾元素的值，但不删除该元素
// priority_queue only:
q.top(); //返回具有最高优先级的元素值，但不删除该元素
deque
与 queue 其他一样，仅有以下区别：
deque<int> q;
q.push_front();
q.push_back();
q.pop_front();
q.pop_back();
priority_queue
int a[]= {10,60,50,20};
priority_queue<int> q1;
priority_queue<int> q2(a, a + 4);
priority_queue<int, vector<int>, greater<int> > q3(a, a + 4);
q.empty();
q.top();
q.emplace();
q.push();
q.pop();
q1.swap(q2);
3.string
#include<cstring>
string s1,s2;
s1 + s2; // 将两个字符串拼接
[cur]; // 访问下标
s1.size(); // 返回字符串长度
s1.append(str); // 将 str 添加到 s1 末尾
s1.replace(pos, n, str); // 将从 pos 位置开始 n 个字符的子串替换为 str
s1.replace(first, last, str);// 将以 first 开始（含）、last 结束（不含）的子串替换为 str，其中 first 和 last 均为迭代器
s1.erase(pos, n); // 删除从 pos 开始（含）的 n 个字符 (若不传参给 n 则表示删去 pos 位置及以后的所有字符）
s1.insert(pos, str); // 在 pos 位置插入字符串 str
s1.insert(pos, n, str) // 在 pos 处连续插入 n 次字符串 str
s1.substr(pos, len); // 从 pos 位置开始截取一个长度为 len 的字符串 (如果从 pos 开始的后缀长度不足 len 则截取这个后缀）
s1.find(str, pos); // 查找字符串中一个字符/字符串在 pos（含）之后第一次出现的位置（若不传参给 pos 则默认为 0 ）
s1.rfind(ch); // 从末尾开始，查找并返回第一个找到的字符 ch 的位置
// 找不到则返回 -1
stoi, stol, sto
从字符串中转换整数、长整数或浮点数。
int num = stoi("123");
double val = stod("123.456");
to_string
将数值转换为字符串。
string str = to_string(123);
4.stack
先进后出
#include<set>
stack<int> s;
stack<int, vector<int> > stk; // 覆盖基础容器类型，使用vector实现stk
s.empty(); // 判断 stack 是否为空，为空返回 true，否则返回 false
s.size(); // 返回 stack 中元素的个数
s.pop(); // 删除栈顶元素，但不返回其值
s.top(); // 返回栈顶元素的值，但不删除此元素
s.push(item); // 在栈顶压入新元素 item
5.set
自动从小到大排序，自动去重
所有操作的时间复杂度为 O(log n)，因为 set 是基于平衡二叉树（红黑树）实现的。
#include<set>
//初始化
set<int> s; // multiset<int> s （不去重）
set<int, greater<int> > s; // 降序排序
set<int> s(s2);
set<int> s = {1, 2, 3};
set<int> s(pos1, pos2);
// 迭代器
set<int>::iterator it;
// 插入
s.insert(k);
s.insert({9, 10, 11});
s.insert(pos1, pos2); //插入[pos1, pos2)内的元素
//删除
s.erase(k); // 删除值为 k 的元素
s.erase(it); // 删除迭代器 it 指向的元素
s.erase(pos1, pos2); // 删除[pos1, pos2)内的元素
//查找
s.find(k); // 查找某元素 k ，找到则返回其迭代器，否则返回 s.end()
s.count(k); // 返回某个值元素 k 的个数
s.contains(k); //(C++20 引入）：更简洁的判断值是否存在
s.contains({1, 2, 3})//（C++23引入）：可以检查一个 initializer_list 或一个范围的所有元素是否存在
//查询
s.lower_bound(k);//返回第一个 >= 给定值 k 的迭代器
s.upper_bound(k);//返回第一个 > 给定值 k 的迭代器
s.equal_range(k);//返回等于给定值 k 的范围（对于 set 而言，最多返回一个元素的范围）
s.emplace(k); // 类似于 insert(k)
s.emplace_hint(pos1, k); // 提示位置为 pos1
s.merge(s2); //（C++17 引入）：将另一个 set(s2) 的元素合并到当前 set(s) 中，重复元素会被忽略
s.empty(); // 判断 set 是否为空，为空返回 true，否则返回 false
s.clear(); // 清除所有元素
s.rbegin();
s.rend();
s.begin(); // 返回指向第一个元素的迭代器
--s.end(); // 返回指向最后一个元素的迭代器
*s.begin(); // 返回指向第一个元素的值
*--s.end(); // 返回指向最后一个元素的值
// 区间形式为 [ begin , end ) ，所以 end 要自减
s.size(); // 返回集合中元素的个数
//支持 == 、!= 、< 、 > 等操作符
/* 遍历 */
for(it = s.begin() ; it != s.end() ; ++it)
*it; // 使用迭代器遍历
set 的默认比较器是 <，这意味着元素必须支持 < 运算符。如果你需要自定义排序规则，需要提供一个比较器函数或仿函数。
struct Compare {
bool operator()(const int &a, const int &b) const {
return a > b; // 降序排序
}
};
std::set<int, Compare> s;
unordered_set
不排序，O (1) 查找。
#include <unordered_set>
// #include <unordered_multiset>
unordered_set<ll> s;
// unordered_multiser<ll> s;
s.insert(); // 在开头插入某元素
s.find(); // 查找，返回迭代器
s.count(); // 返回某个值元素的个数
/* 遍历 */
for(iter = s.begin() ; iter != s.end() ; ++iter)
*iter;
// 注意：新插入的元素遍历时先被扫到。
6.map
#include<map>
map<int, string> m;// int 是 key，string 是 value。
// 基本操作
m.size();
m.empty();
m.clear();
m.count(k);
// 插入
m[1] = "one"; // 如果键不存在，会创建新元素
m[2] = "two"; // 如果键存在，会更新值
m.insert({3, "three"}); // 插入一个键值对
m.insert(pair<int, string>(4, "four"));
m.insert(make_pair(5, "five"));
m.emplace(5, "five"); // 效率比 insert 略高，避免不必要的拷贝
// 修改
m[1] = "XCPC";
m.find(1)->second = ...;
// 查找
m[1];
m.at(1);
m.find(1)->second;
auto it = m.find(3);
if (it != m.end())
cout << it->first << ": " << it->second << endl;
else
cout << "Key not found" << endl;
// 删除
m.erase(2); // 删除键为 2 的元素 //删除键为 k 的元素
m.erase(it); // 删除迭代器指向的元素
// 遍历
它会按照 key 排序
for(auto it = mp.begin(); it != mp.end(); ++it)
cout << it->second << ' ';
for (const auto& [key, value] : m)
cout << key << ": " << value << endl;
// 其他函数
auto lb = m.lower_bound(2); // 返回第一个键 >= 2 的迭代器
auto ub = m.upper_bound(2); // 返回第一个键 > 2 的迭代器
auto range = m.equal_range(2); // 返回一对迭代器，分别为 lower_bound 和 upper_bound
m1.swap(m2);
// 自定义比较函数
struct Compare {
bool operator()(const int& a, const int& b) const {
return a > b; // 降序排列
}
};
map<int, string, Compare> m3 = {{1, "one"}, {2, "two"}, {3, "three"}};
for (const auto& [key, value] : m3)
cout << key << ": " << value << endl;
multimap
#include <map>
multimap<int, string> mp; // 可重
mp.size(), mp.empty(), mp.clear(); // 常规操作
mp.count(k) // 找 key 为 k 的个数
mp.find(k) // 返回第一个插入的 k 的迭代器
mp.erase(k) // 删除所有键值为 k 的元素
/* 插入 */
mp.insert(make_pair(int, string)); // 只能用 make_pair 构造键值对
/* 修改 */
m.find(k)->second = ...; // 修改第一个插入的 key 为 k 的
for(auto it = mp.find(k); it->first == k; ++it) // 修改 key 为 k，值为自己选的
if(it->second == "I") it->second = "Love";
/* 查找 */
mp.find(k)->second;
/* 遍历 */
for(auto it = mp.begin(); it != mp.end(); ++it)
cout << it->second << ' ';
unordered_map
#include<unordered_map>
用法：与 map 差别不大。
优点：因为内部实现了哈希表，因此其查找速度非常的快
缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用 unordered_map
7.list
#include <list>
list<int> l, l2;
list<int>::iterator it;
/* 操作 */
l.clear(); // 清空
l.insert(it, 0);// 在迭代器前面插入一个元素，迭代器指向原来的元素
l.erase(it); // 删除迭代器指向的元素
l.remove(0); // 在 list 删除某一种元素（全删）
l.push_back(0); // 在 list 的末尾添加一个元素
l.push_front(0);// 在 list 的头部添加一个元素
l.pop_back(); // 删除最后一个元素
l.pop_front(); // 删除第一个元素
l.merge(l2); // 合并两个 list
l.reverse(); // 把 list 的元素倒转
l.sort(); // 给 list 排序
l.swap(l2); // 交换两个 list
l.unique(); // 删除 list 中重复的元素
/* 查询 */
l.begin(); // 返回指向第一个元素的迭代器
l.end(); // 返回末尾的迭代器
l.front(); // 返回第一个元素
l.back(); // 返回最后一个元素
l.empty(); // 如果 list 是空的则返回 1
l.size(); // 返回 list 中的元素个数
/* 遍历 */
for(it = l.begin(); it != l.end(); ++it)
*it;
8.bitset
#include <bitset>
bitset<100> b;
bitset<100> f;
b = 10, f = 11;
b[0]; // 访问某一位
bitset(): 每一位都是 false
bitset(unsigned long val): 设为 val 的二进制形式
bitset(const string& str): 设为 01串 str
/* 相同大小的 bitset 可以进行运算符操作 */
/* == != & &= | |= ^ ^= ~ << <<= >> >>= */
b.count(); // 返回 1 的数量
b.size(); // 返回 bitset 的大小
b.any(); // 若有 1， 返回 1
b.none(); // 若无 1， 返回 1
b.all(); // 若全是 1， 返回 1
b.set(); // 全部设为 1
b.set(pos, val);// 将第 pos 位设为 val (0/1)
b.reset(); // 全部设为 0
b.reset(pos) // 将pos位设置成 false
b.flip(); // 翻转每一位
b.flip(pos); // 翻转 pos 位
b.to_string(); // 返回转换成的字符串表达
b.to_ulong(); // 返回转换成的 unsigned long 表达
b.to_ullong() // 返回转换成的 unsigned long long 表达
b._Find_first();// 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小
b._Find_next(pos);// 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小
9.rope
Rope 的复制操作是 O (log n) 的，可以较轻松地实现可持久化。
想要使用 rope，需要在头文件中加入两行：
#include <ext/rope>
using namespace __gnu_cxx;
定义字符串类型的 rope，叫做 crope，要这样定义：
crope a;
支持的操作:
a.push_back(x); // 在 a 的末尾添加字符串 x
a.insert(k, x); // 在 a 的第 k 个字符后加入字符串 x
a.erase(k, x); // 在 a 的第 k 个字符后删除 x 个字符
a.replace(k, x); // 将 a 的第 k 个字符后 x 的长度个字符删除，并插入 x
a.substr(k, x); // 获取 a 的第 k 个字符后的长度为 x 的字符串
a.at(k); // 获取 a 的第 k 个字符（从 0 开始）