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

智能推荐

常用的伪类和伪元素_常用伪元素有哪一些-程序员宅基地

文章浏览阅读1.4k次,点赞4次,收藏13次。常用的伪类:一个 CSS 伪类是以一个冒号( : )作为前缀,被添加到一个选择器末尾的关键字,可以让指定的元素在特定的状态呈现指定的样式。例如 :hover,当用户悬停在指定元素时,可以在这个状态给指定元素添加相应的样式,是在 DOM 树无法描述的状态下才能给元素添加样式。 :link 未访问的节点,通常用于 a 标签 :visited 已访问的节点,通常用于 a 标签 :hover 鼠标悬浮的节点 :active 当前选中的节点 :first-chil_常用伪元素有哪一些

数据挖掘面试 150 道题(附答案)_将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务-程序员宅基地

文章浏览阅读10w+次,点赞50次,收藏483次。单选题1. 某超市研究销售纪录数据后发现,买啤酒的人很大概率也会购买尿布,这种属于数据挖掘的哪类问题?(A)A. 关联规则发现B. 聚类C. 分类D. 自然语言处理2. 以下两种描述分别对应哪两种对分类算法的评价标准? (A)(a) 警察抓小偷,描述警察抓的人中有多少个是小偷的标准。(b) 描述有多少比例的小偷给警察抓了的标准。A. Precision, ..._将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务

【easyui】datagrid根据条件隐藏行_easyui datagrid 判断行隐藏-程序员宅基地

文章浏览阅读9.8k次,点赞4次,收藏3次。rowStyler: function (index, row) { if (row.isEnd == '1') {//条件 return 'display:none'; }else{_easyui datagrid 判断行隐藏

iis php5.6 mysql_Windows Server 2019 IIS10.0+PHP5.6+MySQL5.6环境搭建教程-程序员宅基地

文章浏览阅读423次。PHP版本:php5.6MySQL版本:MySQL5.6软件下载地址:php-5.6.31-nts-Win32-VC11-x64.zipvcredist2012_x64.exeMysql:https://dev.mysql.com/downloads/windows/installer/5.6.html 点击下载按钮,然后点击开始下载,不需要登录就可下载。安装IIS10.0打开左下角的开始菜单找到..._iis搭建mysql5.6

追溯计算机的本源,读电路与系统简史-程序员宅基地

文章浏览阅读3.9k次,点赞2次,收藏19次。元旦的假期和第一个周末的读书时光,比地铁阅读时光幸福了很多。无论是计算机的软硬件,还是人工智能系统,乃至IoT,都会涉及到这一古老而崭新的学科——电路与系统。读这本书,如同在追溯的时光里漫步。这里有一种强大的、迅速的、方便的原动力,它可以有各种用处,所有一切都由它造出来。它给我光,它给我热,它是我船上机械的灵魂。这原动力就是电。——儒勒凡尔纳人们对电的感知可以追溯的2000多年前..._电路与系统简史

加载webView 内存泄露 导致内存暴涨的几种解决方案_webview加载前端页面内存狂飙几百兆-程序员宅基地

文章浏览阅读3.1k次。加载webView导致内存泄露的原因是:Html中的js代码会引起内存泄露1 UIWebView *webView = [[UIWebViewalloc] initWithFrame:CGRectMake(0,64, 320,400)]; [webView loadRequest:[NSURLRequestrequestWithURL:url]];_webview加载前端页面内存狂飙几百兆

随便推点

常用字典_66,555,4444.333333,222222-程序员宅基地

文章浏览阅读7.9k次。huangyu888!@#$zhoujiakui223223jtserver1981@223wztelecom2008easygetyzdx123echina0228xiaxue123-$$4rf7uj3ed8ik!!changeme$$ebochai517qifengjc09001.1qa2ws3edwzcgame12wanzhonggamewanzhonggame..._66,555,4444.333333,222222

一文读懂服务器带外管理-程序员宅基地

文章浏览阅读1.9k次,点赞43次,收藏38次。服务器带外管理(Out-of-Band Management)是指在服务器正常运行时,通过专门的管理通道对服务器进行监控、配置和控制,而无需依赖服务器的主操作系统

Unity NGUI-程序员宅基地

文章浏览阅读344次。Unity 3.10.1 示例

【vue 引入cdn加载失败 解决办法】_联想r9000pcdn引入vue为什么超时-程序员宅基地

文章浏览阅读1.3k次。在项目index.html中放上生产环境下自动加载src下可以把文件放到自己服务器,本地加载 <% if(htmlWebpackPlugin.options.isProd){ %> <script src='file/20220519/vue.min.js' type='text/javascript'></script> <script src='file/20220519/vue-router.min.js' typ_联想r9000pcdn引入vue为什么超时

如何在云服务器上安装kali系统_华为的云服务器可以安装kaili-程序员宅基地

文章浏览阅读3.1k次。在华为云上进行安装一些其他的操作系统:以kali为例 准备阶段: 一台云服务器 除了一块云系统盘外的另一块云硬盘(如果没有可以临时进行购买一个) 操作: 00 购买成功的云硬盘在服务器控制台就是可以直接进行挂载的; 01 使用命令进行下载kali镜像或者进行上传镜像(都可以) wget https://mirrors.163.com/kali-images/kali-2021.3/kali-linux-2021..._华为的云服务器可以安装kaili

Android Dalvik虚拟机初识_每个dalvik虚拟机实例都是一个独立的进程空间-程序员宅基地

文章浏览阅读1k次。首先,让我们来思考下面几个问题:什么是Dalvik虚拟机?Dalvik VM与JVM有什么区别?Dalvik VM有什么新的特点?Dalvik VM的架构是怎么样的?首先,我得承认第一个问题问得很傻:什么是Dalvik虚拟机?没有人给出过一个明确的定义,但是,我们似乎可以从人们对Java虚拟机的描述中得到些信息。Java虚拟机(JVM)是一个虚构_每个dalvik虚拟机实例都是一个独立的进程空间

推荐文章

热门文章

相关标签