C++中的priority_queue和deque以及适配器

2024-06-07 02:36
文章标签 c++ 适配器 queue priority deque

本文主要是介绍C++中的priority_queue和deque以及适配器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++中的priority_queue和deque

  • 一丶 priority_queue
    • 1.1 priority_queue的介绍
    • 1.2 priority_queue的使用
    • 1.3 priority_queue的模拟实现
  • 二丶 deque
    • 2.1 deque的简单介绍
    • 2.2 deque的缺陷
    • 2.3 为什么要选择deque作为stack和queue的迭代器
  • 三丶 容器适配器
    • 3.1 什么是适配器
    • 3.2 STL标准库种stack和queue的底层结构

一丶 priority_queue

1.1 priority_queue的介绍

priority_queue的文档介绍

关于priority_queue:

1.优先级队列是一种容器适配器，它根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2.次上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，它提供一组特定的成员函数来访问其元素，元素从特定容器的"尾部"弹出，其称为优先队列的顶部。
4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器来访问，并支持以下操作：

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

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

注意：priority_queue的头文件是<queue>

1.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构。因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明接口说明
priority_queue()构造一个空的优先级队列
priority_queue(first, last)利用迭代器区间来构造一个优先级队列
empty()检测优先级队列是否为空，是返回true，否则返回false
top()返回优先级队列中最大(最小)元素，即堆顶元素
push(x)在优先级队列中插入元素x，插入后优先级队列会自动调整
pop()删除优先级队列中最大(最小)元素，即堆顶元素，删除完后优先级队列会自动调整

【注意】
1.默认情况下，priority_queue是大堆。
可以通过仿函数来实现小堆。

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件using namespace std;void TestPriorityQueue()
{// 默认情况下，创建的是大堆，其底层按照小于号比较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;//此时自堆顶(下标为0)到堆末尾(下标为size()-1)依此为9 8 7 6 5 4 3 2 1 0//默认为大堆顶for (auto& e : v){cout << q1.top() << " ";q1.pop();}cout << endl;cout << endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;for (auto& e : v){cout << q2.top() << " ";q2.pop();}cout << endl;}int main()
{TestPriorityQueue();return 0;
}

2.如果priority_queue中放自定义类型的数据，用户需要在自定义类型中提供>或者<的重载。(即提供可以比较大小的符合重载实现)。

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
//
using namespace std;class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载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;
}

1.3 priority_queue的模拟实现

通过堆priority_queue的底层结构就是堆，因此此处只需对堆进行通用的封装即可。

Priority_queue.h

#pragma once#include <vector>namespace bit
{//仿函数小于template <class T>class myless{public:bool operator()(const T& x, const T& y){return x < y;}};//仿函数大于template <class T>class mygreater{public:bool operator()(const T& x, const T& y){return x > y;}};//Compare -- 仿函数 通过只传递不同的仿函数对象 达到只传参就能修改功能和需求的目的template<class T, class Container = vector<T>, class Compare = myless<T>>class priority_queue{public://提供个默认构造 priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first; }//建堆 //从倒数第一个非叶子结点开始 向下调整 直至根节点向下调整完毕for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}//向上调整 构建大顶堆void adjust_up(int child){Compare comfunc;//由子节点求取得父节点：子节点-1然后除2int parent = (child - 1) / 2;//构建大堆//循环和结束条件：当子节点不为根结点时和当满足父节点大于子节点时while (child > 0){//当父节点小于子节点时  需要进行交换//if (_con[parent] < _con[child])if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);//更新当前父节点的位置 使其成为新的子节点//然后继续向上调整child = parent;parent = (child - 1) / 2;}//当父节点大于子节点时 可以直接breakelse{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}//删除时 需要自上而下 调整整个堆void adjust_down(int parent){Compare comfunc;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])){++child;}if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//pop的是优先级最高的元素void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}

Test.cpp

#include <iostream>
#include <queue>	//标准库中的priority_queue是在头文件queue中的 
using namespace std;
#include <algorithm>
#include "Priority_Queue.h" void test_priority_queue()
{vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };/*priority_queue<int> q1;for (auto& e : v)q1.push(e);*///迭代器区间//priority_queue<int> q1(v.begin(), v.end());对普通数组也可以（连续的物理空间）int a[] = { 3,2,7,6,0,4,1,9,8,5 };//priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));//切换成小堆 要利用仿函数        仿函数->greater<int>> q1priority_queue<int, vector<int>, greater<int>> q1(a, a + sizeof(a) / sizeof(int));//这个地方可能看上去有点奇怪  greate生成的是小堆while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;}void test_Mypriority_queue()
{vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };/*priority_queue<int> q1;for (auto& e : v)q1.push(e);*///迭代器区间//priority_queue<int> q1(v.begin(), v.end());对普通数组也可以（连续的物理空间）int a[] = { 3,2,7,6,0,4,1,9,8,5 };//bit::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));//切换成小堆 要利用仿函数bit::priority_queue<int, vector<int>, bit::mygreater<int>> q1(a, a + sizeof(a) / sizeof(int));//这个地方可能看上去有点奇怪  greate生成的是小堆while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;}int main()
{//标准库中的test_priority_queue();//我们自行模拟实现的test_Mypriority_queue();return 0;
}

二丶 deque

2.1 deque的简单介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，而且不需要搬移元素；与list比较，空间利用率比较高。
deque概念图
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。如下图：
在这里插入图片描述
双端队列底层是一段假想的连续空间，实际是分段连续的，为了维护其"整体连续"以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂。如下图：
在这里插入图片描述
那么deque是如何借助其迭代器维护其假想的连续结构呢？
在这里插入图片描述

2.2 deque的缺陷

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

2.3 为什么要选择deque作为stack和queue的迭代器

stack是一种后进先出的特殊线性结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；
queue是先进先出的特殊线性数据结构，只要具有push_back()和pop_front()操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中队stack和queue默认选择deque作为底层容器。
那么主要是因为：

1.stack和deque不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
-
2.在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合deque的优点，而完美地避开了其缺陷。

三丶 容器适配器

3.1 什么是适配器

适配器是一种设计模式(设计模式是一套被返回使用的丶多数人知晓的丶经过分类编目的丶代码设计经验的总结)，该种模式将一个类的接口转换成客户希望的另一个接口。
容器适配器概念图

3.2 STL标准库种stack和queue的底层结构

虽然stack和queue种也可以存放元素，但在STL种并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。
比如：
stack和queue的底层
关于利用底层容器deque实现stack和queue的博客请跳转：C++中的stack和queue

本博客仅供个人参考，如有错误请多多包含。
Aruinsches-C++日志-6/6/2024

这篇关于C++中的priority_queue和deque以及适配器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1037944。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2