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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/345553.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Effective Java 2 遇到多个构造器参数时要考虑使用构建器

第2个经验法则&#xff1a;用遇到多个构造器参数时要考虑使用构建器&#xff08;consider a builder when faced with many constructor parameters&#xff09; 上一条讨论了静态工厂相对于构造器来说有五大优势。但静态工厂和构造器有个共同的局限性:它 们都不能很好地扩展到…

开源网关Apache APISIX启用JWT身份验证

说明&#xff1a; 本文APISIX的配置参考我之前写的《Ubuntu部署Apache APISIX》 创建最小API 首先&#xff0c;确保你已经安装了.NET 6 SDK。创建文件夹“MinimalApiDemo”&#xff0c;VS Code打开文件夹&#xff0c;打开终端 dotnet new web -o MinimalApiDemo cd Minimal…

【JMeter接口测试工具】第二节.JMeter基本功能介绍(上)【入门篇】

文章目录 前言一、获取所有学院信息接口执行二、线程组的介绍 2.1 并发和顺序执行 2.2 优先和最后执行线程组 2.3 线程组的设置细节三、HTTP请求的介绍四、查看结果树的配置使用总结 前言 一、获取所有学院信息接口执行 我们先针对一条简单的接口进行执行&#…

代码随想录刷题笔记-哈希表篇

文章目录 242 有效的字母异位词(easy)力扣地址题目描述题目实例解题思路代码实现 383 赎金信(easy)力扣地址题目描述题目实例解题思路代码实现 49 字母异位词分组(mid)力扣地址题目描述题目实例解题思路代码实现 438 找到字符串中所有字母异位词(mid)力扣地址题目描述题目实例解…

3038. 相同分数的最大操作数目 I(Rust模拟击败100%Rust用户)

题目 给你一个整数数组 nums &#xff0c;如果 nums 至少 包含 2 个元素&#xff0c;你可以执行以下操作&#xff1a; 选择 nums 中的前两个元素并将它们删除。 一次操作的 分数 是被删除元素的和。 在确保 所有操作分数相同 的前提下&#xff0c;请你求出 最多 能进行多少次…

SpringBoot整合钉钉实现消息推送

前言 钉钉作为一款企业级通讯工具&#xff0c;具有广泛的应用场景&#xff0c;包括但不限于团队协作、任务提醒、工作汇报等。 通过Spring Boot应用程序整合钉钉实现消息推送&#xff0c;我们可以实现以下功能&#xff1a; 实时向指定用户或群组发送消息通知。自定义消息内容…

Python进阶-部署Flask项目(以TensorFlow图像识别项目WSGI方式启动为例)

本文详细介绍了如何通过WSGI方式部署一个基于TensorFlow图像识别的Flask项目。首先简要介绍了Flask框架的基本概念及其特点&#xff0c;其次详细阐述了Flask项目的部署流程&#xff0c;涵盖了服务器环境配置、Flask应用的创建与测试、WSGI服务器的安装与配置等内容。本文旨在帮…

【iOS】——Runtime学习

文章目录 一、Runtime介绍二、Runtime消息传递三、实例对象、类对象、元类对象四、isa_t结构体的具体实现五、cache_t的具体实现六、class_data_bits_t的具体实现七、Runtime消息转发动态方法解析备用接收者完整消息转发 一、Runtime介绍 iOS的Runtime&#xff0c;通常称为Obj…

使用汇编和proteus实现仿真数码管显示电路

proteus介绍&#xff1a; proteus是一个十分便捷的用于电路仿真的软件&#xff0c;可以用于实现电路的设计、仿真、调试等。并且可以在对应的代码编辑区域&#xff0c;使用代码实现电路功能的仿真。 汇编语言介绍&#xff1a; 百度百科介绍如下&#xff1a; 汇编语言是培养…

【通俗易懂的Python入门基础详细教程,可分享哦!!!】

Python&#xff0c;作为一种高级编程语言&#xff0c;自其诞生以来就以其独特的魅力吸引了无数开发者。以下是对学习Python的简要介绍&#xff1a; 一、Python的起源与发展 Python由荷兰计算机科学家吉多范罗苏姆于1990年代初设计&#xff0c;其设计初衷是作为ABC语言的替代品…

