当前位置: 首页 > news >正文

【C++】priority_queues(优先级队列)和反向迭代器适配器的实现

目录

  • 一、 priority_queue
    • 1.priority_queue的介绍
    • 2.priority_queue的使用
      • 2.1、接口使用说明
      • 2.2、优先级队列的使用样例
    • 3.priority_queue的底层实现
      • 3.1、库里面关于priority_queue的定义
      • 3.2、仿函数
        • 1.什么是仿函数?
        • 2.仿函数样例
      • 3.3、实现优先级队列
        • 1. 1.0版本的实现
        • 2. 2.0版本的实现
  • 二、反向迭代器适配器

前言

继上一篇stack和queue我们讲解了其实现原理,里面也提到了容器适配器的概念,本篇我们要讲的优先级队列,也是一种容器适配器,另外我们再顺带讲一下反向迭代器,这个也是一个容器适配器哦,废话不多说,我们直接切入正题

一、 priority_queue

1.priority_queue的介绍

priority_queue他是一种容器适配器,但其实他底层和堆差不多,接口和堆也非常像,功能也是,默认情况下是大堆,你也可以用仿函数把他改成小堆

它的接口有以下几个:

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

priority_queue的底层是堆,堆其实是完全二叉树,而完全二叉树的物理结构又是类似数组这种连续的物理空间,所以说适配priority_queue的容器要能够随机访问下标,需要支持随机访问迭代器,以便始终在内部保持堆结构,一般我们用vector作为它的默认容器,deque也可以

2.priority_queue的使用

2.1、接口使用说明

在这里插入图片描述

2.2、优先级队列的使用样例

priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}
//打印结果是5,4,3,2,1

tips:默认情况下大的优先级高,底层是个大堆

3.priority_queue的底层实现

3.1、库里面关于priority_queue的定义

在这里插入图片描述
priority_queue类模板参数多了一个Compare,这个参数是用来调节大小堆的,默认的less是大堆,greater是小堆
tips:
在这里插入图片描述

3.2、仿函数

1.什么是仿函数?

仿函数又被叫做函数对象,它们是通过重载operator()运算符的类的实例,它们可以像函数那样被调用,具有这样特性的就是仿函数

2.仿函数样例
template<class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};int main()
{Less<int> lessfunc;cout << lessfunc.operator()(1, 2) << endl;cout << lessfunc(2, 3) << endl;//就这样乍一看还以为是函数调用,其实这是仿函数cout << Less<int>()(1, 2) << endl;//通过匿名对象来调用return 0;
}

3.3、实现优先级队列

1. 1.0版本的实现
template<class T,class Container=vector<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 <_con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size()-1);//再向上调整}void pop(){swap(_con[0], _con[_con.size() - 1]);//先把要删除的堆顶元素和最后一个元素交换_con.pop_back();//然后删除最后一个元素adjust_down(0);//再进行向下调整}const T& top(){return _con[0];}bool empty(){return _con.empty();}private:Container _con;
};

这里重点讲一下向上调整建堆和向下调整建堆,我们以建小堆为例:
在这里插入图片描述
向下调整的原理和向上调整很像,我就不多讲解了

