【C++】priority_queue和deque的使用与实现

priority_queue与deque的使用与模拟实现

✨前言：在C++ STL中，priority_queue和deque是两个重要的容器适配器，它们分别基于堆和双端队列的概念，为不同的应用场景提供了高效的解决方案。本文将深入探讨它们的使用方法、底层实现原理以及在实际开发中的应用选择。
📖专栏：【C++成长之旅】

目录

• priority_queue与deque的使用与模拟实现
  • 一、priority_queue
    • 1.1 介绍
    • 1.2 使用
    • 1.3 模拟实现
  • 二、deque
    • 2.1 介绍
    • 2.2 缺陷
  • 三、STL标准库中对于stack和queue的模拟实现
    • 3.1 为什么选择deque作为stack和queue的底层默认容器
    • 3.2 stack的模拟实现
    • 3.3 queue的模拟实现

一、priority_queue

1.1 介绍

【priority_queue的参考文档】

简单说明（翻译）：

1. priority_queue（优先级队列）底层的数据结构是堆，底层默认的容器是vector。对于堆不是很了解的建议看【堆的实现】，可见，堆一般为顺序存储，底层默认的容器是vector也就正常了。
2. priority_queue是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。可参考堆，可以在任何时候插入元素，但只能访问位于顶部的最大元素（即优先队列中最顶端的元素）。
3. 优先队列作为容器适配器实现，它使用特定容器类作为底层容器，并提供一组特定的成员函数来访问元素。元素从底层容器的"尾部"弹出，这个位置被称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他专门设计的容器类。该容器必须支持通过随机访问迭代器进行访问，并提供以下操作：

• empty()：检查容器是否为空
• size()：返回容器中元素的数量
• front()：返回容器中第一个元素的引用
• push_back()：在容器末尾插入元素
• pop_back()：删除容器末尾的元素

5. 标准容器类vector和deque满足这些要求。默认情况下，如果没有为特定的priority_queue实例指定容器类，则使用vector。
6. 需要支持随机访问迭代器是为了在内部始终保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来实现这一点。

1.2 使用

我们再对于前面的说明做一个总结：
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
我们可以来使用一下：

1. 默认情况下，priority_queue是大堆。

#include<iostream>#include<vector>#include<queue>#include<functional>// greater算法的头文件usingnamespace std;voidtest1(){// 默认情况下，创建的是大堆，其底层按照小于比较 vector<int> v{3,2,7,6,0,4,1,9,8,5}; priority_queue<int> q1;for(auto& e : v) q1.push(e); cout << q1.top()<< endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式 priority_queue<int, vector<int>, greater<int>>q2(v.begin(), v.end()); cout << q2.top()<< endl;}intmain(){test1();return0;}

对于它是如何在默认小于比较的情况下实现大堆的，我们后面的模拟实现会进一步说明。

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

