1.2.1 vector

#include <vector>

vector是非常常用的一个STL容器，虽然名字叫做向量，但在实际使用时，常将其作为一个动态数组来使用，也极少称之为向量。

在需要定义数组时，经常可以使用vector，将其全部初始化为0，并给它稍大的空间，以防越界，常用的范围是1~n，0和n+1则不被使用：

vector<int>v(n+2,0);

除了在定义时初始化，也可以使用v.reserve(n+2)来预分配空间，需要避免频繁push_back导致多次扩容。

vector使用的Type也可以是另一个STL容器，例如vector<vector<int>>，这类似于一个二维数组，也可以进行初始化，但其中的每个元素都是一个vector<int>，这些元素又组成了一个vector。

vector<vector<int>> a(n+2, vector<int>(n+2, 0));

迭代器，iterator，可以理解为一个指向容器中元素的指针，通过迭代器可以遍历容器中的所有元素。

例如v.begin()，返回的就是v[0]的地址，就像我们处理指针一样，如果我们想要得到v[0]的值，就需要解引用，也就是*it。

for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
}

v.end()返回的是最后一个元素的下一个位置，因此在这里使用it < v.end()也是等效的，但并不够通用，并不是所有STL容器的迭代器都可以这样写，因为这样比较的前提是区间连续。

如果数据从v[1]开始存储，那么就应该从v.begin()+1开始遍历。

需要注意的是，在向vector插入或删除元素后，原有的迭代器可能会失效，需要重新获取。

1.2.2 queue

#include <queue>

队列，它是先进先出的，只能在队尾插入数据。

需要注意的是，队列并没有clear()函数，当你需要清空队列，不妨考虑q = queue()。

1.2.3 deque

#include <deque>

双端队列，既可以在队首插入数据，也可以在队尾插入数据。

1.2.4 priority_queue

#include <queue>

优先队列，默认使用less<Type>，得到大根堆，即顶部为最大值；使用greater<Type>得到小根堆，即顶部为最小值。

1.2.5 stack

#include <stack>

栈，它是先进后出的，只能在栈顶插入数据。

1.2.6 list

#include <list>

双向链表，一个很大的特点是，所储存的元素在物理意义上是非连续、非顺序的，适合频繁在中间插入删除的情况。

特别的，链表不能使用algorithm中的sort，但自带有sort成员函数。

1.2.7 map

#include <map>

映射，其中的KeyType都是唯一的。

一个常用的地方是map<char,int>，可以用于储存char型元素出现的次数。

    map<char, int>::const_iterator it;
    for(char ch='a';ch<='z';ch++){
        it=hash.find(ch);
        if(it==hash.end()||it->second<1){
            return false;
        }
    }

1.2.8 set

#include <set>

集合，也就是每个元素仅会出现一次。

1.2.9 pair

#include <utility>

特别的，#include <map>中包含了pair的实现。

对，将两个不同类型的值组合成一个有序对，一个常见的用处是，作为将两个元素绑在一起的结构体的代替品。