引入
最近看了《STL源码剖析》的第 4 章和第 5 章，介绍了 C++ STL 中的序列式容器和关联式容器，本文将总结序列式容器的基础概念，不会详细它们的实现原理（想知道自个儿看书吧，我目前只想了解它们的基本原理，用的时候心里有数就行）。
容器概念
容器是存储数据的地方。C++ STL 容器是一些常见数据结构的实现。任何数据结构都是为了特定的算法服务的。
数据结构：数据的特定排列方式。
根据数据在容器中的排列方式，将容器分为序列式容器和关联式容器。
接下来将介绍序列式容器：array, vector, list, deque 以及它们的适配器：stack, queue, heap, priority_queue。
序列式容器与容器适配器
基础容器
STL 中的底层容器，可以作为其他容器的底层结构（array 除外）。
1.array
-
内置的静态数组类型，空间大小指定后不能改变，元素存储在连续的线性内存空间，不具备动态扩容的能力，实际应用中几乎没有。
-
其迭代器类型为
Random Access Iterator随机访问迭代器。
2.vector
-
动态数组，元素存储在连续的线性内存空间，其空间可以动态缩小或扩大，实际应用中非常普遍。
-
动态扩容策略：申请更大的新空间（一般是旧空间大小的
2倍），进行旧数据迁移，释放旧空间，$O(n)$ 线性时间开销。 -
动态缩容策略：只需要将表达
vector数据结构的指针前移即可，$O(1)$ 时间开销。 -
为了避免频繁发生扩容，
vector有容量的概念，即它的实际大小比客户端需求量更大一些。 -
引起
vector内存空间重新配置的操作（如插入、删除操作），会导致之前定义的迭代器失效。 -
其迭代器类型为
Random Access Iterator随机访问迭代器，支持算术运算。
3.list
- 双向循环链表，元素存储在非线性内存空间，实际应用中非常普遍。
list不会重新配置空间，因此只有被删除元素的迭代器会失效，其他原先的迭代器不会失效。- 其迭代器类型为
Bidirectional Iterator双向迭代器，只支持自增（++）和自减（--）运算。
4.deque
-
双端队列，采用二级结构实现。一级结构称为中控器，是一个元素均为指针的数组，每个指针指向一段连续的线性空间，这段空间即为二级结构，真正存储数据的地方。
-
deque的迭代器实现营造了一种“它是连续空间”的假象，其实它只是“一段一段的定量连续空间”。 -
deque的扩容策略说起来简单：如果一级结构中控器仍有空间，就增加一个指针，指向一段新的连续空间用于存放新元素；否则申请更大的空间迁移一级结构的指针，然后如前所述。 -
deque没有容量概念，因为如第 3 点所述，它可以随时申请一段新空间与旧空间“拼接”起来，不会发生“申请新空间 -> 迁移元素 -> 释放旧空间”（指的是二级结构即真正的数据不会发生迁移，一级结构中的指针还是会发生迁移的）。 -
书中提到
deque的迭代器比较复杂，若需要对deque排序，最好借助vector完成。 -
其迭代器类型为
Random Access Iterator随机访问迭代器，支持算术运算。
5.补充
在新的 C++ 标准中增加了 forward_list 单向链表，应该也算基础容器吧，但它的应用限制太多，只有在特定场合下才能使用。
容器适配器
以某种容器作为底层结构，改变其接口，使之符合某种特性。
1.stack
-
stack栈的特性是“后进先出”，默认采用deque作为底层结构。 -
其实
vector和list也可以作为底层结构，可以根据应用场景分别测试这 3 种底层结构的性能差异进行选择。 -
stack没有迭代器，因为提供迭代器会破坏它“后进先出”的特性。
2.queue
-
queue队列的特性是“先进先出”，默认采用deque作为底层结构。 -
其实 vector 和 list 也可以作为底层结构，但是显然不应该用 vector，因为 vector 删除首元素的时间开销是 $O(n)$，同样的操作 list 只要 $O(1)$ 时间，因此实际应用中只需要测试
deque和 list 作为queue底层结构时的性能差异。 -
queue没有迭代器，因为提供迭代器会破坏它“先进先出”的特性。
3.heap
-
我倾向于把
heap归类为容器适配器，因为其依赖底层结构 vector 存储数据。众所周知的一个小技巧，使用数组表示堆，可以通过下标快速定位一个节点的父节点和子节点。 -
STL 中
heap采用隐式表述的方式，不开放给外部使用，而是通过heap作为底层结构实现priority_queue优先队列开放给外部使用。 -
heap算法中有一个 make_heap 算法，其作用是将一个vector中的元素进行调整使之符合堆特性。在make_heap算法中需要调用一个perlocate down算法下拉调整每个节点（在vector中从后往前寻找第一个非叶子节点开始），此时默认采用<小于比较操作，即较小的节点被下拉了，那么较大的节点自然成为父节点，因此默认情况下是最大堆。 -
heap没有迭代器，不提供遍历功能，因为heap是完全二叉树，其元素需要遵循完全二叉树的排列规则。
4.priority_queue
-
优先队列，默认采用
vector作为底层结构，且默认采用max_heap实现。 -
根据上述
heap的make_heap算法所述，采用<小于比较操作得到的是最大堆，相反采用>大于比较操作得到的是最小堆。
#include <`queue`>
int main() {
priority_`queue`<int, vector<int>, less<int>> pq1; // 最大堆
priority_`queue`<int, vector<int>, greater<int>> pq2; // 最小堆
return 0;
}