STL序列式容器使用概念总结-创新互联

引入

最近看了《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 ) O(n) O(n) 线性时间开销。

3. 动态缩容策略：只需要将表达vector数据结构的指针前移即可， O ( 1 ) O(1) 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 ) O(n) O(n)，同样的操作 list 只要 O ( 1 ) O(1) 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`, less>pq1;    // 大堆
    priority_`queue`, greater>pq2; // 最小堆
    return 0;
}

最后

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

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：STL序列式容器使用概念总结-创新互联
URL分享：http://cxhlcq.com/article/csppic.html