2. 2.0版本的实现
template<class T>
struct less//这个虽然叫less但是它是大堆
{bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
struct greater//这个虽然叫greater,但是他是小堆
{bool operator()(const T& x, const T& y){return x > y;}
};
template<class T,class Container=vector<T>,class Com=less<T>>
class priority_queue
{
public:size_t size(){return _con.size();}void adjust_up(size_t child){Com com;//搞一个仿函数对象size_t parent = (child - 1) / 2;while (child>0){//if (_con[child] > _con[parent])//if ( _con[parent]<_con[child] )if(com(_con[parent],_con[child])){//注意这里换成仿函数的时候要和它里面的<对上,再替换成仿函数对象调用swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Com com;size_t child = parent * 2 + 1;while (child<_con.size()){//if (child + 1 <_con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){child++;}//if (_con[child] > _con[parent])//if (_con[parent]< _con[child])if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size()-1);//再向上调整}void pop(){swap(_con[0], _con[_con.size() - 1]);//先把要删除的堆顶元素和最后一个元素交换_con.pop_back();//然后删除最后一个元素adjust_down(0);//再进行向下调整}const T& top(){return _con[0];}bool empty(){return _con.empty();}private:Container _con;
};

tips:

int main()
{priority_queue<int,vector<int>,greater<int>> pq;//注意这里:如果你要传仿函数的参数类型,一定不要忘记了这个vector<int>//不能跳过这个缺省参数去传他后面的其他参数,切记切记!!!return 0;
}

二、反向迭代器适配器

反向迭代器适配器,可以根据正向迭代器适配出它相应的反向迭代器

反向迭代器的实现思想其实很简单,相比我们前面list的实现;我们在这里实现反向迭代器主要是利用正向迭代器来替我们完成,库里面的实现讲求了对称,begin/end和rbegin/rend是堆成的
在这里插入图片描述

template<class iterator, class Ref, class Ptr>
struct ReserveIterator
{typedef ReserveIterator<iterator, Ref, Ptr> Self;iterator _it;ReserveIterator(iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}
};

关于容器适配器之类的容器我们就先讲到这里,我们下期浅谈一下模板✌

相关文章:

【C++】priority_queues(优先级队列)和反向迭代器适配器的实现

目录 一、 priority_queue1.priority_queue的介绍2.priority_queue的使用2.1、接口使用说明2.2、优先级队列的使用样例 3.priority_queue的底层实现3.1、库里面关于priority_queue的定义3.2、仿函数1.什么是仿函数&#xff1f;2.仿函数样例 3.3、实现优先级队列1. 1.0版本的实现…...

Go语言函数

在Go语言中&#xff0c;函数是一种基本的构建块&#xff0c;用于组织代码并执行特定任务。它们是可重复使用的代码段&#xff0c;可以接收输入参数&#xff0c;执行一系列操作&#xff0c;并可返回结果。以下是Go语言中函数的详细介绍及其使用方法&#xff1a; 基本语法 Go语…...

如何使用EasyExcel导入百万数据

摘要&#xff1a; 本文将详细探讨如何利用EasyExcel库&#xff0c;以及结合Java编程&#xff0c;高效地导入大规模数据至应用程序中。我们将逐步介绍导入流程、代码实现细节&#xff0c;并提供性能优化建议&#xff0c;旨在帮助读者在处理百万级别数据时&#xff0c;提高效率与…...

【解决】Unity Build 应用程序运行即崩溃问题

开发平台&#xff1a;Unity 2021.3.7f1c1   一、问题描述 编辑器 Build 工程结束&#xff0c;但控制台 未显示 Build completed with a result of Succeeded [时间长度] 信息。该情况下打包流程正常&#xff0c;但应用程序包打开即崩溃。   二、问题测试记录 测试1&#xf…...

C++数据结构——红黑树

前言&#xff1a;本篇文章我们继续来分享C中的另一个复杂数据结构——红黑树。 目录 一.红黑树概念 二.红黑树性质 三.红黑树实现 1.基本框架 2.插入 3.判断平衡 四.完整代码 总结 一.红黑树概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个…...

Java并发编程:学习路线图

文章目录 一、操作系统内核原理1、进程管理详解2、内存管理详解3、IO输入输出系统详解4、进程间通信机制详解5、网络通信原理剖析 二、Java内存模型三、并发集合1、Map&#xff08;1&#xff09;ConcurrentHashMap&#xff08;2&#xff09;ConcurrentSkipListMap 2、List&…...

算法_前缀和

DP34 【模板】前缀和 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n in.nextInt(),q in.ne…...

C语言(指针)7

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;关注收藏&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#x…...

线程纵横:C++并发编程的深度解析与实践

hello &#xff01;大家好呀&#xff01; 欢迎大家来到我的Linux高性能服务器编程系列之《线程纵横&#xff1a;C并发编程的深度解析与实践》&#xff0c;在这篇文章中&#xff0c;你将会学习到C新特性&#xff0c;并发编程&#xff0c;以及其如何带来的高性能的魅力&#xff0…...

在阿里云服务器上安装MySQL

目录 一、先卸载不需要的环境 1.关闭MySQL服务 2.查看安装包以及卸载安装包 3.依次卸载所有包 4. 获取mysql官⽅yum源 二、安装&#xff08;密钥过期解决方法&#xff09; 三、启动并进入 关于MySQL MySQL是一个广泛使用的开源关系型数据库管理系统&#xff08;RDBMS&…...

国标GB28181协议EasyCVR视频汇聚平台获取设备录像仅展示部分片段的原因排查

国标GB28181协议EasyCVR安防平台可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集中存储、云存储等丰富的视频能力&#xff0c;平台支持7*24小时实时高清视频监控&#xff0c;能同时播放多路监控视频流&#xf…...

Java的类和对象(一)—— 初始类和对象,this关键字,构造方法

前言 从这篇文章开始&#xff0c;我们就进入到了JavaSE的核心部分。这篇文章是Java类和对象的第一篇&#xff0c;主要介绍类和对象的概念&#xff0c;this关键字以及构造方法~~ 什么是类&#xff1f;什么是对象&#xff1f; 学过C语言的老铁们&#xff0c;可以类比struct自定义…...

富格林:曝光虚假套路规避亏损

富格林指出&#xff0c;在现货黄金市场中&#xff0c;交易时间很充足投资机会也多的是&#xff0c;但为什么还是有人亏损甚至爆仓呢&#xff1f;其实导致这种情况&#xff0c;是因为有一些投资者不知道其中的虚假套路&#xff0c;很容易就一头栽进去了。要规避虚假套路带来的亏…...

数据源网站分享

1. 国家统计局&#xff1a; http://www.stats.gov.cn/提供国家宏观经济数据 2. 工业和信息化部&#xff1a; http://www.miit.gov.cn 发布工业运行及信息化相关数据 3. 中国人民银行&#xff1a; http://www.pbc.gov.cn/ 提供金融市场政策及运行相关数据 4. 国家金融监督…...

Flutter 中的 CupertinoAlertDialog 小部件:全面指南

Flutter 中的 CupertinoAlertDialog 小部件&#xff1a;全面指南 在Flutter中&#xff0c;CupertinoAlertDialog是用于在iOS风格的应用中显示警告或提示信息的模态对话框。它以其圆角卡片和模糊背景为特点&#xff0c;为用户提供了一个简洁而直观的交互界面。CupertinoAlertDi…...

【RAG 论文】UPR:使用 LLM 来做检索后的 re-rank

论文&#xff1a;Improving Passage Retrieval with Zero-Shot Question Generation ⭐⭐⭐⭐ EMNLP 2022, arXiv:2204.07496 Code: github.com/DevSinghSachan/unsupervised-passage-reranking 论文&#xff1a;Open-source Large Language Models are Strong Zero-shot Query…...

安全风险 - 如何解决 setAccessible(true) 带来的安全风险?

可能每款成熟的金融app上架前都会经过层层安全检测才能执行上架&#xff0c;所以我隔三差五就能看到安全检测报告中提到的问题&#xff0c;根据问题的不同级别&#xff0c;处理的优先级也有所不同&#xff0c;此次讲的主要是一个 “轻度问题” &#xff0c;个人认为属于那种可改…...

创建继承自QObject的线程:一个详细指南

目录标题 步骤 1&#xff1a;创建一个新的QObject子类步骤 2&#xff1a;在新的QObject子类中实现工作代码步骤 3&#xff1a;创建一个新的QThread对象步骤 4&#xff1a;管理线程的生命周期步骤 5&#xff1a;处理线程间通信结论 在Qt中&#xff0c;线程可以通过继承QThread类…...

java项目之智慧图书管理系统设计与实现(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的智慧图书管理系统设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 智慧图书管理…...

分享一些人生道理,希望能对大家有所帮助!

1. 别总想出风头&#xff0c;炫耀就是深渊&#xff0c;贪心就是毁灭&#xff0c;人性的恶一旦被激发&#xff0c;后果不堪设想。 2. 戒取怨之言&#xff1a;不要说招人怨恨的话&#xff0c;播下使人怨恨的种子。 3. 学会感恩&#xff0c;因为感恩能够让你更加幸福。 4. 玉碎不能…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...