[STL]priority_queue类及反向迭代器的模拟实现

🪐🪐🪐欢迎来到程序员餐厅💫💫💫
今日主菜: priority_queue类及反向迭代器
主厨:邪王真眼
主厨的主页:Chef‘s blog
所属专栏:c++大冒险
向着c++,塔塔开!
[本节目标]
-
1.仿函数
-
2.priority_queue
-
3.反向迭代器
一.仿函数
1.1仿函数是什么
仿函数(Functor)是一种重载了函数调用运算符(operator())的类对象,他的使用方法看起来与函数极其相似,却又有不同,因此成为仿函数
1.2仿函数的定义与使用
我们现在写一个可以比较两个变量大小的仿函数以及函数
template<class T>
class Less
{bool operator()(const T&a,const T&b ){return a < b;}
};
template<class T>bool Less(const T& a, const T& b ){return a < b;}
那么问题来了,仿函数的优势是什么呢?
我们知道有时候为了在函数中调用别的函数我们需要传一个叫做函数指针的东西,简单的函数还好,复杂的函数的指针是真的难看懂,于是乎,仿函数横空出世,你要用它就传个他的类就行,一下子容易多了。
二、priority_queue
2.1 priority_queue的介绍
- empty():检测容器是否为空
- size():返回容器中有效元素个数
- front():返回容器中第一个元素的引用
- push_back():在容器尾部插入元素
- pop_back():删除容器尾部元素
2.2成员变量
template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public://函数private:Container _con;}; 2.3empty
bool empty(){reutrn _con.empty();} 2.4size
返回容器适配器的元素个数
size_t size(){return _con.size();} 2.5top
返回堆顶元素
注意事项:我们的返回值是const类型,没有非const,这是因为如果你用非const就可能导致堆顶元素修改,进而导致结构不再是大堆或小堆。
constT& top()const{_con.front();} 2.6push
入堆
- 1.先尾插
- 2.在向上调整
void push(T& val){_con.push_back(val);UpAdjust();}void UpAdjust(size_t number)//大堆{int child = number - 1;int parent = child = (child-1) / 2;while (child){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child-1) / 2;}elsebreak;}} 这里我们既要思考,如果建一个小堆那就要在写一个函数,可是他们两个函数只有

