【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;}
};

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

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

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

相关文章

memset函数

让我们先看两个代码 memset(dp, 0x3f, sizeof(dp)); for (int i 0; i < 5; i)cout << dp[i] << " "; memset(dp, 127, sizeof(dp)); for (int i 0; i < 5; i)cout << dp[i] << " "; 代码结果如下&#xff1a; 现在我们来分…

ubuntu编译pcl时报错

报错如下 cc1plus: warning: -Wabi wont warn about anything [-Wabi] cc1plus: note: -Wabi warns about differences from the most up-to-date ABI, which is also used by default cc1plus: note: use e.g. -Wabi11 to warn about changes from GCC 7 在网上找到了一封邮件…

Java | Leetcode Java题解之第74题搜索二维矩阵

题目&#xff1a; 题解&#xff1a; class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length, n matrix[0].length;int low 0, high m * n - 1;while (low < high) {int mid (high - low) / 2 low;int x matrix[mid / n][m…

(done) 关于 pytorch 代码里常出现的 batch_first 到底是啥?

参考文章&#xff1a;https://pytorch.org/docs/stable/generated/torch.nn.utils.rnn.pad_sequence.html 首先看参考文章里的解释&#xff0c;如下图 从文章描述来看&#xff0c;当 batch_first True 时&#xff0c;输出的张量的 size 是 B x T x *。当 batch_first False…

618速递丨各平台内卷严重,这些行业能否率先炸场?

根据最新发布的《中国网络视听发展研究报告&#xff08;2024&#xff09;》显示&#xff0c;71.2%的受访用户因为看短视频和直播进行网上购物&#xff0c;超40%的用户认为短视频和直播是他们的主要消费渠道&#xff0c;内容消费正成为各大电商争夺的关键赛道。 今年618&#x…

[BJDCTF 2020]easy_md5、[HNCTF 2022 Week1]Interesting_include、[GDOUCTF 2023]泄露的伪装

目录 [BJDCTF 2020]easy_md5 ffifdyop [SWPUCTF 2021 新生赛]crypto8 [HNCTF 2022 Week1]Interesting_include php://filter协议 [GDOUCTF 2023]泄露的伪装 [BJDCTF 2020]easy_md5 尝试输入一个1&#xff0c;发现输入的内容会通过get传递但是没有其他回显 观察一下响应…

【多模态】30、Monkey | 支持大尺寸图像输入的多任务多模态大模型

文章目录 一、背景二、方法2.1 Enhancing Input Resolution2.2 Multi-level Description Generation2.3 Multi-task Training 三、效果3.1 Image Caption3.2 General VQA3.3 Scene Text-centric VQA3.4 Document-oriented VQA3.5 消融实验3.6 可视化 论文&#xff1a;Monkey : …

【JS面试题】this

this取什么值&#xff0c;是在函数执行的时候确定的&#xff0c;不是在函数定义的时候确定的&#xff01; this的6种使用场景&#xff1a; ① 在普通函数中使用&#xff1a;返回window对象 ② 使用call apply bind 调用&#xff1a;绑定的是哪个对象就返回哪个对象 ③ 在对象…

MacApp自动化测试之Automator初体验

今天我们继续讲Automator的使用。 初体验 启动Automator程序&#xff0c;选择【工作流程】类型。从资源库区域依次将获取指定的URL、从网页中获得文本、新建文本文件三个操作拖进工作流创建区域。 然后修改内容&#xff0c;将获取指定的URL操作中的URL替换成https://www.cnb…

【C/C++笔试练习】DNS劫持、三次握手、TCP协议、HTTPS、四次挥手、HTTP报文、拥塞窗口、POP3协议、UDP协议、收件人列表、养兔子

