本文讲了一些 C++ STL 容器和容器适配器的基本用法和原理，当然没有所有的内容，只是说了一些比较常用的东西。
方法并不是所有都有提到，只是挑了一些常用的，并没有所有都讲（太多了）。
参考资料：
-
《算法竞赛进阶指南》
在此表示感谢。
0. 什么是 STL
C++ 标准模板库（Standard Template Library），简称 STL，是 C++ 标准库的一部分。
主要有算法（Algorithms）、容器（Containers）、迭代器（Iterators）三大部分。
简单来说，就是一个个封装好的数据结构和算法，方便使用
1. vector
vector 简单来说就是动态数组，包含在 \(\texttt{vector}\) 头文件里面。
实现
那么 vector 是怎么做到动态数组的呢？
vector 内部实现基于倍增思想：
设 \(n,m\) 为 vector 的实际长度和最大长度，向 vector 加入元素前，若 \(n=m\)，则在内存中申请 \(2m\) 的连续空间，并把内容转移到新的地址上（同时释放旧的空间），再执行插入。从 vector 中删除元素后，若 \(n\le m/4\)，则释放一半的空间。
（所以 vector 比较慢。
vector 支持随机访问，因为重载了运算符 []，所以对于任意的下标 \(0 \le i < n\) 可以向数组一样用 [\(i\)] 取值。
因为 vector 不是链表，所以不支持在任意位置 \(O(1)\) 插入元素。
声明
#include<vector>
vector<type> Name;
\(\texttt{type}\) 里面可以放任意的类型，包括结构体和类，\(\texttt{Name}\) 也可以是数组，比如 vector<int> b[10]; 也是可以的。
方法
-
构造函数
vector()创建一个空的 vector.vector(int nSize)创建一个 vector，元素个数为 \(\texttt{nSize}\).vector(int nSize, const T& t)创建一个vector，元素个数为 \(\texttt{nSize}\)，且值均为 \(\texttt{t}\). -
\(\texttt{push_back}\) / \(\texttt{pop_back}\)
push_back(x)往 vector 的最后加入元素 \(\texttt{x}\).pop_back()删除最后一个元素。 -
\(\texttt{size}\) / \(\texttt{empty}\)
size()函数返回的是 vector 的元素个数，empty()函数检测 vector 是否为空。 -
\(\texttt{clear}\)
clear()函数清空 vector. -
迭代器
迭代器就像 STL 容器的“指针”，可以用
*操作符解除引用。迭代器的声明：
vector<type>::iterator Name;\(\texttt{type}\) 和指向的 vector 的类型要相同。
vector<int> a; vector<int>::iterator it;迭代器可以与整数相加进行移动，或者和另外一个迭代器相减得到距离，和指针类似。
-
\(\texttt{begin}\) / \(\texttt{end}\)
begin()函数返回的是指向 vector 中的第一个元素的迭代器，end()返回的指向最后一个元素的下一个元素的迭代器。为什么要返回一个指向最后一个元素的下一个元素的迭代器呢？
方便，比如：
for(vector<int>::iterator it = a.begin(); i != a.end(); i++) cout << *it << " ";这样就可以遍历整个 vector 了。
因为迭代器像指针，所以
*a.begin()也等同于a[0]。*a.end()等同于a[a.size()]，这里越界访问了。同样的，上面的遍历 vector 的代码也可以写成：
for(int i = 0; i < a.size(); i++) cout << a[i] << " "; -
\(\texttt{front}\) / \(\texttt{back}\)
front()函数返回 vector 的第一个元素，等价于*a.begin()和a[0]。back()函数返回 vector 的最后一个元素，等价于*(a.end() - 1)和a[a.size() - 1]。 -
\(\texttt{insert}\)
insert(iterator it, const T& x)向量中迭代器指向元素前增加一个元素 \(\texttt{x}\).注意 \(\texttt{insert}\) 的时候，迭代器位置可能将改变，因为元素移动，所以迭代器指向的在修改前后可能不是同一个元素。
-
\(\texttt{erase}\)
erase(iterator it)删除向量中迭代器指向元素。同 \(\texttt{insert}\)，\(\texttt{erase}\) 的时候，迭代器位置可能将改变。
应用
数组需要节省空间时使用。
例：建图。
例题：【模板】建图。
2. queue
queue 就如其名，是一个队列（queue），包含在 \(\texttt{queue}\) 头文件里面。
queue 是一个容器适配器，建立在容器 list 或容器 deque 上。
底层使用链表实现所以不支持随机访问任意元素。
所以 queue 不支持随机访问，也就没有迭代器，插入删除时间复杂度为 \(O(1)\)。
声明
#include<queue>
queue<type> Name;
方法
-
构造函数
queue()创建一个空的 queue. -
\(\texttt{push}\) / \(\texttt{pop}\)
push(x)往 queue 的最后加入元素 \(\texttt{x}\).pop()弹出第一个元素。 -
\(\texttt{size}\) / \(\texttt{empty}\)
同 vector.
size()函数返回的是 queue 的元素个数，empty()函数检测 queue 是否为空。 -
\(\texttt{front}\) / \(\texttt{back}\)
front()返回 queue 的第一个元素。back()返回 queue 的最后一个元素。
其他技巧
-
清空队列
因为 queue 的底层是由链表实现的，链表的每一个元素不一定靠在一起，
所以 queue 没有办法像 vector 一样 \(O(1)\) 清空队列，且 STL 也没有提供这个函数。
所以我们如果要清空 queue 就需要自己写。
代码（其中 \(q\) 为 queue 定义的队列）：
while(!q.empty()) q.pop();意思：弹出队列的第一个元素直到队列为空。
注意时间复杂度是 \(O(n)\) 的。
应用
队列就。。队列。
例：广搜。
例题：滑动窗口 /【模板】单调队列。
3. priority_queue
priority 英[praɪˈɒrəti] 美[praɪˈɔːrəti]
n. 优先事项; 最重要的事; 首要事情; 优先; 优先权; 重点; (车辆的)优先通行权;
[例句] But respondents ranked it last on a list of priorities.
但被调查者将它排在优先事项列表的最后。
[其他] 复数：priorities
priority_queue 即优先队列，或叫优先级队列。
priority_queue 和 queue 一样，都包含在头文件 \(\texttt{queue}\) 里。
同 queue，priority_queue 也是一个容器适配器，建立在容器 vector 上。
优先队列
什么是优先队列？
明显地，是一个队列。但这个队列有一个优先级，下标越小，优先级越高。
比如规定数字大的优先级越高，那么这个队列就是一个不升序列。
为了维护这个队列的优先性，每进入一个元素或删除一个元素，都要进行一定次数的交换，以维护队列。
实现
如何实现优先队列？
你可能会想每次操作去对这个序列进行排序。
但是排序的时间复杂度太高了，大部分时间复杂度低的排序都为 \(O(n\log n)\)，如果我们有 \(n\) 个元素，那么最多会到 \(O(n^2\log n)\)，很显然不够高效
还有一个是插入排序和一部分的冒泡排序，但是时间复杂度最坏也会到达 \(O(n)\).
那有没有更快的？
有，堆。
为了方便，STL 使用了二叉堆（不知道的可以看 OI Wiki - 二叉堆），一次操作维护时间复杂度最坏为 \(O(\log_2n)\)，已经很高效了。
但也因为是堆，所以 priority_queue 不支持随机访问，也就没有迭代器。
STL 有内置的实现堆的函数，可以直接调用，priority_queue 就用了这几个函数。
这几个函数是对数组使用的，也可以用在 vector 上，而 priority_queue 就使用了 vector，所以 priority_queue 需要一个 vector.
声明
#include<queue>
priority_queue<type> Name;
priority_queue<type,vector<type> > Name;
priority_queue<type, vector<type>, functional> Name;
priority_queue 有 \(3\) 种声明方法，第一种，即定义一个 priority_queue，类型为 \(\texttt{type}\)，名称为 \(\texttt{Name}\).
如果以第一种定义，则定义了一个以元素大到小的 priority_queue。
但是因为 STL 是泛型编程，要适用于任意的类型。对于一些结构体、类，怎么比大小？
你可能知道了，可以重载运算符。在 priority_queue 中，使用 < 来比较大小的，所以你可以重载运算符 <。
不知道重载运算符可以看 菜鸟教程 - C++ 重载运算符和重载函数。
如果有两个优先队列，同一个类型，但比较方法不一样，为了再写一个类型定义另外一个比较方法，
于是就有了第三种声明方式，其中 \(\texttt{functional}\) 是比较方式，用仿函数。
仿函数是一个重载了 () 运算符的类或结构体，因为可以像函数一样调用但又不是函数，所以被叫做仿函数。在这里不对仿函数进行详细的讲解，想了解可以看 百度百科 - 仿函数。
第二种是一个相对完整的写法，传了一个 vector，如果不给这个 vector 数组用第一种定义方法，则 priority_queue 会自己定义。
如果你就只想让队列由小到大排，且里面的元素就只是单纯的数，但又不想重载运算符或写仿函数，其实 STL 已经提供了一个内置的仿函数 greater 可以直接使用，像这样：
priority_queue<int, vector<int>, greater<int> > q;
这样就定义了一个从小到大排的整型优先队列。
方法
-
构造函数
priority_queue()创建一个空的 priority_queue. -
\(\texttt{push}\) / \(\texttt{pop}\)
push(x)往 priority_queue 加入元素 \(\texttt{x}\).pop()弹出队首元素。 -
\(\texttt{size}\) / \(\texttt{empty}\)
同 vector.
size()函数返回的是 priority_queue 的元素个数，empty()函数检测 priority_queue 是否为空。 -
\(\texttt{top}\)
top()返回 priority_queue 的队首元素。
其他技巧
-
清空队列
可以像 queue 一样清空队列。
应用
比如需要用到堆的地方。
例题：【模板】堆。
4. set
set 除了设置、放，还有集合的意思。
所以 set 即集合，包含在 \(\texttt{set}\) 头文件中。
集合
关于集合的最简单的说法就是在朴素集合论（最原始的集合论）中的定义，即集合是“确定的一堆东西”，集合里的“东西”则称为元素。现代的集合一般被定义为：由一个或多个确定的元素所构成的整体。
实现
set 保证元素有序，基于红黑树实现。
红黑树是一颗二叉平衡搜索树，平衡树是二叉搜索树中的一类，这个搜索树满足任意节点的子树的高度差都小于等于 \(1\)，操作一次时间复杂度可以做到 \(O(\log n)\).
红黑树怎么实现？我不会，直接查 百度 - 红黑树。
声明
#include<set>
set<type> Name;
set<type, functional> Name;
定义一个 set，类型为 \(\texttt{type}\)，名称为 \(\texttt{Name}\).
一样的，因为 set 保证元素有序又要泛型编程，所以和 priority_queue 一样，结构体、类需要重载运算符 <（搜索树是需要比较的）或者写仿函数。
方法
这里的左边指优先级高，右边指优先级低。
-
构造函数
set()创建一个空的 set. -
\(\texttt{size}\) / \(\texttt{empty}\)
不讲了。
-
\(\texttt{clear}\)
clear()函数清空 set. -
\(\texttt{insert}\) / \(\texttt{erase}\)
insert(x)往 set 里加入元素 \(\texttt{x}\)，重复插入无效。erase(x)删除元素 \(\texttt{x}\).erase(iterator it)删除迭代器 \(\texttt{it}\) 指向的元素。 -
\(\texttt{count}\)
count(x)查看元素 \(\texttt{x}\) 的个数。因为重复插入无效，所以返回不是 \(1\) 就是 \(0\)。 -
\(\texttt{begin}\) / \(\texttt{end}\)
begin()函数返回的是指向 set 中的最左边的元素的迭代器，end()返回的指向最右边的元素的下一个元素的迭代器。 -
\(\texttt{find}\)
find(x)返回一个指向 \(\texttt{x}\) 位置的迭代器，找不到则返回end()的位置。
其他技巧
-
\(\texttt{lower_bound}\) / \(\texttt{upper_bound}\)
lower_bound(x)返回一个指向大于等于 \(\texttt{x}\) 的第一个元素的迭代器。upper_bound(x)返回一个指向大于 \(\texttt{x}\) 的第一个元素的迭代器。
应用
就。。集合。
5. map
map 除了地图，还有映射的意思。
map 即映射，包含在 \(\texttt{map}\) 头文件中。
映射
什么是映射，在数学里，映射是个术语，指两个元素的集之间元素相互“对应”的关系。
两个非空集合 \(A\) 与 \(B\) 间存在着对应关系 \(f\)，而且对于 \(A\) 中的每一个元素 \(a\)，\(B\) 中总有唯一的一个元素 \(b\) 与它对应，就这种对应为从 \(A\) 到 \(B\) 的映射，记作 \(f:A→B\)。其中，\(b\) 称为元素 \(a\) 在映射 \(f\) 下的像，记作：\(b=f(a)\)。\(a\) 称为 \(b\) 关于映射 \(f\) 的原像。集合 \(A\) 中所有元素的像的集合称为映射 \(f\) 的值域，记作 \(f(A)\)。
百度百科上抄的，看起来有点复杂，但其实说得已经很好理解了，可以多读几遍。
明显地，\(B\) 集合里面的元素不一定都用得上，也有可能一个元素对应 \(A\) 中的多个元素，也就是原像可能没有或者不止一个，所以一般的两个集合不存在逆映射。
在 map 中，\(A\) 集合叫做键，\(B\) 集合叫做值.
实现
map 保证元素有序，和 set 一样基于红黑树实现。
所以操作一次时间复杂度同 set 可以做到 \(O(\log n)\).
声明
#include<map>
map<key_type,value_type> Name;
map<key_type, value_type, functional> Name;
\(\texttt{key_type}\) 相当于集合 \(A\) 的类型，或者是键的类型。
\(\texttt{value_type}\) 相当于集合 \(B\) 的类型，或者是值的类型。
\(\texttt{functional}\) 不解释（之前说过了）。
方法
这里的左边指优先级高，右边指优先级低。
-
构造函数
map()创建一个空的 map. -
\(\texttt{size}\) / \(\texttt{empty}\)
不讲了。
-
\(\texttt{clear}\)
clear()函数清空 map. -
插入元素
-
\(\texttt{insert}\)
insert(pair<key_type, value_type> x)\(\texttt{x}\) 为一个 pair，第一个值为键，第二个值为值，即键对应值。不知道 pair 看这里 百度百科 - pair。
-
“数组”方式
set<string, int> s; s["123"] = 1;map 重载了运算符
[]和=，可以像数组一样更改键所对应的值。
-
-
\(\texttt{erase}\)
erase(x)删除键 \(\texttt{x}\)。erase(iterator it)删除迭代器 \(\texttt{it}\) 指向的键。 -
\(\texttt{count}\)
count(x)查看键 \(\texttt{x}\) 的个数。因为重复插入无效（像是唯一的），所以返回不是 \(1\) 就是 \(0\)。 -
\(\texttt{begin}\) / \(\texttt{end}\)
begin()函数返回的是指向 map 中的最左边的键的迭代器，end()返回的指向最右边的键的下一位的迭代器。 -
查找元素
-
\(\texttt{find}\)
find(x)返回一个指向键 \(\texttt{x}\) 位置的迭代器，找不到则返回end()的位置。 -
“数组”方式
set<string, int> s; cout << s["123"] << endl;map 重载了运算符
[]，可以像数组一样获取键所对应的值。
-
应用
标记一个值但是数据很大时可以用 map 代替数组标记。
例题：【模板】哈希。
6. 其他
STL 的容器、容器适配器不止这些，比如还有：
序列容器：list、forward_list、deque、array 等。
关联容器：multiset、multimap、unordered_set、unordered_map、bitset 等。
容器适配器：stack.
...