容器适配器 -------------- stack 、queue、priority_queue的使用以及 为什么默认使用deque作为底层容器?

2023-11-19

什么是适配器?
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

1.为什么将stack、queue和priority_queue称作为容器适配器?
虽然stack、queue、priority_queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将 其称为容器适配器,这是因为每个容器在底层都有自己的实现方式,而stack、queue、priority_queue只是 在底层将其他容器进行了封装,比如:
1.stack 栈
可以看出stack的底层是通过封装一个容器而实现的,c++默认的容器是deque。
在这里插入图片描述
2.queue 队列
与stack相同,queue底层也是通过封装别的容器实现的。
在这里插入图片描述
3.pirority_queue 优先级队列
在这里插入图片描述
2.具体的使用
stack,和queue的使用都很简单,大家简单看一下文档就可以容易的掌握,我们这里就重点看一下**priority_queue(优先级队列)**的使用方法:

  • 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  • 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
  • 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
  • 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问,并支持以下操作: empty():检测容器是否为空
    size():返回容器中有效元素个数
    front():返回容器中第一个元素的引用
    push_back():在容器尾部插入元素
    pop_back():删除容器尾部元素
  • 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指 定容器类,则使用vector。
  • 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作.
    2.1 priority_queue的使用
    优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成 堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意: 默认情况下priority_queue是大堆。
    在这里插入图片描述
    看下面的代码了解接口用法:
#include<vector>
#include<queue>
#include<functional>

void TestPriority_queue()
{
	//默认情况下,创建的是大堆,其底层按照小于号比较
	vector<int > v{3,2,7,6,0,4,1,9,8,5};

	
	//创建q1,并将 v中数据插入到 
	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; 
 } 

注意:
1.默认情况下,priority_queue是大堆。
2. 如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
例如:有一个日期类,Date,将多个Date对象,当如priority_queue中,则需要在Date类中对 > 或者 <,进行重载。
3. 有些情况下,用户可能需要提供比较器规则
看下面的例子:

class Less
 {
 	public:
 		bool operator()(const Date* pLeft,const Date* pRight)
 		{
 			return *pLeft < *pRight;
		 }
 };
 
 void TestPriority_queue()
 {
 	//自己制定的比较规则
	 priority_queue<Date*,vector<Date*>,Less> q;
	 q.push(&Date(2019,10,11)); 
	 q.push(&Date(2019,10,12)); 
	 q.push(&Date(2019,10,13)); 
	 cout<<*q.top()<<endl;
 }

3. 为什么选择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不仅效率高,而且内存使用率高。vector 当容量不够时,会开更大的空间,拷数据然后释放原来的空间,操作复杂。而deque会找另一块内存继续存放数据,效率高。
  • 相比较list,deque的插入操作会更加的高效,而且内存的使用率高,list会导致更多的内存碎片。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

