C++ STL也就是C++标准模板库，它是C++标准库的一部分。STL的目的是标准化组件，它实现了常用的数据结构和算法。本次主要讲下STL的几个序列容器。
1、vector
数据结构：一段连续的线性内存空间，元素连续存放。
通过分析源码，vector就是使用了3个迭代器来表示的：
通过灵活运用以上三个迭代器，vector容器可以轻松的实现诸如首尾标识、大小、容器、空容器判断等几乎所有功能，如：
vector元素的插入：
vector元素的移除和插入同理，需要将指定元素移除后，指定元素后面的数据往前移动覆盖数据，当然，移除最后一个元素时，不需要移动拷贝数据。
结论：
1、有一段连续的内存空间，并且起始地址不变，因此能够很好的支持随即存取，即[]取值操作符；
2、由于内存是连续的，在中间进行插入和删除时会造成内存块的拷贝，另外，当vector的内存空间不够时，需要重新申请一块足够大的内存并进行数据的重新拷贝，极其影响效率。
提升效率的方法：
1、预先分配足够大小的内存，避免因频繁的执行扩容影响效率；
2、尽量使用在最后面插入新元素的方法；即尽量使用push_back，不用或少用insert、erase方法。
2、list
数据结构：双向链表
总结：
1、具有vector和deque容器所不具备的优势，它可以在常规时间内，在序列已知的任何位置插入或删除元素。
2、无法通过位置来直接访问序列中的元素，即，不能索引元素。为了访问list内部的一个元素，必须一个一个的从第一个或最后一个开始遍历元素。
3、deque
数据结构：双向队列，可以在头尾两端插入或删除元素；
形象说来，Map中控器和缓存区的关系就类似于一本字典，字典以拼音首字母为索引，拼音首字母对应字典的页数范围就类似于Map中控器节点指向一段缓存区。假如要加入新的首字母，则又在字典插入一段该首字母对应的页数，同时将页数范围记录到字典首字母对应的页数中。
迭代器里面含有4个成员，连续空间开始地址（first），结束地址（last），空间中当前元素的地址（cur）以及连续空间地址在map中的位置（node）。这里的map不是stl里的map，而是一小块连续空间，其中每一个元素都是指针，指向另一段（较大的）连续线性空间（deque储存空间的主体），当map空间已满，需要再找一块更大的空间来作为map。first、last指向node所指缓冲区的头和尾，标示出缓冲区的边界，当iterator++（node向右移动）或iterator--（由node向左移动）到边界时，为了保持其连续线，需要跳到下一个缓冲区。
1、map中控器的大小如何确定？
map管理的节点个数是求max（8， 所需节点数+2），其中8是map的默认节点数；
所需节点数算法：元素个数/缓存区能存储的元素数 + 1；（缓存区默认是512字节的大小）
以要存储的是20个int类型的元素为例：
缓存区能存储 size = 512字节/sizeof(int) = 128个int类型的元素；
所需节点数nodeNum = 20/size + 1 = 1个节点；
则map管理的节点个数max(8, 1+2)即8个节点。
申请的map空间不够时，也需要重新配置更大的空间，将原来map里的指针拷贝过来，最后释放原来的空间。
扩容新map的分配规则：旧map.size() + max(旧map.size()，新增节点数) + 2.
若新增节点数为5，旧map的大小为8，则扩容后map的大小为：
8 + max(8,5) + 2 = 20;
2、deque数据的插入、删除是怎样的？
两端插入与删除：
以push_front为例，叙述头端插入过程：(画流程图太麻烦，直接以步骤的方式展现)
以pop_front为例，叙述头端删除过程：(画流程图太麻烦，直接以步骤的方式展现)
后端插入删除push_back()、push_front()步骤和前述同理，理解了前端就能理解后端的，不再赘述。
双端插入和删除不需要对已有元素进行移动，因此效率非常高。
中间插入与删除：
中间删除步骤和插入步骤类似，不再赘述。
注意：在中间插入和删除元素时，会导致指向deque元素的任何pointer、iterator失效。但是，deque的内存重分配优于vector，因为其内部结构不需要复制所有元素。
3、deque数据是否支持随机访问元素？
支持，它可以像vector一样使用[]访问任意元素，但是随机访问速度比不上vector快，因为它要内部处理堆跳转。
总结：
1、deque与vector最大的差异就是：deque是分段连续线性空间，随时可以增加一段新的空间；而vector是当内存不够时，需要重新分配、复制数据、释放原始空间。
2、比较优劣：
vector是可以快速地在最后添加删除元素，并可以快速地访问任意元素。
list是可以快速地在所有地方添加删除元素，但是只能快速地访问最开始与最后的元素
deque在开始和最后添加元素都一样快，并提供了随机访问方法。
由于deque不要求连续空间，所以可以保存的元素比vector更大，在前面和后面添加元素时都不需要移动其它块的元素，所以性能也很高。
3、如何选择：
在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector；
（2）如果你需要大量的插入和删除，而不关心随即存取，则应使用list；
（3）如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque；
4、queue
数据结构：一种先进先出的队列；底层容器默认为deque容器，list也可以实现，是单端和双端的区别。（严格来说，queue其实是适配器，而不是容器，因为它是对容器的再封装）
总结：
1、必须从一个口元素入队，另一个口元素出队。
2、不能随机存取，不支持遍历。
5、stack
数据结构：后进先出的栈；底层容器默认为deque容器，list也可以实现，是单端和双端的区别。（严格来说，stack其实是适配器，而不是容器，因为它是对容器的再封装）
stack和“撤销”操作是一样的，操作入栈，撤销时，最先出栈的不就是刚刚进行的操作吗。
总结：
1、必须从同一个口入栈出栈。
2、不能随机存取，不支持遍历。
6、priority_queue
数据结构：不论先进后进，优先级最高者先出的队列。但是如何定义“优先级”取决于我们，比如在医院，病情最严重的得到最先救治，操作系统进程调度中，优先级最高的得到优先调用。其内部使用的是堆排序。
想具体了解堆排序的推荐看下：
https://www.cnblogs.com/chengxiao/p/6129630.html
说下相关概念：
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
先写个简单的例子：
priority_queue<Type, Container, Functional>，模板申明带3个参数，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。Container必须是用数组实现的容器，比如vector, deque等等，但不能用 list（原因是堆排序是通过数组构建的堆）。STL里面默认用的是vector。
为了方便理解，提出这样一个需求：公司微波炉热饭顺序按年龄来确定热饭优先级，年长者优先热饭。
总结：
1、priority_queue只允许访问最顶端元素(priority_queue.top)，即堆顶元素；
2、priority_queue内部采取的最大堆的算法，每次弹出的元素都是优先级最高的元素，并且加入或弹出元素，内部元素都需要重新调整结构，即排序；
3、由于需要计算优先级，所以如果不是基本数据类型，则必须重载operator确定优先级。
参考链接：
https://juejin.im/post/5c9de926f265da30b53eb970
https://www.cnblogs.com/xiaogege/archive/2013/04/06/STL_deque.html
http://blog.chinaunix.net/uid-13909379-id-4902042.html
https://www.jianshu.com/p/65fdd3099238