这里需要改变,一个是>,一个是<。
于是乎,我们立刻想到了再加一个模板参数,用它来处理这个大于小于的问题,
如下:
template<class T>
class Less
{bool operator()(const T&a,const T&b ){return a < b;}
};
template<class T>
class Greater
{bool operator()(const T& a, const T& b){return a > b;}
}; void push(T& val){_con.push_back(val);UpAdjust();}Compare com;void UpAdjust(size_t number)//大堆{int child = number - 1;int parent = child = (child-1) / 2;while (child){if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child-1) / 2;}elsebreak;}} 2.7pop
出堆
这个就比较难了,为了保证堆的结构尽可能不被破坏以降低时间复杂度,我们选择:
- 先把第一个元素和最后一个元素交换位置
- 最后删除最后一个元素。
- 在对堆顶进行向下调整法
- 构造一个仿函数模板对象,再利用重载的()运算符进行比较
template<class T>
class Less
{bool operator()(const T&a,const T&b ){return a < b;}
};
template<class T>
class Greater
{bool operator()(const T& a, const T& b){return a > b;}
};
Compare com;void DownAdjust(size_t size){int parent = 0;int child = parent * 2+1;while (child<size){if (child<size&&com(_con[child], _con[child + 1]))child++;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);
_con.pop_back();DownAdjust(size());}
三、反向迭代器
反向迭代器是一种适配器,它是根据不同容器的正向迭代器,来生成对应的反向迭代器。
反向迭代器的rbegin对应迭代器的end位置,rend对应begin位置。
3.1 成员变量
细节:
- 使用struct,标明公有属性
- 成员变量是一个正向迭代器
template <class Iterator,class Ref,class Ptr>
struct ReverseItreator
{typedef ReverseIterator<Iterator, Ref, Ptr> self;Iterator it;
};
3.2默认成员函数
写一个缺省的构造,别的编译器自动生即可。
ReverseItreator(Iterator val=Iterator()):it(val){}
3.3operator*
Ref operator*(){Iterator its = it;its--;return *its;}
3.4operator--
self operator--()
{return ++it;
}
self operator--()const
{Iterator its = it;++it;return its;
}
3.5operator++
self operator++(){return --it;}self operator++()const{Iterator its = it;--it;return its;}
3.6operator->
Ptr operator->(){return & (*it);}
3.7operator==,operator!=
bool operator==(const self&s){return it = s.it;}bool operator !=(const self& s){return it = s.it;}
3.8反向迭代器的应用
在容器中,以vector举例
template<class T>
class vector
{
public:typedef T* Iterator;typedef const T* Const_Iterator;typedef ReverseIterator<Iteartor, T&, T*> Reverse_Iterator;typedef ReverseIterator<Iteartor, constT&,cosnt T*> Const_Reverse_Iterator;Iterator end(){return _finish;}Const_Iterator end()const{return _finish;}Iterator begin(){return _start;}Const_Iterator begin()const{return _start;}private:T* _start;T* _finish;
};
反向迭代器函数:
Reverse_Iterator rbegin(){return (Reverse_Iterator)end();}Const_Reverse_Iterator rbegin()const{return (Const_Reverse_Iterator)end();}Reverse_Iterator rend(){return (Reverse_Iterator)begin();}Const_Reverse_Iterator rend()const{return (Const_Reverse_Iterator)begin();}
这时候我们就要提个问题了,就拿rbegin了,来说吧
看看这个函数怎么样:
Reverse_Iterator begin(){return _finish;}
乍一看似乎完全没问题,但是但是,如果是list你咋办呢,是deque你咋办呢,他们都没有这个
_finish成员变量啊,所以我们一开始就说了,它是根据不同容器的正向迭代器,来生成对应的反向迭代器。反向迭代器去调用正向迭代器的实现方法才能保证他的普适性。
总结
- 仿函数的用法及优势,并在priority_queue适配器中加以应用
- 对priority_queue进行了了解和模拟,
- 实现很久前就提到的了反向迭代器,对迭代器这个概念有了更深的了解。
感觉有用的话就点个赞支持一下吧

