C++ STL队列queue和优先队列priority_queue的底层实现和用法_c++ queue底层实现-程序员宅基地

技术标签: c++  java  # C++的STL详解  蓝桥杯  

STL其他内容解析:关于C++中STL的理解和应用


首先要知道,队列和优先队列都是容器适配器,即在已有的容器之上封装而成。

关于容器适配器:C++ STL中的容器适配器详解


队列queue

队列queue是一种先进先出的数据结构,并且添加元素只能添加在尾部,删除元素只能删除首元素。

常用操作:

q.push(x);  //入队:将x压入队列的末端
q.pop(); 	//出队:弹出队列的队首元素,不返回任何值
q.front();  //返回队首元素
q.back();	//返回队尾元素
q.empty();  //判断队列是否为空
q.size();   //返回队列的元素个数

底层实现:deque

在STL中队列queue的默认容器是双端队列 deque,也可以使用 list 自定义队列,但是vector不行,因为vector不能提供删除第一个元素这个操作。

优先队列priority_queue

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先出队的行为特征。

优先队列实现了类似堆的功能(其实底层就是用堆实现的)。

常用操作:

q.push(x);  //入队
q.pop(); 	//出队
q.top();  //返回队内优先级最高的元素
q.empty();  //判断队列是否为空
q.size();   //返回队列的元素个数

自定义优先队列:

STL默认使用 < 操作符来确定对象之间的优先级关系(也就是从大到小排序,默认大根堆)。

priority_queue<int> q;  //默认大根堆

小根堆:

priority_queue<int,vector<int>,greater<int>> q;  //自定义小根堆

其中,第一个参数为数据类型,第二个参数为容器类型。第三个参数为比较函数。

结构体:需要重载运算符<

# include<iostream>
#include<queue>
using namespace std;

struct orz{
	int sum;
	int x,y;
};
 
priority_queue<orz> q;

operator <(orz a,orz b){
	return a.sum>b.sum;
}

int main(){
	for (int i=1; i<=10; i++){
		orz p;
		p.x=i;
		p.y=i;
		p.sum=i;
		q.push(p);
	}
	while (q.size()!=0){
		orz p=q.top();
		cout<<p.sum<<endl;
		q.pop();
	}
	
	return 0;
}

更常用的写法:对结构体排序 

friend bool operator

    struct Edge {
        int u;
        int v;
        int w;
        friend bool operator <(const Edge &x, const Edge &y)
        {
            return x.w > y.w;
        }
    };
    Edge t[1000005];
    priority_queue<Edge> q;

底层实现:

优先队列的底层是用实现的。
在优先队列中默认存放数据的容器是vector,在声明时也可以用deque(双向队列)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_21989927/article/details/109406646

智能推荐

S7-200SMART PLC中进行MODBUS RTU通信的3种方法(1)_smart 200 modbus rtu轮询-程序员宅基地

文章浏览阅读2.6k次。S7-200SMART PLC中进行MODBUS RTU通信的3种方法(1)_smart 200 modbus rtu轮询

计算机浮点数乘法过程,计算机中单精度浮点数运算详解-程序员宅基地

文章浏览阅读2.1k次。写在前面在PA_2019fall中有一项任务是完成CPU中的浮点数运算,这也是我第一次认真的思考了一下真实的计算机中CPU是如何进行的浮点数运算在写PA的过程中一头雾水,从迷茫,到困惑,到弄懂,到完成,中间经历了各种坎坷,又无奈于手上的资料仅仅只有一个Guide和i386,剩下不会的地方全靠百度于是就诞生了这一篇博客,把其中的过程给大家讲的明明白白的!预备知识什么是浮点数?浮点数表示的是一个数字,..._单精度浮点数乘法

蓝牙BLE动态广播信号模拟,mac自定义动态广播修改中继模块,解决行业动态蓝牙设备(比如宇泛企业、DD等)教学方案_dd蓝牙广播-程序员宅基地

文章浏览阅读4.5k次。蓝牙BLE动态广播信号模拟,mac自定义动态广播修改中继模块,解决行业动态蓝牙设备(比如宇泛企业、DD等)教学方案提示: 此学习方法适用于蓝牙基站(动态RAW广播)提示:以下是本篇文章正文内容,可供参考一、什么是蓝牙动态广播?示例:下面以某一款ibeacon基站为例。02 01 06 03 03 3C FE 17 FD 00 03 B7 00 05 73 62 C8 8E 00 00 00 C4 E8 A6 E4 F0 01 10 64 1F 0E固定内容 17 FD 00 03 B7 00_dd蓝牙广播

pdm导出mysql脚本_用powerdesigner 使 pdm生成sql脚本及反向工程生成ER图-程序员宅基地

文章浏览阅读273次。3、如果选择生成脚本,你可以得到一个你命名的SQL文件;4、如果要通过ODBC连接目标数据库生成表,你要先定义好ODBC的链接。5、建议用生成SQL脚本方式一、PowerDesigner生成sql问题生成sql的方法是 Database -->Generate Database (Ctrl + G ) 但是提示Could not load VBScript engine.Check VBSc..._pdm导出er图