容器适配器 -------------- stack 、queue、priority_queue的使用以及 为什么默认使用deque作为底层容器? 的相关文章

  • 军队文职(数学2+物理)——高等数学 7、导数的几何应用

    1 单调性与极值 设 f x 在 a b 内可导 若 则 f x 在 a b 内单调增加 减少 若 则 f x 在 a b 内单调不减 单调不增 极值 设函数 f x 在 a b 内有意义 是 a b 内的某一点 则如果存在一个点的邻域 使
  • 掌握 Android 自动化测试框架 UiAutomator & UiAutomator2

    掌握 Android 自动化测试框架 UiAutomator UiAutomator2 一 UiAutomator 简介 二 UiAutomator2 的诞生 三 UiAutomator2 的应用实践 总结 你是否曾经在进行 Android
  • 基于Matlab萤火虫算法优化订单分批问题

    基于Matlab萤火虫算法优化订单分批问题 订单分批优化问题是在供应链管理中常见的一个重要问题 涉及到如何合理地将一批订单分成若干个批次以最大程度地提高运输效率和降低成本 为了解决这一问题 我们可以借助萤火虫算法 Firefly Algor
  • 多线程环境下使用openssl

    openssl 官网说了 OpenSSL can safely be used in multi threaded applications provided that at least two callback functions are
  • 如何判断代码的好坏

    对于代码好坏的判断 是需要一定的标准来衡量 比如可读性 可维护性 可拓展性 简洁性等等 好的代码 无论是对于代码开发者来说 还是对于设备维护者来说都是赏心悦目的 而坏的代码则是让人一头雾水 心生胆怯 甚至在开发和维护阶段 因为修改或者重构代
  • MATLAB指纹识别系统[GUI,预警]

    一 课题介绍 随着生物识别技术的不断发展 人们发现每个人的指纹具有唯一性和不变性 因此指纹识别技术逐步发展为一种新的身份识别方式 并且凭借其良好的安全可靠性 大有取代传统身份识别方式的趋势 本文简要介绍了指纹识别的基本步骤 分别是指纹图像预
  • scala扁平化

    扁平化 将嵌套列表中的所有元素单独放到一个新列表中 嵌套列表 列表中元素均为列表的列表称之为嵌套列表 object 扁平化 def main args Array String Unit 嵌套列表 val list1 List List 1
  • 字节跳动(今日头条)小程序支付、支付宝、微信支付完整版

    字节跳动 今日头条 小程序支付 开通支付 官方参数组装 小程序代码 服务端 支付宝支付 微信H5支付 支付宝回调 微信H5支付回调 开通支付 开通支付就不做说明了 请直接查看官方文档 https microapp bytedance com
  • Maven pom.xml报错Multiple annotations found at this line: - Missing artifact log4j:log4j:jar:1.2.15:co

    Maven pom xml 报错 Multiple annotationsfound at this line Missing artifactlog4j log4j jar 1 2 15 compile Missing artifacto
  • jsp+Echarts实现图表可视化,连接数据库,从数据库拿数据

    实现可视化的图表 jsp mysql eclipse 从数据库拿数据改变表格的数据算是echarts的初始入门案例的升级版 想了解Echarts的各位大大 传送门 https echarts apache org examples zh e
  • Netty 4.0 实现心跳检测和断线重连

    一 实现心跳检测 原理 当服务端每隔一段时间就会向客户端发送心跳包 客户端收到心跳包后同样也会回一个心跳包给服务端 一般情况下 客户端与服务端在指定时间内没有任何读写请求 就会认为连接是idle 空闲的 的 此时 客户端需要向服务端发送心跳
  • python安装robotframework报错_荐Win10+python3.8+robot framework安装及遇见的问题

    前提 自己已经下载装好了Python3 x 下面是我逐步尝试搜索后出现的各类爆粗信息和截图 现在已经最后正确的方法汇总到文章前面 方便自取 Windows10系统 操作均在cmd命令行窗口内进行 1 装pip python m pip in
  • 【转】protoc-go-inject-tag 作用

    时间 2022 03 01 本文章向大家介绍 转 protoc go inject tag 作用 主要包括 转 protoc go inject tag 作用使用实例 应用技巧 基本知识点总结和需要注意事项 具有一定的参考价值 需要的朋友可
  • window10在vscode中配置conda出错解决办法

    Windows 10 VSCode激活conda虚拟环境失败解决方案 CommandNotFoundError Your shell has not been 码农家园
  • VS 2022使用报错(一)

    1 NET框架不兼容 发生背景 博主最近打开同事的源代码发现许多引用都无效了 中间我尝试删除了这些引用 在重新添加引用的时候都找不到这些了 最后发现是解决方案里面没有配置 NET框架 问题解决 配置 NET框架 右键项目属性 在目标框架里面
  • python搭建ip池(多线程)

    之前有讲过怎么搭建ip池 但由于单线程的效率太低 于是我们升级改造一下 将单线程变成多线程来搭建ip池 之前的方法可以参考一下 python搭建ip池 如果会简单的request和提取文字就可以直接不看 本文将会重点放在多线程的部分 过程分
  • 微软个人云端服务器在哪里找,云端的服务器在哪里

    云端的服务器在哪里 内容精选 换一换 智能边缘平台 Intelligent EdgeFabric 通过纳管用户的边缘节点 提供将云上应用延伸到边缘的能力 联动边缘和云端的数据 同时 在云端提供统一的边缘节点 应用监控 日志采集等运维能力 为
  • python基础:面向对象一些简单案例:计算圆的面积和周长,烤羊肉串

    1 计算圆的面积和周长 from math import pi class Circle def init self r self r r def zhouchang self return 2 pi self r def area sel
  • shell编程计算1-1000中所有3或5的倍数之和

    bin bash sum 0 int 1 while int lt 1000 do if int 3 0 int 5 0 then sum sum int fi let int done echo sum bin bash sum 0 fo

