引入

最近看了《STL源码剖析》的第 4 章和第 5 章，介绍了 C++ STL 中的序列式容器和关联式容器，本文将总结序列式容器的基础概念，不会详细它们的实现原理（想知道自个儿看书吧，我目前只想了解它们的基本原理，用的时候心里有数就行）。

容器概念

容器是存储数据的地方。C++ STL 容器是一些常见数据结构的实现。任何数据结构都是为了特定的算法服务的。

数据结构：数据的特定排列方式。

根据数据在容器中的排列方式，将容器分为序列式容器和关联式容器。

接下来将介绍序列式容器：array, vector, list, deque 以及它们的适配器：stack, queue, heap, priority_queue。

序列式容器与容器适配器

基础容器

STL 中的底层容器，可以作为其他容器的底层结构（array 除外）。

1.array

1. 内置的静态数组类型，空间大小指定后不能改变，元素存储在连续的线性内存空间，不具备动态扩容的能力，实际应用中几乎没有。

2. 其迭代器类型为 Random Access Iterator 随机访问迭代器。

2.vector

1. 动态数组，元素存储在连续的线性内存空间，其空间可以动态缩小或扩大，实际应用中非常普遍。

2. 动态扩容策略：申请更大的新空间（一般是旧空间大小的 2 倍），进行旧数据迁移，释放旧空间，\(O(n)\) 线性时间开销。

3. 动态缩容策略：只需要将表达 vector 数据结构的指针前移即可，\(O(1)\) 时间开销。

4. 为了避免频繁发生扩容，vector 有容量的概念，即它的实际大小比客户端需求量更大一些。

5. 引起 vector 内存空间重新配置的操作（如插入、删除操作），会导致之前定义的迭代器失效。

6. 其迭代器类型为 Random Access Iterator 随机访问迭代器，支持算术运算。

3.list

1. 双向循环链表，元素存储在非线性内存空间，实际应用中非常普遍。
2. list 不会重新配置空间，因此只有被删除元素的迭代器会失效，其他原先的迭代器不会失效。
3. 其迭代器类型为 Bidirectional Iterator 双向迭代器，只支持自增（++）和自减（--）运算。

4.deque

1. 双端队列，采用二级结构实现。一级结构称为中控器，是一个元素均为指针的数组，每个指针指向一段连续的线性空间，这段空间即为二级结构，真正存储数据的地方。

2. deque 的迭代器实现营造了一种“它是连续空间”的假象，其实它只是“一段一段的定量连续空间”。

3. deque 的扩容策略说起来简单：如果一级结构中控器仍有空间，就增加一个指针，指向一段新的连续空间用于存放新元素；否则申请更大的空间迁移一级结构的指针，然后如前所述。

4. deque 没有容量概念，因为如第 3 点所述，它可以随时申请一段新空间与旧空间“拼接”起来，不会发生“申请新空间 -> 迁移元素 -> 释放旧空间”（指的是二级结构即真正的数据不会发生迁移，一级结构中的指针还是会发生迁移的）。

5. 书中提到 deque 的迭代器比较复杂，若需要对 deque 排序，最好借助 vector 完成。

6. 其迭代器类型为 Random Access Iterator 随机访问迭代器，支持算术运算。

5.补充

在新的 C++ 标准中增加了 forward_list 单向链表，应该也算基础容器吧，但它的应用限制太多，只有在特定场合下才能使用。

容器适配器

以某种容器作为底层结构，改变其接口，使之符合某种特性。

1.stack

1. stack 栈的特性是“后进先出”，默认采用 deque 作为底层结构。

2. 其实 vector 和 list 也可以作为底层结构，可以根据应用场景分别测试这 3 种底层结构的性能差异进行选择。

3. stack 没有迭代器，因为提供迭代器会破坏它“后进先出”的特性。

2.queue

1. queue 队列的特性是“先进先出”，默认采用 deque 作为底层结构。

2. 其实 vector 和 list 也可以作为底层结构，但是显然不应该用 vector，因为 vector 删除首元素的时间开销是 \(O(n)\)，同样的操作 list 只要 \(O(1)\) 时间，因此实际应用中只需要测试 deque 和 list 作为 queue 底层结构时的性能差异。

3. queue 没有迭代器，因为提供迭代器会破坏它“先进先出”的特性。

3.heap

1. 我倾向于把 heap 归类为容器适配器，因为其依赖底层结构 vector 存储数据。众所周知的一个小技巧，使用数组表示堆，可以通过下标快速定位一个节点的父节点和子节点。

2. STL 中 heap 采用隐式表述的方式，不开放给外部使用，而是通过 heap 作为底层结构实现 priority_queue 优先队列开放给外部使用。

3. heap 算法中有一个 make_heap 算法，其作用是将一个 vector 中的元素进行调整使之符合堆特性。在 make_heap 算法中需要调用一个 perlocate down 算法下拉调整每个节点（在 vector 中从后往前寻找第一个非叶子节点开始），此时默认采用 < 小于比较操作，即较小的节点被下拉了，那么较大的节点自然成为父节点，因此默认情况下是最大堆。

4. heap 没有迭代器，不提供遍历功能，因为 heap 是完全二叉树，其元素需要遵循完全二叉树的排列规则。

4.priority_queue

1. 优先队列，默认采用 vector 作为底层结构，且默认采用 max_heap 实现。

2. 根据上述 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;
}

最后

如果你有疑惑，欢迎评论，我尽可能回复！

如果本文对你有帮助，点个赞吧，这是我坚持的动力！