STL是C++标准库的一部分，中文翻译为“标准模板库”，其中包含了一些常用的算法与数据结构，他们通常存储在对应的头文件中如<vector> <stack> <queue>，或者是直接使用<bits/stdc++.h>。
原本的训练内容是栈和队列，但这两种数据结构属于竞赛中 常用的STL ，所以这里进行了一些扩展。下面将简单介绍几种 常用的STL 容器，内容以概括汇总为主，并不涉及很多原型以及特殊用法。
如无特殊说明，以下默认使用x作为变量，使用it指代迭代器。
基本概念
迭代器iterator
STL中存在迭代器的概念，它类似指针操作，指向容器中的某个元素。同样可以使用“*”解除引用，在不同的STL中还分为“随机访问迭代器”和“双向访问迭代器”等等，他们在使用上有所不同。
随机访问迭代器
代表容器:vector
有类似指针的操作，可以对迭代器进行加减从而实现移动；也可以两个迭代器相减获得两个元素的位置。
以vector为例,遍历并输出：
vector a;
for(vector::iterator i=a.begin();i!=a.end();i++)
{
cout<<*i<<" ";
}
//或者是：
vector::iterator it=a.begin();
for(int i=0;i<a.size();i++)
{
cout<<it[i];
}
双向访问迭代器
代表容器：set
只能对迭代器进行++或者–操作，不能像随机访问迭代器一样跳跃访问或者是赋值。
像set这样内部有序的容器，++和–操作代表的是按照容器排序规则的上一个元素或者是下一个元素。
|
容器
|
对应的迭代器类型
|
|
array
|
随机访问迭代器
|
|
vector
|
随机访问迭代器
|
|
deque
|
随机访问迭代器
|
|
list
|
双向迭代器
|
|
set / multiset
|
双向迭代器
|
|
map / multimap
|
双向迭代器
|
|
forward_list
|
前向迭代器
|
|
unordered_map / unordered_multimap
|
前向迭代器
|
|
unordered_set / unordered_multiset
|
前向迭代器
|
|
stack
|
不支持迭代器
|
|
queue
|
不支持迭代器
|
For each 遍历容器
我们可以使用下面的方式遍历大多数容器；
map<string,int> m;
for(auto i:m)
{
cout<<i.first<<" "<<i.second<<endl;
}
通用操作
以下是所有容器都支持的操作，之后将不再列出这两个操作:
a.size();//返回容器中元素的数量 a.empty();/如果容器为空返回true，否则返回false
以下一些成员函数经常出现，并且功能类似，这里提前进行介绍，在之后的内容中不再详述:
a.begin();//返回容器首元素的迭代器 a.end();//返回容器最后一个元素之后的迭代器，a.end()-1才是最后一个元素的迭代器 a.clear();//清空容器 a.push(x);//向容器中添加一个元素，类似的还有push_back和pop_front a.pop();//将容器中的元素弹出，类似的还有pop_back和pop_front
vector向量/动态数组
vector实现的是基于倍增的思想。.
一般声明的数组长度是固定的，如果使用链表储存，不断动态申请内存会降低程序运行的效率，并且程序的编写会变得更加复杂，因此我们常使用vector来当作动态数组。在底层实现中，vector也是通过动态申请内存的方式来实现动态存储。当vector被存满的时候会进行扩容操作，基本的过程如下：
- 重新申请一个更大的空间。
- 将原数据存入新空间。
- 释放原有空间。
因为扩容后数据存储到了一个新空间中，因此原有的迭代器、指针和引用有可能会失效，同时为了避免反复申请空间，不同的编译器会申请不同的额外空间，通常是之前数据的两倍。
将所有数据放入新空间的操作尽管花费了更多的时间，但是可以保证内存空间的连续性，这也是为什么vector可以支持随机访问。
常用的成员函数
a.push_back(x); a.pop_back(); a.clear(); a.push(); a.pop(); a.begin(); a.end();
常用用法
- 使用下标进行访问元素
- 存储邻接表
- hash的拉链法
deque双端队列
参考：C++ STL deque容器底层实现原理（深度剖析） (biancheng.net)
deque 和vector有些类似，都是通过动态申请空间实现。
不同的是deque存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。然后使用一个map数组记录每一段的地址，由此保证整体有序。
当要在队首或者队尾插入新的数据时，只需要新申请一段空间，然后将其地址存入map数组中。
当map数组存满以后使用类似vector的方式重新申请空间并转移数据。
deque实例
常用的成员函数
q.push_back(x); q.push_front(x); q.pop_back(); q.pop_front(); q.front();//返回队首元素 q.back();//返回队尾元素 q.clear(); q.begin(); q.end();
常用用法
stack、list、queue的底层均使用了deque实现。
stack栈
栈是一种基础的数据结构，也被称为FILO表（先进后出），底层使用deque实现。
常用的成员函数
s.push(x); s.pop();//弹出栈顶元素 s.top();//返回栈顶元素的引用
注意，栈并没有提供迭代器可以遍历所有元素，也没有提供clear来快速清空。
queue队列
队列是一种基础数据结构，也被称为FIFO表（先进先出），底层使用deque实现。
常用的成员函数
q.push(x); q.pop(); q.front();//返回队首元素 q.back();//返回队尾元素
常用用法
在进行广度优先搜索时会使用到queue，有些算法可能会使用到堆优化，则需要使用下面的priority_queue
priority_queue优先队列
优先队列底层通过vector实现，并在其内部维护了一个堆，因此可以保证top的元素为最大（最小）。
我们在大多数情况下可以使用优先队列来代替堆。
声明方式
priority_queue q;//默认大根堆 priority_queue <int,vector<int>,greater<int>> q;//声明大根堆 priority_queue <int,vector<int>,less<int>> q;//声明小根堆
对于大根堆和小根堆，还可以通过结构体的重载运算符实现，但如果不存储结构体变量，上述的声明方式更加简洁.
常用的成员函数
q.push(x); q.pop(); q.top();//返回堆顶元素，也就是最大值（最小值）
常用用法
- 代替堆
- 需要维护最大或者最小值的情况
扩展操作：懒惰删除法
相比于自己手写的堆，STL的灵活性并没有那么高，不能进行单点修改、单点删除等。为此我们可以使用懒惰删除法。
我们采取的策略是额外记录删除信息，当我们从堆顶取出来的时候再判断元素是否已经被删除，也就是说删除操作要在堆顶进行。
（示例暂缺）
set/multiset集合
这两个容器维护的是一个集合，前者不允许集合中存在相同的元素，后者允许相同的元素存在。
在集合中的元素都是有序的（默认从小到大，可以重载运算符）。
常用的成员函数
s.clear(); s.begin(); s.end(); s.insert(x);//插入一个元素 s.find(x);//查找等于x的元素并返回他的迭代器，如果不存在则返回s.end(); s.lower_bound(x);//查找大于等于x的元素中最小的一个，并返回指向他的迭代器 s.upper_bound(x);//查找大于x的元素中最小的一个，并返回指向他的迭代器 s.erase(it);//删除it指向的元素 s.erase(x);//删除所有等于x的元素（multiset） s.count(x);//计算集合中x的数量（multiset）
关于lower_bound和upper_bound
这两个函数的区别在于是否取到等于号，也常被用在二分中。
map/multimap映射
该容器存储一个键值对（key-value）
常用的成员函数
m.clear(); m.begin(); m.end(); m.insert(make_pair(key,value)); m.erase(it); m.erase(key);//以上和set功能类似 m.find(key);//查找到key所在的二元组并返回迭代器，如果不存在则返回m.end()
[ ]操作符
该容器也可以使用[ ]来访问元素，但索引不是下标，而是key值（类似PHP中Array的键值对），同时可以对其进行复制操作改变value
常用用法
当做hash表使用。
参考内容：
[1]李煜东．算法竞赛进阶指南．
[2]C语言中文网：C语言程序设计门户网站(入门教程、编程软件) (biancheng.net)
