C++ STL
C++ STL 是 C++ 自带的函数库，做题时充分利用这些函数，能节省大量时间。
vector
可变长数组，倍增的思想。
具体来说，一个 vector 数组一开始长度不大，每当元素装满数组， vector 便向系统申请两倍于原空间的空间，然后将原来的数据全移到新空间上。
vector 没有一个个申请空间，是因为在 C++ 中，申请空间的速度与空间的大小无关，而是与申请次数挂钩。
定义
vector<int> v;
基本操作
v[x]支持随机寻址。v.size()返回元素个数。v.empty()返回是否为空。v.clear()清空数组。v.push_back()、pop_back()分别表示在尾部添加和删除元素。v.begin()、v.end()分别返回头部迭代器和尾部迭代器。
支持比较运算，按字典序。
pair
存储成对的元素，用于排序的话排序后还能找到每个元素原来的下标。
定义
pair<int,int> p;
基本操作
p.first第一个元素。p.second第二个元素。
支持比较运算，按字典序（以first为第一关键字，以second为第二关键字）。
string
字符串。
定义
string s;
基本操作
s.size()/s.length()返回字符串长度。s.empty()返回字符串是否为空。s.clear()清空字符串。s.substr(【起始下标】，【子串长度】)返回子串。s.c_str()返回字符串所在字符数组的起始迭代器。
queue,
队列，先进先出表。
定义
queue<int> q;
基本操作
q.size()返回元素个数。q.empty()返回队列是否为空。q.push()向队尾插入一个元素。q.front()返回队头元素。q.back()返回队尾元素。q.pop()弹出队头元素。
priority_queue
优先队列，相当于一个二叉堆，维护极值在堆顶。
默认是大根堆。
定义
priority_queue<int> q;
基本操作
q.size()返回元素个数。q.empty()返回队列是否为空。q.push()插入一个元素。q.top()返回堆顶元素。q.pop()弹出堆顶元素。
定义成小根堆的方式：
priority_queue<int,vector<int>,greater<int> > q;
至于为什么会变成小根堆，读者有兴趣可以查资料，这里不多叙述。
stack
栈，先进后出表。
定义
stack<int> s;
基本操作
s.size()返回元素个数。s.empty()返回栈是否为空。s.push()向栈顶插入一个元素。s.top()返回栈顶元素。s.pop()弹出栈顶元素。
注意， C++ 中给栈分配的空间有限，数据大时可能会溢出，俗称“爆栈”，要慎用。
deque
双端队列，几乎有上文函数的所有操作。
定义
deque<int> d;
基本操作
d.size()返回元素个数。d.empty()返回双端队列是否为空。d.clear()清空双端队列。d.front()返回队头。d.back()返回队尾。d.push_back()在队尾添加元素。d.pop_back()在队尾删除元素。d.push_front()在队头添加元素。d.pop_front()在队头删除元素。d.begin()返回队头迭代器。d.end()返回队尾迭代器。d[x]支持随机寻址。
set 和 map
都基于平衡树（红黑树），动态维护有序序列。
这两个函数内部差不多，用法也差不多
时间复杂度 \(\operatorname{O(logn)}\)
set 和 multiset
有序集合， set 自动去重， multiset 不去重，用法相同。
定义
set<int> s;
multiset<int> ms;
基本操作
s.size()返回集合元素个数。s.empty()返回集合是否为空s.clear()清空集合。s.begin()返回集合头部迭代器。end()返回集合尾部迭代器。++, --返回前驱和后继。s.insert(x)插入一个数。s.find(x)查找一个数。s.count(x)返回某一个数的个数。s.erase(x)分两种情况：- 输入是一个数 \(x\) ，删除所有 \(x\) 。
- 输入一个迭代器，删除这个迭代器。
s.lower_bound(x)返回大于等于x的最小的数的迭代器。s.upper_bound(x)返回大于x的最小的数的迭代器。
map 和 multimap
映射器，可以将映射前类型 key（包括 STL 容器的任何基本类型）映射到映射后类型 value （包括 STL 容器的任何基本类型）。
和 set 一样， map 分去重和非去重型，分别为 map 和 multimap 。
定义
map<int,int> m;
multimap<int,int> mm;
基本用法
m.size()返回映射器元素个数。m.empty()返回映射器是否为空m.clear()清空映射器。m.begin()返回映射器头部迭代器。m.end()返回映射器尾部迭代器。++, --返回前驱和后继。m.insert({x,y})插入一个 pair 。m.erase({x,y})输入一个 pair 或迭代器。m.find(x)查找一个元素。m[x]支持随机寻址，不过 multimap 不支持此操作。lower_bound()返回大于等于x的最小的数的迭代器。upper_bound()返回大于x的最小的数的迭代器。
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位取反