相关文章:
[STL]priority_queue类及反向迭代器的模拟实现
🪐🪐🪐欢迎来到程序员餐厅💫💫💫 今日主菜: priority_queue类及反向迭代器 主厨:邪王真眼 主厨的主页:Chef‘s blog 所属专栏:c大冒险 向着c&…...
vue2 脚手架
安装 文档:https://cli.vuejs.org/zh/ 第一步:全局安装(仅第一次执行) npm install -g vue/cli 或 yarn global add vue/cli 备注:如果出现下载缓慢:请配置npm 淘宝镜像: npm config set regis…...
【OpenStack】OpenStack实战之开篇
目录 那么,OpenStack是什么?云又是什么?关于容器应用程序OpenStack如何适配其中?如何设置它?如何学会使用它?推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战我的整个职业生涯到目前为止一直围绕着为离线或隔离网络设计和开发应用程…...
Python实现WebSocket通信
WebSocket是一种在单个TCP连接上进行全双工通信的协议,位于 OSI 模型的应用层。 与传统的HTTP请求-响应模型不同,WebSocket的最大特点就是,服务器可以主动向客户端推送信息,客户端也可以主动向服务器发送信息,实现实时性和互动性…...
MATLAB 自定义生成直线点云(详细介绍) (47)
MATLAB 自定义生成直线点云 (详细介绍)(47) 一、算法介绍二、具体步骤二、算法实现1.代码2.效果一、算法介绍 通过这里的直线生成方法,可以生成模拟直线的点云数据,并通过调整起点、终点、数量和噪声水平等参数来探索不同类型的直线数据。这种方法可以用于测试、验证和开…...
UniTask 异步任务
文章目录 前言一、UniTask是什么?二、使用步骤三、常用的UniTask API和示例1.编写异步方法2.处理异常3.延迟执行4.等待多个UniTask或者一个UniTas完成5.异步加载资源示例6.手动控制UniTask的完成状态7.UniTask.Lazy延迟任务的创建8.后台线程切换Unity主线程9.不要返…...
【git分支管理策略】如何高效的管理好代码版本
目录 1.分支管理策略 2.我用的分支管理策略 3.一些常见问题 1.分支管理策略 分支管理策略就是一些经过实践后总结出来的可靠的分支管理的办法,让分支之间能科学合理、高效的进行协作,帮助我们在整个开发流程中合理的管理好代码版本。 目前有两套Git…...
css的transition详解
CSS的transition属性是一个简写属性,用于设置四个过渡效果属性,以在元素的状态改变时创建平滑的动画效果。这四个属性分别是: transition-property: 定义应用过渡效果的CSS属性名称。当指定的CSS属性改变时,过渡效果将…...
agent利用知识来做规划:《KnowAgent: Knowledge-Augmented Planning for LLM-Based Agents》笔记
文章目录 简介KnowAgent思路准备知识Action Knowledge的定义Planning Path Generation with Action KnowledgePlanning Path Refinement via Knowledgeable Self-LearningKnowAgent的实验结果 总结参考资料 简介 《KnowAgent: Knowledge-Augmented Planning for LLM-Based Age…...
01 React新建开发环境
https://create-react-app.dev/docs/getting-started npx create-react-app my-appJSX使用表达式嵌入 function App() {const count 100;function getSelfName() {return "SelfName"}return (<div>Hello World!<div>{This is Javascript message~!}&l…...
nginx--解决响应头带Set-Cookie导致的验证失败
解决响应头带Set-Cookie导致的验证失败 前言给nginx.conf 设置Secure配置完成后会发现cookie就不会发生变化了 前言 在用nginx做代理的时候,会发现nginx在访问不同ip请求的时候会带setCookie 导致后端就是放开cookie验证,在访问玩这个链接他更新了cooki…...
InstructGPT的流程介绍
1. Step1:SFT,Supervised Fine-Tuning,有监督微调。顾名思义,它是在有监督(有标注)数据上微调训练得到的。这里的监督数据其实就是输入Prompt,输出相应的回复,只不过这里的回复是人工…...
docker容器下部署hbase并在springboot中通过jdbc连接
我在windows的docker中部署了一个hbase服务,然后用springboot连接到此服务并访问数据。 详情可参考项目中的README.md。项目中提供了用于构建镜像的dockerfile,以及测试代码。 项目连接: https://gitee.com/forgot940629/hbase_phoenix_sprin…...
Qt——智能指针实战
目录 前言正文一、理论介绍1、QPointer2、QScopedPoint3、QSharedPoint4、QWeakPoint 二、实战演练1、QPoint2、QScopedPoint3、QSharedPointa、示例一b、示例二 4、QWeakPoint END、总结的知识与问题 参考 前言 智能指针的使用,对很多程序员来说,都算是…...
Unity Mobile Notifications推送问题
1.在部分机型点击通知弹窗进不去游戏 把这里改成自己的Activity 2.推送的时候没有横幅跟icon红点 主要是第一句话 注册的时候选项可以选择 defaultNotificationChannel new AndroidNotificationChannel(“default_channel”, “Default Channel”, “For Generic notifica…...
C++_回文串
目录 回文子串 最长回文子串 分割回文串 IV 分割回文串 II 最长回文子序列 让字符串成为回文串的最少插入次数 回文子串 647. 回文子串 思路,i j表示改范围内是否为回文串, ②倒着遍历是为了取出dp[i 1][j - 1] ③i j 只有一对,不会重复…...
【阅读论文】When Large Language Models Meet Vector Databases: A Survey
摘要 本调查探讨了大型语言模型(LLM)和向量数据库(VecDB)之间的协同潜力,这是一个新兴但迅速发展的研究领域。随着LLM的广泛应用,出现了许多挑战,包括产生虚构内容、知识过时、商业应用成本高昂…...
兼职副业大揭秘:六个潜力满满的赚钱途径
亲爱的朋友,你对兼职副业充满好奇与期待,这非常好!在此,我将为你分享一些能够助你赚取额外收入的兼职副业建议。以下是六个颇具潜力的兼职副业方向,希望能为你的探索之路提供些许启发。 1,网络调查与市场洞…...
C++ Qt开发:QUdpSocket实现组播通信
Qt 是一个跨平台C图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍如何运用QUdpSocket组件实现基于UDP的组播通信…...
excel 表中有图片并在筛选特定行时,只显示该行的图片
建议:选中excel 表中某张图片,CtrlA,选中所有图片。再右键,在菜单中选设置对象格式 在属性里按下图设置, 生效之后,筛选某个产品的时候,就不会显示其他的不符合筛选条件的产品的图片了。...
新手入门DetectionLab:10个步骤掌握企业网络安全检测基础
新手入门DetectionLab:10个步骤掌握企业网络安全检测基础 【免费下载链接】DetectionLab clong/DetectionLab: DetectionLab是一个开源项目,旨在建立一个高度可配置的虚拟环境以模拟企业网络,用于检测恶意活动、演练入侵检测系统(…...
解放你的创造力:用TEdit打造泰拉瑞亚专属世界地图
解放你的创造力:用TEdit打造泰拉瑞亚专属世界地图 【免费下载链接】Terraria-Map-Editor TEdit - Terraria Map Editor - TEdit is a stand alone, open source map editor for Terraria. It lets you edit maps just like (almost) paint! It also lets you change…...
开源剧本AI落地实操:像素剧本圣殿+Dual-GPU并行推理完整教程
开源剧本AI落地实操:像素剧本圣殿Dual-GPU并行推理完整教程 1. 项目概览 像素剧本圣殿(Pixel Script Temple)是一款基于Qwen2.5-14B-Instruct深度微调的专业剧本创作工具。这个开源项目将先进的AI推理能力与独特的8-Bit复古美学相结合&…...
赋能音乐自由:Unlock Music技术解密与全场景应用指南
赋能音乐自由:Unlock Music技术解密与全场景应用指南 【免费下载链接】unlock-music 在浏览器中解锁加密的音乐文件。原仓库: 1. https://github.com/unlock-music/unlock-music ;2. https://git.unlock-music.dev/um/web 项目地址: https:…...
YOLO12开源模型合规部署:离线环境+审计日志+模型版本固化方案
YOLO12开源模型合规部署:离线环境审计日志模型版本固化方案 1. 项目背景与核心价值 YOLO12作为Ultralytics在2025年推出的最新实时目标检测模型,在保持高速推理性能的同时显著提升了检测精度。其引入的注意力机制优化了特征提取网络,nano版…...
从线索到成交,陀螺匠帮我打通了客户管理全流程
作为一个从业多年销售,我觉得我在管理客户过程中遇到的这些问题,很多企业多多少少也出现过。比如销售小王跟了一个月的客户,最后发现小李早就联系过了,经常白忙活;好不容易谈成的单子,合同改来改去…...
Cursor Pro破解工具:如何通过开源技术方案实现AI编程助手无限制使用?
Cursor Pro破解工具:如何通过开源技术方案实现AI编程助手无限制使用? 【免费下载链接】cursor-free-vip [Support 0.45](Multi Language 多语言)自动注册 Cursor Ai ,自动重置机器ID , 免费升级使用Pro 功能…...
4个革新性步骤:NHSE动物森友会存档编辑器完全指南
4个革新性步骤:NHSE动物森友会存档编辑器完全指南 【免费下载链接】NHSE Animal Crossing: New Horizons save editor 项目地址: https://gitcode.com/gh_mirrors/nh/NHSE NHSE(动物森友会存档编辑器)作为一款开源免费工具,…...
LeetCode 热题 100 之 131. 分割回文串 51. N 皇后
131. 分割回文串 51. N 皇后 131. 分割回文串 class Solution {public List<List<String>> partition(String s) {List<List<String>> res new ArrayList<>();List<String> path new ArrayList<>();backtrack(s, 0, path, res);re…...
OPENIPC[ssc338Q+hi3536dv100]开源图传----硬件选型与实战避坑指南
1. 开源图传系统硬件选型逻辑 第一次接触OPENIPC开源图传时,我和大多数新手一样被各种专业术语搞得头晕眼花。经过三个月的实际搭建和测试,终于摸清了硬件选型的门道。这里分享的不仅是参数对比,更是我踩过坑后总结的实战经验。 核心硬件架构…...