classDate{friend ostream&operator<<(ostream& _cout,const Date& d);public:Date(int year =1900,int month =1,int day =1):_year(year),_month(month),_day(day){}booloperator<(const Date& d)const{return(_year < d._year)||(_year == d._year && _month < d._month)||(_year == d._year && _month == d._month && _day < d._day);}booloperator>(const Date& d)const{return(_year > d._year)||(_year == d._year && _month > d._month)||(_year == d._year && _month == d._month && _day > d._day);}private:int _year;int _month;int _day;}; ostream&operator<<(ostream& _cout,const Date& d){ _cout << d._year <<"-"<< d._month <<"-"<< d._day;return _cout;}voidtest2(){// 大堆，需要用户在自定义类型中提供<的重载 priority_queue<Date> q1; q1.push(Date(2018,10,29)); q1.push(Date(2018,10,28)); q1.push(Date(2018,10,30)); cout << q1.top()<< endl;// 如果要创建小堆，需要用户提供>的重载 priority_queue<Date, vector<Date>, greater<Date>> q2; q2.push(Date(2018,10,29)); q2.push(Date(2018,10,28)); q2.push(Date(2018,10,30)); cout << q2.top()<< endl;}intmain(){test2();return0;}

有兴趣可以练习一下：数组中的第K个最大元素

1.3 模拟实现

接下来我们模拟实现一下，在此之前，我们要对于堆这种数据结构有所了解，不懂的可以去我前面的关于堆的实现的链接。
那咱们就步入正题，对于priority_queue的实现其实就是将堆进行一定的封装，那我们就直接写吧。

#pragmaonce#include<vector>// 优先队列模板类// T: 元素类型, Container: 底层容器类型(默认vector), Compare: 比较器类型(默认less<T>)template<classT,classContainer= vector<T>,classCompare= less<T>>classpriority_queue{public:// 默认构造函数priority_queue(){}// 向下调整算法(堆化)// 用于维护堆性质，当某个节点不满足堆性质时，将其向下调整// a: 容器引用, n: 堆的大小, root: 要调整的根节点下标voidAdjustDown(Container& a,int n,int root){int parent = root;int child = parent *2+1;// 左孩子while(child < n){// 如果右孩子存在且比左孩子大(对于大堆)，选择较大的孩子if(child +1< n &&_comp(a[child], a[child +1])){++child;// 选择右孩子}// 如果父节点小于孩子节点(对于大堆)，需要交换if(_comp(a[parent], a[child])){swap(a[child], a[parent]); parent = child;// 继续向下调整 child = parent *2+1;// 新的左孩子}else{break;// 已经满足堆性质，退出循环}}}// 向上调整算法// 用于在插入新元素后维护堆性质，从叶子节点向上调整// child: 新插入元素的下标voidAdjustUp(int child){ Compare com;int parent =(child -1)/2;// 计算父节点下标while(child >0){// 如果父节点小于孩子节点(对于大堆)，需要交换//if (_c[parent] < _c[child])if(com(_c[parent], _c[child])){swap(_c[child], _c[parent]); child = parent;// 继续向上调整 parent =(child -1)/2;// 新的父节点}else{break;// 已经满足堆性质，退出循环}}}// 使用迭代器范围构造优先队列// first: 起始迭代器, last: 结束迭代器template<classInputIterator>priority_queue(InputIterator first, InputIterator last):_c(first, last)// 用迭代器范围初始化底层容器{int size = _c.size();// 从最后一个非叶子节点开始，向前逐个向下调整建堆int i =(size -2)/2;// 最后一个非叶子节点的下标while(i >=0){AdjustDown(_c, last - first, i); i--;}}// 判断优先队列是否为空boolempty()const{return _c.empty();}// 返回优先队列中元素个数 size_t size()const{return _c.size();}// 返回堆顶元素(非const版本) T&top(){return _c[0];// 堆顶元素总是在容器首部}// 返回堆顶元素(const版本)const T&top()const{return _c[0];}// 插入新元素voidpush(const T& x){ _c.push_back(x);// 在尾部插入新元素AdjustUp(_c.size()-1);// 从新插入的位置向上调整}// 删除堆顶元素voidpop(){swap(_c[0], _c[_c.size()-1]);// 将堆顶元素与最后一个元素交换 _c.pop_back();// 删除原来的堆顶元素(现在在尾部)AdjustDown(_c, _c.size(),0);// 从新的堆顶位置向下调整}private: Container _c;// 底层容器，用于存储堆元素 Compare _comp;// 比较器对象，用于元素比较};

对于堆比较了解的我们来说，实现很简单，这里我们就主要再来说明一下它为什么小于是大堆：

二、deque

2.1 介绍

在上篇文章【stack与queue】中，我们对于两者的模拟实现的时候底层容器其采用的是vector，我也提到，底层并未用vector作为默认容器，而是：

这就是deque（双端队列），现在我们就对于deque来进行简单的介绍吧。

deque(双端队列)：是一种双开口的"连续"空间的数据结构。
双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

那么deque到底是怎么实现的呢。难道deque是一块连续的空间，然后怎么样怎么样……

其实，**deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。**其
底层结构如下图所示：

可见，双端队列底层采用分段存储的方式，实际内存是不连续的。所以为了给用户提供连续空间和随机访问的错觉，deque的迭代器承担了屏蔽底层复杂性的重任。

我们也可以来看一下deque的迭代器实现，如下图:

解释：

我们可以看出，中控器其实是一个指针数组，每个指针指向一个缓冲区，当缓冲区不够时可以动态增长。迭代器的指针：
cur: 指向当前元素
first: 指向当前缓冲区的起始位置
last: 指向当前缓冲区的结束位置
node: 指向中控器中当前缓冲区对应的指针

那deque是如何借助其迭代器维护其假想连续的结构呢？

其实，在deque的底层，除了中控数组以外，还有两个迭代器，start 与 finish 迭代器。如下图：

这样，在对于头插和头删以及尾插、尾删的时候，就会很快O(1)。

这样一看，deque与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
deque的核心特点就是：

• 头尾插入删除时间复杂度O(1)
• 支持随机访问，但效率低于vector
• 底层采用"中控器+缓冲区"的分段存储方式
  但是，它也是有缺陷的。

2.2 缺陷

尽管deque功能强大，但也有明显缺陷：

1. 随机访问效率较低（需要计算缓冲区位置）
2. 迭代器失效规则复杂
3. 内存使用效率不如vector
4. 缓存局部性较差
   因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

三、STL标准库中对于stack和queue的模拟实现

3.1 为什么选择deque作为stack和queue的底层默认容器

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的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。
下面我们就仿照标准库来进行stack和queue的模拟实现。

3.2 stack的模拟实现

#include<deque>template<classT,classCon= deque<T>>classstack{public:stack(){}voidpush(const T& x){ _c.push_back(x);}voidpop(){ _c.pop_back();} T&top(){return _c.back();}const T&top()const{return _c.back();} size_t size()const{return _c.size();}boolempty()const{return _c.empty();}private: Con _c;};

3.3 queue的模拟实现

#include<deque>template<classT,classCon= deque<T>>classqueue{public:queue(){}voidpush(const T& x){ _c.push_back(x);}voidpop(){ _c.pop_front();} T&back(){return _c.back();}const T&back()const{return _c.back();} T&front(){return _c.front();}const T&front()const{return _c.front();} size_t size()const{return _c.size();}boolempty()const{return _c.empty();}private: Con _c;};

如果本文对您有启发：
✅ 点赞 -让更多人看到这篇硬核技术解析 ！
✅ 收藏 -实战代码随时复现
✅ 关注 -获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