STL1 容器、pair 模板、容器适配器
在写C++程序的时候会发现STL是一个不错的东西，减少了代码量，使代码的复用率大大提高，减轻了程序猿的负担。还有一个就是容器，你会发现要是自己写一个链表、队列，或者是数组的时候，既要花时间还要操心怎么去维护，里面的指针啊，内存够不够用啊，长度问题，有没有可能溢出啊等等一系列的问题等着我们去解决，还是比较头疼的。所以容器的出现解决了这一个问题，它将这些数据结构都封装成了一个类，只需要加上头文件，我们就可以轻松的应用，不用那么复杂，就连指针也被封装成了迭代器，用起来更方便，更人性化，方便了我们的编程，对于程序员来说还是一大福音！！
C++中的容器类包括“顺序存储结构”和“关联存储结构”，前者包括vector，list，deque等；后者包括set，map，multiset，multimap等。若需要存储的元素数在编译器间就可以确定，可以使用数组来存储，否则，就需要用到容器类了。
STL 基本概念：https://www.cnblogs.com/lsgxeva/p/7789100.html
注：
1 能进行算术运算的迭代器只有随机访问迭代器，要求容器元素存储在连续内存空间里，所以，没有关联容器的迭代器能算术运算。 只有vector 和 deque 才可以，list也不可以。
2 在multimap中，同一个键关联的元素相邻存放。
一、顺序容器
1 vector
可变长的动态数组
必须包含头文件 #include <vector>
支持随机访问迭代器
• 根据下标随机访问某个元素时间为常数
• 在尾部添加速度很快
• 在中间插入慢
所有STL算法都能对vector操作
常用构造函数
vector(); 无参构造函数, 将容器初始化成空的
vector(int n); 将容器初始化成有n个元素
vector(int n, const T & val); 假定元素类型是T, 将容器初始化成有n个元素, 每个元素的值都是val
vector(iterator first, iterator last); 将容器初始化为与别的容器上区间[first, last)一致的内容
用法示例
vector<int>a, b(n,0) 的意思就是 创建了一个 int 类型的空的vector容器a，和一个 int 类型n个元素，且值均为0的vector容器b
常用成员函数
void pop_back(); 删除容器末尾的元素
void push_back(const T & val); 将val添加到容器末尾
int size(); 返回容器中元素的个数
T & font(); 返回容器中第一个元素的引用
T & back(); 返回容器中最后一个元素的引用
二维动态数组
vector< vector > v(3);
v有3个元素,
每个元素都是vector 容器
注：
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
优点：
(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()
(2) 随机访问方便，即支持[ ]操作符和vector.at()
(3) 节省空间。
缺点：
(1) 在内部进行插入删除操作效率低。
(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。
2 list
双向链表
每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小就方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点：
(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作，在任何位置插入/删除都是常数时间。
(3) 可在两端进行push、pop。
(4) 具有所有顺序容器都有的成员函数。
缺点：
(1) 不支持根据下标随机存取元素，即不支持[ ]操作符和vector.at()。
(2) 相对于verctor占用内存多。
list 容器还支持8个成员函数
push_front 在链表最前面插入
pop_front 删除链表最前面的元素
sort 排序 (list 容器的迭代器不支持完全随机访问，不支持 STL 的算法 sort，要用list自己的sort成员函数)
remove 删除和指定值相等的所有元素
unique 删除所有和前一个元素相同的元素
merge 合并两个链表, 并清空被合并的链表
reverse 颠倒链表
splice 在指定位置前面插入另一链表中的一个或多个元素；并在另一链表中删除被插入的元素
3 deque (double end queue)
双端队列
deque是在功能上合并了vector和list，所有适用于vector的操作都适用于deque
优点:
(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
deque 容器还支持2个成员函数
push_front 将元素插入到容器的头部
pop_front 删除头部的元素
使用区别：
1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
二、关联容器
内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。
1 multiset
使用时加头文件 #include <set>
常用成员函数
iterator find(const T & val); 在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。
iterator insert(const T & val); 将val插入到容器中并返回其迭代器。
void insert( iterator first,iterator last); 将区间[first,last)插入容器。
int count(const T & val); 统计有多少个元素的值和val相等。
iterator lower_bound(const T & val); 查找一个最大的位置 it,使得[begin(),it) 中所有的元素都比 val 小。
iterator upper_bound(const T & val); 查找一个最小的位置 it,使得[it,end()) 中所有的元素都比 val 大。
pair>iterator,iterator> equal_range(const T & val); 同时求得lower_bound和upper_bound。
iterator erase(iterator it); 删除it指向的元素，返回其后面的元素的迭代器(Visual studio 2010上如此，但是在C++标准和Dev C++中，返回值不是这样)。
2 set
使用时加头文件 #include <set>
插入set中已有的元素时，忽略插入。
3 multimap
使用时加头文件 #include <map>
multimap中的元素由 <关键字,值>组成，每个元素是一个pair对象，关键字就是first成员变量,其类型是Key。
multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less<Key> 定义关键字的“小于”关系。
常用成员函数
lower_bound(key)返回一个迭代器，指向键不小于k的第一个元素
upper_bound(key)返回一个迭代器，指向键大于k的第一个元素
multimap容器(authors)元素的两种插入方式（C++ Primer 中文第5版 P386）
multimap<string, string> authors;
//插入元素，关键字为 Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
//插入元素，关键字也为 Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"}); 注：
1 在multimap中，同一个键关联的元素相邻存放。
2 在使用 std::multimap时，发现没有明确的文档说明std::multimap容器是怎样的顺序存放的，即对同一个关键ID,先加入的放在前面还是后面，还是随机的。测试结果是先加的在前面。
相关参考：
关于std::multimap的相同键值插入顺序问题：http://www.xuebuyuan.com/1617500.html
multimap中一个key对应多个键值的查询处理：https://zhidao.baidu.com/question/918049459459983899.html
4 map
使用时加头文件 #include <map>
map容器(word_count)元素的五种插入方式（C++ Primer 中文第5版 P384）
word_count[word] = 1;
word_count.insert({word, 1});
word_count.insert(make_pair (word, 1));
word_count.insert(pair<string, size_t> (word, 1));
word_count.insert(map<string, size_t>::value_type (word, 1)); map容器元素的三种插入方式 http://blog.csdn.net/u012964993/article/details/21734657
三、pair 模板
pair 默认对first升序，当first相同时对second升序；
类模板：template <class T1, class T2> struct pair
参数：T1是第一个值的数据类型，T2是第二个值的数据类型。
功能：pair将一对值组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。
具体用法参考：
https://www.cnblogs.com/handsomecui/p/4946151.html
http://blog.csdn.net/duan19920101/article/details/50724840
四、容器适配器
可以用某种顺序容器来实现，(让已有的顺序容器以栈/队列的方式工作)
容器适配器都有3个成员函数:
• push: 添加一个元素;
• top: 返回栈顶部或队头元素的引用
• pop: 删除一个元素
容器适配器上没有迭代器，STL中各种排序, 查找, 变序等算法都不适合容器适配器
1 stack 栈 后进先出 (Last In First Out) 即 LIFO
头文件 <stack>
只能插入, 删除, 访问栈顶的元素
可用 vector, list, deque来实现
• 缺省情况下, 用deque实现
• 用 vector和deque实现, 比用list实现性能好
stack 的主要操作:
void push(const T & x); 将x压入栈顶
void pop(); 弹出(即删除)栈顶元素
T & top(); 返回栈顶元素的引用. 通过该函数, 可以读取栈顶元素的值, 也可以修改栈顶元素
2 queue 队列 先进先出 (First In First Out) 即 FIFO
头文件 <queue>
和stack 基本类似, 可以用 list和deque实现
缺省情况下用deque实现
queue 的主要操作:
push() 在末尾加入一个元素
pop() 删除第一个元素
front() 返回第一个元素
3 priority_queue 优先级队列 最高优先级元素总是第一个出列 可用堆实现
头文件 <queue>
和 queue类似, 可以用vector和deque实现
缺省情况下用vector实现
priority_queue 通常用堆排序技术实现, 保证最大的元素总是在最前面
• 执行pop操作时, 删除的是最大的元素
• 执行top操作时, 返回的是最大元素的引用
默认的元素比较器是 less<T>
其他总结参考：
http://blog.csdn.net/gogokongyin/article/details/51178378