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