文章目录 C/C笔试练习选择部分&#xff08;1&#xff09;DNS劫持&#xff08;2&#xff09;三次握手&#xff08;3&#xff09;TCP协议&#xff08;4&#xff09;HTTPS&#xff08;5&#xff09;四次挥手&#xff08;6&#xff09;HTTP报文&#xff08;7&#xff09;拥塞窗口&a…

JVM面试题:85道JVM虚拟机面试题及答案

面试题 1 .简述Java堆的结构&#xff1f;什么是堆中的永久代(Perm Gen space)? JVM整体结构及内存模型 试题回答参考思路&#xff1a; 1、堆结构 JVM的堆是运行时数据区&#xff0c;所有类的实例和数组都是在堆上分配内存。它在JVM启动的时候被创建。对象所占的堆内存是由自…

【AI学习】聊两句昨夜OpenAI的GPT-4o

蹭个热点&#xff0c;聊两句昨夜的大事件——OpenAI发布GPT-4o&#xff0c;我看到和想到的一点东西。 首先是端到端方法&#xff0c;前面关于深度学习的文章&#xff0c;对端到端的重要性做了一些学习&#xff0c;对端到端这个概念有了一些理解。正如Richard Sutton在《苦涩的…

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

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

一个不知名的开源项目可以带来多少收入

起源 2020 年新冠疫情开始蔓延&#xff0c;当时我在同时经营 3 个不同的公司。除了其中的体育赛事平台因为疫情关门大吉之外&#xff0c;另外两个公司并没有受影响&#xff0c;营收和利润反而都持续增加。但是连续几个月不能出远门&#xff0c;也不能随便见朋友和客户&#xff…

Kafka学习-Java使用Kafka

文章目录 前言一、Kafka1、什么是消息队列offset 2、高性能topicpartition 3、高扩展broker 4、高可用replicas、leader、follower 5、持久化和过期策略6、消费者组7、Zookeeper8、架构图 二、安装Zookeeper三、安装Kafka四、Java中使用Kafka1、引入依赖2、生产者3、消费者4、运…

【C语言】/*操作符(下)*/

目录 一、操作符的分类 二、二进制和进制转换 2.1 进制 2.2 进制之间的转换 三、原码、反码、补码 四、单目操作符 五、逗号表达式 六、下标引用操作符[] 七、函数调用操作符() 八、结构体成员访问操作符 8.1 直接访问操作符(.) 8.2 间接访问操作符(->) 九、操作符…

【Spring】初识 Spring AOP(面向切面编程)

目录 1、介绍AOP 1.1、AOP的定义 1.2、AOP的作用 1.3、AOP的核心概念及术语 2、AOP实现示例 3、EnableAspectJAutoProxy注解 1、介绍AOP 1.1、AOP的定义 AOP&#xff08;Aspect Orient Programming&#xff09;&#xff0c;直译过来就是面向切面编程&#xff0c;AOP 是一…

[动画详解]LeetCode151.翻转字符串里的单词

&#x1f496;&#x1f496;&#x1f496;欢迎来到我的博客&#xff0c;我是anmory&#x1f496;&#x1f496;&#x1f496; 又和大家见面了 欢迎来到动画详解LeetCode算法系列 用通俗易懂的动画让算法题不再神秘 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成…

十二生肖Midjourney绘画大挑战:释放你的创意火花

随着AI艺术逐渐进入大众视野&#xff0c;使用Midjourney绘制十二生肖不仅能够激发我们的想象力&#xff0c;还能让我们与传统文化进行一场新式的对话。在这里&#xff0c;我们会逐一提供给你创意满满的绘画提示词&#xff0c;让你的作品别具一格。而且&#xff0c;我们还精选了…

Python进行excel处理-01

最近干采购&#xff0c;每个月要对供应商的对账单&#xff0c;对对应的采购订单号和物料编号的价格和数量&#xff0c;是不是和物料管控总表里面的价格数量是不是一致&#xff0c;于是写了一个代码。 从总表里面找到&#xff0c;对账单里对应采购订单和物料编码的数据&#xf…