随机推荐

  • Spring Security 自定义用户认证

    一 PasswordEncoder 在 Configuration注解的类下注入bean import org springframework security crypto bcrypt BCryptPasswordEncoder imp
  • C++ 数据类型

    使用编程语言进行编程时 需要用到各种变量来存储各种信息 变量保留的是它所存储的值的内存位置 这意味着 当创建一个变量时 就会在内存中保留一些空间 可能需要存储各种数据类型 比如字符型 宽字符型 整型 浮点型 双浮点型 布尔型等 的信息 操作
  • AI绘图实战(六):制作一张庆祝五一劳动节的海报

    S AI能取代设计师么 I 至少在设计行业 目前AI扮演的主要角色还是超级工具 要顶替 除非甲方对设计效果无所畏惧 预先学习 安装及其问题解决参考 Windows安装Stable Diffusion WebUI及问题解决记录 运行使用时问题
  • JUMPSERVER+ZABBIX二次开发

    未完待续 1 apps assets models assets py 添加字段 zabbix group id models IntegerField null True blank True verbose name Zabbix Gr
  • Rust对文件的操作

    一 文件IO操作 在类unix系统中 一切都是文件 所以说广义的文件操作 其实包括很多 Socket 管道 内存映射等等 其实文件操作无论怎么变化 主流仍然是对外设的访问 计算机本身的组成 是一系列的硬件整合在一起的 单纯的只有CPU和内存
  • WSL 2是什么

    Windows Subsystem for Linux WSL 适用于 Linux 的 Windows 子系统是微软在Windows 10上提供的一项供用户快速运行Linux命令和工具的功能 相比前一代的WSL WSL 2提供更全的兼容性
  • 【vue2】vue2中引入jquery

    文章目录 安装 main js中引用 修改webpack配置 把以下三步做好 就不会出现 jquery is not define 的问题了 安装 npm i jquery S main js中引用 import from jquery V
  • 918. 环形子数组的最大和

    918 环形子数组的最大和 难度中等192 给定一个由整数数组 A 表示的环形数组 C 求 C 的非空子数组的最大可能和 在此处 环形数组意味着数组的末端将会与开头相连呈环状 形式上 当0 lt i lt A length 时 C i A
  • Docker安装RabbitMQ docker安装RabbitMQ完整详细教程

    Docker安装RabbitMQ docker安装RabbitMQ完整详细教程 Docker 上安装 RabbitMQ 3 12 的步骤 选择要安装的RabbitMQ 版本 1 拉取 RabbitMQ 镜像 2 创建并运行容器 3 Rabb
  • H5移动端便捷兼容测试方式

    一 准备 1 谷歌浏览器 2 H链接 3 主流设备分辨率 尺寸 二 步骤 1 打开F12 选择手机模式 2 看顶部设备信息 点击 县级弹窗最底部的edit进入编辑模式 3 添加想要测试的设备 设备的宽高需要按照手机的分辨率和像素值计算 以i
  • Oracle的三种高可用集群方案

    转载自 http www cnblogs com baiboy p orc2 html label1 Oracle的三种高可用集群方案 1 RAC Real Application Clusters 多个Oracle服务器组成一个共享的Ca
  • Java 基本数据类型之间的运算规则

    博主前些天发现了一个巨牛的人工智能学习网站 通俗易懂 风趣幽默 忍不住也分享一下给大家 点击跳转到网站 前言 这里只讨论七种基本数据类型变量间的运算 不包含boolean类型的 1 自动类型提升 结论 当容量小的数据类型的变量与容量大的数据
  • 水果识别系统-tensorflow项目

    介绍 水果识别系统 可识别15种水果 人工智能 机器学习 模式识别项目 编程语言Python 基于tensorflow机器学习库通过卷积神经网络对数据集进行训练 经过多次迭代训练得到模型 预测精度达到99 技术栈 python tensor
  • Spring AOP、拦截器、过滤器的区别

    一 区别与概念 Filter过滤器 拦截web访问url地址 Interceptor拦截器 拦截以 action结尾的url 拦截Action的访问 Spring AOP拦截器 只能拦截Spring管理Bean的访问 业务层Service
  • 解决dataframe格式表格的合并

    这几天遇到了一个关于表格合并的问题 其实问题很简单 对于两个表格df1和df2 取出df1的每一行特征和df2的每一行的特征合并 再将label合并 但是看了很多pandas关于表的合并 其并不适用到我这个问题 所以在此我想简单的总结一下关
  • 使用虚拟机安装ikuai软路由系统,搭建pppoe拨号服务器

    搭建pppoe拨号服务器 一 搭建ikuai软路由系统 1 VMware版本 2 ikuai官网上下载系统镜像 3 使用虚拟机安装ikuai系统 4 登录ikuai管理界面 二 安装win7虚拟机验证拨号功能 三 其他电脑要使用这个pppo
  • 【解决】使用IDEA创建springboot项目时,出现错误Cannot download ‘https://start.spring.io‘: connect timed out

    第一步创建项目 create New Project 第二步 错误的意思为 初始化失败 https start spring io 请检查URL 网络和代理设置 错误消息 无法下载 https start spring io 连接超时 解决
  • java数据迁移程序

    环境 mysql 目标 亿级数据迁移 最终耗时 1 2小时 服务器更佳 建议在晚上或者没人访问的情况下操作 思路 1 不能一下将所有数据 导入到目标数据表 耗时太久 且占用资源 所有就用程序批量执行 每次执行一个范围段 比如第一个线程 1
  • stm32局部变量定义过大导致栈溢出

    我在stm32做归一化以及自相关的项目时 一开始直接定义了长度为8192的数组 进行自相关 单片机一直没有反应 上位机不输出信息 然后我把点数改为128后就能正常输出了 并且在调试后 我发现最高能运行的点数是512 经过上网查询我终于发现了
  • 容器适配器 -------------- stack 、queue、priority_queue的使用以及 为什么默认使用deque作为底层容器?

    什么是适配器 适配器是一种设计模式 设计模式是一套被反复使用的 多数人知晓的 经过分类编目的 代码设计经验的总结 该种模式是将一个类的接口转换成客户希望的另外一个接口 1 为什么将stack queue和priority queue称作为容