本文代码已同步Github

一、deque的简单介绍

1、deque的特点

deque全称是double-ended queue，也叫双端队列。

它是一种序列式容器，最大的特点是：可以在头部和尾部高效地插入、删除元素。

和vector相比：

• vector适合尾插尾删，但头插头删效率较低
• deque头尾插入、删除效率都较高

和list相比：

• list不支持随机访问
• deque支持随机访问，比如dq[i]

不过，deque并不是真正连续的一整块空间，而是由多段连续的小空间组成，整体上通过迭代器维护成“看起来连续”的结构。

那么，如果deque真的既有vector的优点，同时还有list的优点；
那么我们数据结构直接学习deque就好了，为什么还要学习vector和list呢？

难道deque没有缺点？

下面我们便来介绍一下deque的底层，通过底层我们再来分析deque的优缺点；

2、deque的底层原理

我们先来思考一下：

vector的优点是：
1、尾插尾删效率不错，支持高效下标随机访问
2、物理空间连续，所以高速缓存利用率高

vector的缺点是：
1、需要扩容，扩容有代价
2、头部和中间插入删除效率低

接着来看list

list的优点是：
1、按需申请释放空间，不需要扩容
2、任意位置插入删除

list的缺点是：
1、不支持下标随机访问

deque既然想同时拥有两者的优点，那就需要在底层设计上下功夫

vector只是顺序存储，而list是链式存储

我们来看deque的结构：

核心结构就是中控数组+缓冲区

• 中控数组里面存放的是指针，每个指针指向一段连续的小空间；
• 每个指针指向的就是缓冲区，缓冲区内部是连续的，用来真正存放数据

我们通过一张图来理解

显然，deque是一段假想的连续空间，实际是多段连续小空间组成；

这样的结构用什么来维护呢？

普通的下标直接访问当然无法满足要求；答案就是迭代器来维护

通常一个迭代器需要维护四个信息

T*_cur;// 当前元素位置T*_first;// 当前缓冲区的起始位置T*_last;// 当前缓冲区的结束位置T**_node;// 当前缓冲区在中控数组中的位置

迭代器移动时：

• 如果当前缓冲区没有越界，直接移动_cur
• 如果_cur到达缓冲区边界，就通过_node找到下一个缓冲区
• 然后更新_first、_last和_cur

因此，迭代器不仅要记录当前元素，还要知道当前元素属于哪一段缓冲区，以及如何切换到下一段；

我们通过一张图来理解

注意⚠️：对于deque，实际上第一次插入数据，会将指针存放在中控数组的中间位置，而不是第一个位置

3、核心接口逻辑分析

那么deque是怎样借助迭代器来维护呢？

是通过两个迭代器，start和finish`` ``start和finish是两个 deque 迭代器，分别描述有效数据的起始位置和尾后位置。

下面我们来分析一下核心接口的实现逻辑：

1、对于push_back：
首先会找到finish的cur，此时cur指向的是尾后位置
判断cur==last，如果相等则需要重新开一个buff并更新finish，然后进行插入
如果不相等，则直接在cur位置插入即可，之后更新迭代器，时间复杂度为O(1)

2、对于pop_back：
首先找到finish的cur，如果删除之后当前buff已经没有有效元素，就需要释放buff；
否则就直接--cur即可，时间复杂度为O(1)

3、对于push_front：
首先找到start的cur，此时cur指向的是第一个有效元素的位置：
如果cur==first，需要新开一个buff并更新start，然后再进行插入
否则就直接--cur,然后在cur位置插入

4、对于pop_front：
首先找到start的cur，此时cur指向的是第一个有效元素的位置：
如果删除之后当前buff为空，需要释放buff同时将start指向下一个buff
否则就直接++cur，时间复杂度为O(1)

