STL用法

序列式容器

向量 ( vector ) 后端可高效增加元素的顺序表。
数组 ( array ) C++11 ，定长的顺序表，C 风格数组的简单包装。
双端队列 ( deque ) 双端都可高效增加元素的顺序表。
列表 ( list ) 可以沿双向遍历的链表。
单向列表 ( forward_list ) 只能沿一个方向遍历的链表。

关联式容器

集合 ( set ) 用以有序地存储互异元素的容器。其实现是由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种比较元素大小的谓词进行排列。
多重集合 ( multiset ) 用以有序地存储元素的容器。允许存在相等的元素。
映射 (map) 由 {键，值} 对组成的集合，以某种比较键大小关系的谓词进行排列。
多重映射 ( multimap ) 由 {键，值} 对组成的多重集合，亦即允许键有相等情况的映射。

无序（关联式）容器

无序（多重）集合 ( unordered_set / unordered_multiset ) C++11 ，与 set/multiset 的区别在于元素无序，只关心「元素是否存在」，使用哈希实现。
无序（多重）映射 (unordered_map/unordered_multimap) C++11 ，与 map/multimap 的区别在于键 (key) 无序，只关心 "键与值的对应关系"，使用哈希实现。

共有函数

=：有赋值运算符以及复制构造函数。

begin()：返回指向开头元素的迭代器。

end()：返回指向末尾的下一个元素的迭代器。end() 不指向某个元素，但它是末尾元素的后继。

size()：返回容器内的元素个数。

max_size()：返回容器理论上能存储的最大元素个数。依容器类型和所存储变量的类型而变。

empty()：返回容器是否为空。

swap()：交换两个容器。

clear()：清空容器。

迭代器：

类似于指针,有两种字符可以使用例如 *it 和自增 ++

begin()/cbegin()

返回指向首元素的迭代器，其中 *begin = front。
end()/cend()

返回指向数组尾端占位符的迭代器，注意是没有元素的。
rbegin()/crbegin()

返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。
rend()/crend()

返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

很多 STL 函数都使用迭代器作为参数。

可以使用 std::advance(it, n) 将迭代器 it 向后移动 n 步；若 n 为负数，则对应向前移动。迭代器必须满足双向迭代器，否则行为未定义。

在 C++11 以后可以使用 std::next(it) 获得向前迭代器 it 的后继（此时迭代器 it 不变），
std::next(it, n) 获得向前迭代器 it 的第 n 个后继。

在 C++11 以后可以使用 std::prev(it) 获得双向迭代器 it 的前驱（此时迭代器 it 不变），std::prev(it, n) 获得双向迭代器 it 的第 n 个前驱。

vector

很泛用,优势在于动态开空间.

经典用法例如;邻接表存图等

vector<int>e[MAXN]
void push(int x,int y){
e[x].push_back(y);
e[y].push_back(x);
}
for (int i = 0 ; i < data.size(); i++)
cout << data[i] << endl;  //vector
for(auto y:v[x])//c++11以后

for(auto it=x.begin();it!=x.end();++it)

此两种遍历方式适合几乎所有STL

注意

insert() 支持在某个迭代器位置插入元素、可以插入多个。 复杂度与 pos 距离末尾长度成线性而非常数的

erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert() 一致。

priority_queue

优先队列,默认是大跟堆.

如果是pair类型默认的比较函数只比较第一个元素.

push(val): 将元素 val 插入优先队列。

pop(): 移除队列顶部的元素。

top(): 返回队列顶部的元素，即优先级最高的元素。

size(): 返回优先队列中的元素数量。

empty(): 检查优先队列是否为空。

set/multiset

set 是关联容器，含有键值类型对象的已排序集，搜索、移除和插入拥有对数复杂度。set 内部通常采用红黑树实现。平衡二叉树的特性使得 set 非常适合处理需要同时兼顾查找、插入与删除的情况。

和数学中的集合相似，set 中不会出现值相同的元素。如果需要有相同元素的集合，需要使用multiset。multiset 的使用方法与 set 的使用方法基本相同。

insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。

insert(first,last) 插入迭代器在 $[first,last)$ 范围内的所有元素。

erase(x) 删除值为 x 的所有元素，返回删除元素的个数。

erase(pos) 删除迭代器为 pos 的元素，要求迭代器必须合法。

erase(first,last) 删除迭代器在 $[first,last)$ 范围内的所有元素。

clear() 清空 set。

count(x) 返回 set 内键为 x 的元素数量。

find(x) 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()。

lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回end()。

upper_bound(x) 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回end()。

empty() 返回容器是否为空。

size() 返回容器内元素个数。

map

map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map 通常实现为红黑树。

map<Key, T> yourMap;

Key 是键的类型，T 是值的类型，下面是使用 map 的实例：

map<string, int> M;

插入与删除操作

可以直接通过下标访问来进行查询或插入操作。例如 mp["Alan"]=100。

通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如mp.insert(pair<string,int>("Alan",100));；

erase(key) 函数会删除键为 key 的所有元素。返回值为删除元素的数量。

erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。

erase(first,last): 删除迭代器在 $[first,last)$ 范围内的所有元素。

clear() 函数会清空整个容器。

map 中不会存在键相同的元素，multimap 中允许多个元素拥有同一键。multimap 的使用方法与 ```map`` 的使用方法不太一样.

使用样例

`map` 用于存储复杂状态

在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之

有关的答案（如到达此状态的最小步数）。map 可以用来实现此功能。其中的键是状态，而值是与之相
关的答案。

bitset

size()：返回 bitset 的位数。

count()：返回 bitset 中值为 1 的位的数量。

any()：返回 bitset 中是否有。

set()：将所有位都设置为 1 。

set(pos)：将第 pos 位设置为 1 。

reset()：将所有位都设置为 0 。

reset(pos)：将第 pos 位设置为 0 。

flip()：对所有位取反。

flip(pos)：对第 pos 位取反。

位运算操作符：

`&`：按位与。

`|`：按位或。

`^`：按位异或。

`<<`：左移。

`>>`：右移。

比较常见的用法就是优化各种暴力,使其复杂度 ,从而通过某些题目.

例如

给你n个集合（ $n\le10000$ ）每个集合最多 $10000$ 个数，每个数最大为 $10000$ ，最多$2^5$次查询，询问是否存在$x,y$是否在同一个集合中.
有 $n$ 个数， $x_i$ 可以取值 $l_i-r_i$ ，问 $sum({x_i}^2)$ 可能的值有多少。

考虑设 $f[i][j]$ ,前 $i$ 个数，和为 $j$ 的数字是否存在,转移方程如下:

$$
f[i][j]=f[i-1][j-x*x]
$$

直接暴力复杂度是 $10^10$ , 但是可以通过bitset优化.

$n$ 个数，背包容量 $m$ ，问装满背包时候，背包里面异或值最大可能是多少( $n,m,v_i\le1024$ )？

f[i][j][k] = f[i - 1][j][k] 不选i
f[i][j][k] |= f[i - 1][j ^ w][k - v] 选i

需要注意的是bitset大概能通过 $10^5$ 的 $n^2$ 再往上会因为空间问题挂掉,不过可以使用根号分治之类的手段降低空间复杂度.