计算机网络复习题

期末题库复习1 一. 单选题&#xff08;共32题&#xff0c;100分&#xff09; 1. (单选题) 在脉冲起始时刻&#xff0c;有无跳变来表示“0”和“1”&#xff0c;且在脉冲中间时刻始终发生跳变的编码是&#xff08; &#xff09;。 A.非归零码 B.曼彻斯特编码 C.归零码 D.差…

Facebook革新:数字社交的下一个阶段

在数字化时代&#xff0c;社交网络已经成为人们生活中不可或缺的一部分。作为全球最大的社交网络平台之一&#xff0c;Facebook一直在不断创新&#xff0c;引领着数字社交的发展。然而&#xff0c;随着科技的不断进步和社交需求的变化&#xff0c;Facebook正在走向一个新的阶段…

k8s和deepflow部署与测试

Ubuntu-22-LTS部署k8s和deepflow 环境详情&#xff1a; Static hostname: k8smaster.example.net Icon name: computer-vm Chassis: vm Machine ID: 22349ac6f9ba406293d0541bcba7c05d Boot ID: 605a74a509724a88940bbbb69cde77f2 Virtualization: vmware Operating System: U…

STM32F103C8移植uCOSIII并以不同周期点亮两个LED灯(HAL库方式)【uCOS】【STM32开发板】【STM32CubeMX】

STM32F103C8移植uC/OSIII并以不同周期点亮两个LED灯&#xff08;HAL库方式&#xff09;【uC/OS】【STM32开发板】【STM32CubeMX】 实验说明 将嵌入式操作系统uC/OSIII移植到STM32F103C8上&#xff0c;构建两个任务&#xff0c;两个任务分别以1s和3s周期对LED进行点亮—熄灭的…

基于Python + Flask+ Mysq实现简易留言板

使用Python Flask Mysql实现简易留言板&#xff0c;包括网友编辑留言、修改留言&#xff0c;删除留言、分页显示四大功能。 写出留言板建设过程&#xff0c;包括开发使用工具、留言板模块设计、数据库设计、页面设计、关键技术。 留言板建设过程总结 一&#xff0e;开发使用…

一文学习yolov5 实例分割:从训练到部署

一文学习yolov5 实例分割&#xff1a;从训练到部署 1.模型介绍1.1 YOLOv5结构1.2 YOLOv5 推理时间 2.构建数据集2.1 使用labelme标注数据集2.2 生成coco格式label2.3 coco格式转yolo格式 3.训练3.1 整理数据集3.2 修改配置文件3.3 执行代码进行训练 4.使用OpenCV进行c部署参考文…

燃料电池汽车践行者

前言 见《氢燃料电池技术综述》 见《燃料电池工作原理详解》 见《燃料电池发电系统详解》 见《燃料电池电动汽车详解》 见《氢燃料电池汽车行业发展》 现代汽车&#xff08;中国&#xff09; 现代汽车集团&#xff0c;自1998年成立氢燃料电池研发小组以来深耕氢燃料电池技术&am…

Python爬虫入门与登录验证自动化思路

1、pytyon爬虫 1.1、爬虫简介 Python爬虫是使用Python编写的程序&#xff0c;可以自动访问网页并提取其中的信息。爬虫可以模拟浏览器的行为&#xff0c;自动点击链接、填写表单、进行登录等操作&#xff0c;从而获取网页中的数据。 使用Python编写爬虫的好处是&#xff0c;…

IGraph使用实例——线性代数计算(blas)

1 概述 在图论中&#xff0c;BLAS&#xff08;Basic Linear Algebra Subprograms&#xff09;并不直接应用于图论的计算&#xff0c;而是作为一套线性代数计算中通用的基本运算操作函数集合&#xff0c;用于进行向量和矩阵的基本运算。然而&#xff0c;这些基本运算在图论的相…

LangChain基础知识入门

LangChain的介绍和入门 1 什么是LangChain LangChain由 Harrison Chase 创建于2022年10月&#xff0c;它是围绕LLMs&#xff08;大语言模型&#xff09;建立的一个框架&#xff0c;LLMs使用机器学习算法和海量数据来分析和理解自然语言&#xff0c;GPT3.5、GPT4是LLMs最先进的代…