5、对于operator[]:
deque 支持随机访问，但由于底层不是一整块连续空间，因此不能像 vector 那样直接通过首地址 + index 访问;
它需要根据 index 计算目标元素位于哪个 buffer，以及在该 buffer 中的具体位置:
注意⚠️:计算时要以 start.cur 作为起点，而不是简单地从某个 buffer 的 first 位置开始。

下面来看insert和erase

6、对于insert：
传入的参数是迭代器pos，在pos前插入元素；
插入元素后，为了保持元素顺序，需要移动一部分元素；如果移动过程中超出当前缓冲区边界，则可能涉及其他缓冲区；
时间复杂度为线性级别，最差为O(N)

7、对于erase：
无论传入的参数是迭代器还是迭代器区间，都需要挪动数据进行覆盖删除；
时间复杂度为线性级别，最差为O(N)

4、deque的缺陷

与vector相比，deque的优势是：头插和头删时，不需要挪动数据，效率很高；
在扩容时，也不需要挪动大量数据；

与list相比，底层是分段连续空间，可以用[]来访问，空间利用率高

但是，deque同样不能够大量的调用insert和erase，这两个接口效率不高

deque 的明显缺点：遍历效率通常不如 vector

deque 的遍历效率相较于 vector 会低一些；
因为 vector 底层是一整块连续空间，迭代器移动时基本就是指针后移；
而 deque 底层是分段连续空间，迭代器在移动时需要判断是否到达当前 buff 的边界，必要时还要切换到下一个 buff

因此，当需要线性结构时，大多数情况下优先考虑vector和list

5、为什么stack和queue默认使用deque

stack是一种后进先出的特殊线性数据结构；
因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list；

queue是先进先出的特殊线性数据结构
只要具有push_back()和pop_front()操作的线性结构，都可以作为queue的底层容器，比如list

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

• stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
• 对于stack来说，deque比vector的效率高，尾插尾删都是O(1)，但deque扩容时不需要搬移大量数据；
• 对于queue来说，deque头删和尾插均为O(1)，相较于list，不需要为每个节点额外维护指针，而且内存使用率高；

综上，deque在作为stack和queue的底层容器时：
既满足了头尾操作的需求，又避开了自身不适合高效遍历的缺点。

二、priority_queue的介绍与使用

1、priority_queue的特点

首先我们先给出priority_queue的文档：priority_queue使用文档

接着我们来了解一下priority_queue

priority_queue是 C++ STL 中的容器适配器，本质上是堆（Heap）数据结构;

它的核心特点是优先级最高的元素总是位于队首（即top()），而出队顺序与入队顺序无关，只与优先级大小有关。

对于堆，我们在前面的数据结构中已经学习过，当时采用的是动态数组作为底层容器；

传送门：数据结构堆详解：原理、实现与应用、

和stack,queue一样，都是容器适配器，那么对于堆而言，数组就是很好的容器；

通过对数组进行包装，使其在逻辑结构上是一颗完全二叉树

2、priority_queue的核心接口

整理出核心接口

对于这些接口，我们都是在熟悉不过了；

简单来测试一下

3、大堆与小堆

注意⚠️：在默认情况下，priority_queue是大根堆；

怎样换成小根堆呢？

我们仔细来看其模板参数

有三个模板参数：
第一个是参数类型T；第二个是底层容器，默认是vector；第三个是一个仿函数

什么是仿函数呢？

仿函数（Functor）是 C++ 中一种行为类似函数的对象
它的本质是一个重载了函数调用运算符 operator() 的类或结构体，因此该类的实例可以像普通函数一样被调用。

本质上就是一个类，里面没有成员变量，重载了比较函数；

怎么调用呢？

创建对象后，使用**对象名（参数）**的语法，和函数调用完全一致；

我们先来实现一个默认的Less以及Greater仿函数

template<classT>classLess{public:booloperator()(constT&x,constT&y){returnx<y;}};template<classT>classGreater{public:booloperator()(constT&x,constT&y){returnx>y;}};

我们来测试一下

三、priority_queue的模拟实现

1、底层结构分析

我们来看文档中对于优先级队列底层容器的要求

