STL 2022 年 7 月 15 日

[C++-STL] deque的分析

STL源码, 实现 stack 和 queue 都使用了 deque 作为适配器. deque 是什么？它的结构是什么？为什么 Stack和 Queue要用它来作为适配器实现？

STL 容器约1205字 -- 阅读时间≈3分钟

STL源码实现 Stack 和 Queue 都使用了 deque 作为适配器

deque 是什么？它的结构是什么？为什么 Stack和 Queue要用它来作为适配器实现？

文档中的 deque

官方文档中这样解释 deque，而通俗来讲 deque 就是一个可以前插后插、前删后删的动态开辟的线性结构的容器

并且，这个 deque 拥有许多的成员函数:

这些成员函数功能，好像 list 容器也有，但是为什么 Stack、Queue的要由它作为适配器实现呢？

deque 结构介绍

我们都知道：

vector，占用的是连续的物理空间，所以它具有他以下优缺点：

优点：

尾插尾删，时间复杂度为 O(1)

可以随机访问

cpu高速缓存命中率高

缺点：

头插头删、中间插中间删，需要挪动数据，效率低

需要扩容消耗资源，并且有可能造成空间的浪费

list，占用的物理空间是不连续的，所以它具有以下优缺点：

优点：

任意位置插入删除，时间复杂度都是 O(1)

按需申请空间不会造成浪费

缺点：

不可随机访问

cpu高速缓存命中率低

其实，使用 vector 一般都是有需要随机访问的需求；使用 list 一般是有频繁不定位置插入数据的的需求

这两种容器，vector的随机访问 和 list 的插入删除数据 O(1)，是他们的绝对优势

而 deque 的结构实现，其实在一定程度上综合了 vector 和 list 两种容器结构的优点

list 是单个数据节点由指针相互连接

而 deque 的结构就像是 以固定长度的可以存放多个数据的vector 为一个的节点相互连接起来

但是并不是像list那样个节点存储相邻结点的地址，而是额外提供了一个vector来按顺序存放 deque中各个vector节点的地址

并且为了支持双端操作，还提供了两个迭代器分别指向首数据位置和末数据位置

所以 deque 的结构，大致上是这样的：

每段 vector 之间没有实际联系，而是由另一个容器存放每个vector的地址，且存放vector地址的容器也不是从首空间开始存放的，因为需要考虑到头插新vector 需要添加指针

知道了首元素位置与末元素位置，有知道了每个vector之间的顺序，且vector定长，就可以通过计算位置来实现随机访问

并且，在deque中尾插尾删、头插头删是不用挪动数据的，因为当vector满了之后，会添加新的 vector

这样的结构在一定程度上综合了 vector 和 list 的优点，但是都没有优到vector和list的那种程度

所以，综合一下，deque的优缺点有：

优点：

可以先计算位置来实现，随机访问，效率比list遍历快得多

头插尾插、头删尾删时间复杂度都是 O(1)

扩容代价较小

CPU高速缓存命中率较高，比 list 高

缺点：

中间插入删除效率不行

虽然可以随机访问，但是效率还是比vector差，因为需要先计算位置

所以，deque 其实就是一个功能多但是功能效率不是非常高的容器

问题：为什么 Stack 和 Queue 的实现，要用 deque 来做适配器

要回答这个问题，就得先明白 Stack 和 Queue 的结构、功能需要什么，也就是这两种容器的需求是什么？

栈 Stack

先进后出，只能尾插、尾删，一般由顺序表实现

队列 Queue

先进先出，只能尾插、头删，一般由链表实现

而 deque 功能齐全，头插尾插、头删尾删效率不差，结构综合了链表与顺序表

其实 deque 适合用于大量的头插尾插、头删尾删、偶尔随机访问的场景，而这正是 Stack 和 Queue 需要的

作者：哈米d1ch 发表日期：2022 年 7 月 15 日

[C++-STL] deque的分析

文档中的 deque

deque 结构介绍

问题： 为什么 Stack 和 Queue 的实现，要用 deque 来做适配器

问题：为什么 Stack 和 Queue 的实现，要用 deque 来做适配器