C++_STL源码阅读：三大底层序列容器 Vector List Deque

你的名字 2022-05-24 07:45 189阅读 0赞

### 一 笨重的废话： ###

容器是STL体系的重要支撑点，承上启下，下基于Allocator进行memory的分配与管理，形成一个个的容器，对上呢，支撑Iterator和各种Algorithms，所以，Container才是STL的核心。

那么Container又分 序列式 + 关联式 两种；（跟 线性 vs 非线性 不是一个概念）；《STL源码剖析》是这么分类的；

序列式容器中，有线性的特点，比较常见的是三大底层： Vector List Deque

这三者为何重要？

*  使用广泛，事实上，人类世界的问题，大多还是一维线性问题；特别是编程语言实现时，不承认“多维数组”，都是嵌套一维一维的数组得到的；
 *  它们构成了其他次级容器，比如sList、stack、queue、max\_heap->priority\_queue；

这里面有两个“怪”点，可以稍微讨论下：

1 heap是我最不解的，请见下文第四部分；

2 “先重后轻”：List实际上是双向链表，即STL底层先弄了双向的链式容器，然后又在其上弄了个sList。。。。；类似情况还可见Deque，是个双端访问结构，然后在之上可以实现queue；如果先易后难呢，即先实现单向链表、单端访问的queue，后者这个问题（两个queue实现dqueu）多次在面试题中碰到（详见leetcode）；但STL没这么干。。。。

### 二 抄袭的重点内容 ###

好吧，要说重点了，重点是照搬一篇：https://blog.csdn.net/gogokongyin/article/details/51178378

文章说的足够详细了，简单总结下是：

*  Vector：类似C时代的数组，大段连续Memory； 需要**随机快速Read**，但不考虑Write成本；
 *  List：就是双向链表，Memory不连续； 需要考虑**Write操作成本**时选用， 但不能随即快速Read；
 *  Deque：分段式连续Memory，伪装整体连续；需要频繁的**双端操作**时，请考虑之；默认实现Stack 和 Queue；

以上三大底层容器，都是各自独立实现，相互之间没啥关系；

其中，List->sList，前者基于BiDirectional Iterator，后者基于Forward Iterator；

### **三 Deque的结构与实现：** ###

既然Deque这家伙是伪装的整体连续，实际上是多段Memory组成的，那么它是个三层结构，or二级跳：

*  Iterator层：start和finish两个Iterator； 每个Itartor又是个struct（cur、first、last、node）；
 *  Map：中控器，记录Iterator的node，是对应哪一段子缓冲区；
 *  Buffer & 各个分段Memory： 连续的子缓冲区

![20180523150529121][]

Deque成员和类继承关系如下：

![20180523151414849][]

### **四 Heap & Priority\_queue** ###

heap并非STL的标准组件，它通常可以基于array | vector | list来实现；

Heap在逻辑结构上是非线性的Tree，在物理结构上却可以用线性结构来存储；这挑战了线性结构，因为狭义的线性是数组元素顺序访问，但heap在线性结构上必须“跳跃”，即parent和child经常并非是相邻的两个元素。原因就在于，这其中用到了一个非常重要的Tree“完全二叉树”，它的重要性质 Index\_parent \*2 + (1or2) = Index\_child。这支撑了线性存储时父子元素的下标关系。

即： 非线性（Tree）的逻辑结构 <-- 完全二叉树 --> 线性的物理存储结构

分类：

*  min-heap
 *  max-heap -> **priority\_queue**

[20180523150529121]: /images/20220524/a9c2953beec94b73a19a4c8ec056babd.png
[20180523151414849]: /images/20220524/cf5d73d61fdc4785a96cb753cf2dc915.png