要求是随机迭代器+高效的上述接口

首先想到的就是vector，完美符合上述要求

还有一个容器，同样符合要求，就是deque

deque同样也是随机迭代器，尾插尾删也是O(1)级别；

那为什么库里面选择了vector作为底层容器呢？

• priority_queue不需要deque的头部O(1)操作，vector就能满足要求
• 堆算法涉及大量的随机下标访问，vector效率更高
• vector的开销极小，而deque还需要中控数组map来维护

因此，选择vector是最划算的选择

下面来完成基础的框架搭建

//priority_queue.h#include<vector>template<classT>classLess{public:booloperator()(constT&x,constT&y){returnx<y;}};template<classT>classGreater{public:booloperator()(constT&x,constT&y){returnx>y;}};namespacestl{template<classT,classContainer=std::vector<T>,classCompare=Less<T>>classpriority_queue{private:Container _con;Compare _cmp;public:};}=

2、插入元素：向上调整

其实就是前面数据结构中的堆的向上调整算法

我们封装一个函数即可

voidAdjustUp(size_t child){size_t parent=(child-1)/2;while(child>0){//Less:父节点 < 孩子节点 -> 大根堆//Greater:父节点 > 孩子节点 -> 小根堆if(_cmp(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);child=parent;parent=(child-1)/2;}elsebreak;}}

3、删除堆顶：向下调整

也就是堆的向下调整算法

voidAdjustDown(size_t parent){size_t child=parent*2+1;while(child<_con.size()){if(child+1<_con.size()&&_cmp(_con[child],_con[child+1]))++child;//Less:父节点 < 孩子节点 -> 大根堆//Greater:父节点 > 孩子节点 -> 小根堆if(_cmp(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);parent=child;child=parent*2+1;}elsebreak;}}

4、核心接口实现

由于是适配器模式，因此是直接在底层容器基础上保留特定场景的接口即可

voidpush(constT&x){_con.push_back(x);AdjustUp(_con.size()-1);}voidpop(){std::swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}T&top(){return_con.front();}constT&top()const{return_con.front();}constsize_tsize()const{return_con.size();}boolempty()const{return_con.empty();}

接着来测试一下

五、总结

通过这两篇文章，我们学习了deque、stack、queue以及priority_queue。

对于deque，我们不仅学习了它的基本接口，更重要的是理解了它的底层设计
deque通过中控数组 + 多段缓冲区的方式，在保证随机访问能力的同时，实现了高效的头尾插入和删除
但是这种分段存储的结构也带来了额外的迭代器维护开销，因此deque虽然功能比较全面，却并不是一种适合大量遍历的容器。

进一步，我们理解了为什么stack和queue默认使用deque作为底层容器
stack和queue本质上都是容器适配器，它们并没有重新设计一套底层数据结构，而是在已有容器的基础上保留自己需要的接口
deque恰好能够很好地满足它们对于头尾操作的需求，同时又不需要使用自身不擅长的遍历功能。

对于priority_queue，我们进一步接触了 STL 中的另一种容器适配器
它本质上是对堆进行封装，通过底层容器存储数据，并利用堆的向上调整和向下调整来维护优先级关系
同时，通过仿函数可以灵活地改变元素之间的比较规则，从而实现大根堆和小根堆。

最后，通过模拟实现priority_queue，我们也能够更加直观地理解 STL 容器适配器的设计思想：

底层容器负责数据的存储，适配器负责限制和组织接口，而具体的数据结构算法则负责实现对应的功能。

从stack、queue到priority_queue，它们看似是不同的容器，实际上都建立在已有数据结构之上
理解这一点之后，我们在学习 STL 时就不应该只停留在“记住接口怎么用”，而应该进一步思考：

这个容器底层是什么？为什么选择它？接口又是如何利用底层结构实现的？

这也是学习 STL 和数据结构过程中非常重要的一种思维方式。

如果觉得有帮助，可以关注Github项目持续更新