大班科学计算机的发明应用教案,大班科学活动神奇的圈教案-程序员宅基地

文章浏览阅读97次。大班科学活动神奇的圈教案作为一位不辞辛劳的人民教师,总归要编写教案,教案有助于学生理解并掌握系统的知识。那么什么样的教案才是好的呢?下面是小编为大家整理的大班科学活动神奇的圈教案,欢迎阅读,希望大家能够喜欢。大班科学活动神奇的圈教案1一、活动目标:1.探索将长条纸制作成麦比乌斯圈,等分不同的次数后会产生不同的现象。2.大胆与同伴交流自己的操作方法和发现,对科学现象感兴趣。二、活动准备:1.人手两张..._大班计算机的发明可以延伸到

Shopee新加坡最全笔试面经汇总+内推持续进行中_shopee笔试-程序员宅基地

文章浏览阅读3.2k次,点赞2次,收藏15次。更多关于笔试、面经、内推、岗位相关的消息, 请在公众号“坡县互联网内推”中获取。【一面】新加坡一般是HR面为第一面,这点可能和国内大部分公司都不一样。一般是半小时英文面试。不过不用怕,很多国内的同学担心自己的口语问题,如果实在对自己的口语没有信心,可以在HR发邮件约定面试时说明情况。下面举的是技术岗的例子,非技术岗不会问技术问题。5分钟的英文自我介绍:自我介绍尽量丰富一些,既要包含自己以往的经历,也要体现自己对shopee的了解。面试毕竟是一个双向选择的过程。面试shopee的原因:关于shope_shopee笔试

随便推点

“菩提子”是菩提树的种子吗?-程序员宅基地

文章浏览阅读1.8k次。“菩提子”是菩提树的种子吗? 现在文玩市场上门槛最低销售最多的产品莫过于各种菩提子了,随便找一家文玩市场和商铺进去看看基本都能看见大小形状各异的疑似植物器官的东西被冠以“某某菩提子”之名。 对于这些菩提子最常被问到的一个问题就是:这是不是菩提树的种子?答案是否定的,菩提树Ficus religiosa是桑科榕属的植物,开花为隐头花序,果实为

带你玩转Glide的回调与监听-程序员宅基地

文章浏览阅读695次。大家早上好,今天我们继续学习Glide。 在上一篇文章当中,我带着大家一起深入探究了Glide的缓存机制,我们不光掌握了Glide缓存的使用方法,还通过源码分析对缓存的工作原理进行了了解。虽说上篇文章和本篇文章的内容关系并不是很大,不过感兴趣的朋友还是可以去阅读一下 深入探究Glide的缓存机制 。 今天我们就先从缓存这一块内容开始入手吧。不过今天文章中的源码都建在上一篇源码分析的基础之上,还_判断 glide 监听

Flutter 鼠标右键-程序员宅基地

文章浏览阅读3k次。import 'package:universal_html/html.dart';void main() {​ // Disable the default browser behavior for right clicking // 屏蔽浏览器默认的右键点击事件 window.document.onContextMenu.listen((evt) => evt.preventDefault());​ runApp(MyApp());}//具体使用Contain._flutter 鼠标右键

SpringCloud之负载均衡_f5 lb-程序员宅基地

文章浏览阅读391次。负载均衡(LB)的分类集中式LB(偏硬件):即在服务的消费方和提供方之间使用独立的LB设施(可以是硬件,如F5,也可以是软件,如nginx),由该设施负责把访问请求通过某种策略转发至服务的提供方;进程式LB(偏软件):将LB逻辑集成到消费方,消费方从服务注册中心获知有哪些地址可用,然后自己再从这些地址中选择出一个合适的服务器。Ribbon就属于进程内LB,它只是一个类库, 集成于消费方..._f5 lb

数字电路设计--用3个开关控制一个电灯_logisim用74138设计一个照明灯电路,要求改变任一个开关状态,都可以控制照明灯由亮-程序员宅基地

文章浏览阅读5.2w次,点赞22次,收藏100次。题目要求:用数据选择器设计一个用 3 个开关控制一个电灯的逻辑电路,当改变任何一个开关的状态,都能控制电灯由亮变灭或由灭变亮。最好用 74LS151。题目链接:http://zhidao.baidu.com/question/1689762126759866268.html-----------------------以前,做而论道曾设计过这样的电路,可见:http://hi.baidu.com/_logisim用74138设计一个照明灯电路,要求改变任一个开关状态,都可以控制照明灯由亮

java模拟jvm(常量池的解析)_inttag-程序员宅基地

文章浏览阅读153次。java实现字节码解析1(常量池的解析)大体的思路就是按照之前写的那篇字节码解析里面所描述的方式。https://blog.csdn.net/qq_43147121/article/details/108035464这里面有几个要我们用到位运算来处理基本类型的地方,可以看我前面那篇Java基本类型的博客。https://blog.csdn.net/qq_43147121/article/details/108145123下面直接贴代码:1.这是一个工具类,主要就是将byte数组转换为各种基本类型_inttag

推荐文章

热门文章

相关标签