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

[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的介绍

1. 优先队列是一种容器适配器,STL中默认使用的容器是vector(不过deque也可以)
2. 他存储数据的结构是堆,默认是大堆。
3.  底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
  1. empty():检测容器是否为空
  2. size():返回容器中有效元素个数
  3. front():返回容器中第一个元素的引用
  4. push_back():在容器尾部插入元素
  5. pop_back():删除容器尾部元素
4.  需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、 push_heap pop_heap 来自动完成此操作。

2.2成员变量

	template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public://函数private:Container _con;};
我们是直接模拟的STL的格式,但事实上,在模板参数那里,应该把Container放到最后才合适,因为我们一般不会修改使用的容器,但会选择建一个大堆或者小堆,STL的格式导致我们在调整为小堆时,必须也写容器才行(盲猜大佬写的时候喝假酒了)。

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

出堆

这个就比较难了,为了保证堆的结构尽可能不被破坏以降低时间复杂度,我们选择:

  1. 先把第一个元素和最后一个元素交换位置
  2. 最后删除最后一个元素。
  3. 在对堆顶进行向下调整法
  4. 构造一个仿函数模板对象,再利用重载的()运算符进行比较
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 成员变量

细节:

  1. 使用struct,标明公有属性
  2. 成员变量是一个正向迭代器
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类及反向迭代器的模拟实现

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 今日主菜&#xff1a; priority_queue类及反向迭代器 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 向着c&…...

vue2 脚手架

安装 文档&#xff1a;https://cli.vuejs.org/zh/ 第一步&#xff1a;全局安装&#xff08;仅第一次执行&#xff09; npm install -g vue/cli 或 yarn global add vue/cli 备注&#xff1a;如果出现下载缓慢&#xff1a;请配置npm 淘宝镜像&#xff1a; npm config set regis…...

【OpenStack】OpenStack实战之开篇

目录 那么,OpenStack是什么?云又是什么?关于容器应用程序OpenStack如何适配其中?如何设置它?如何学会使用它?推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战我的整个职业生涯到目前为止一直围绕着为离线或隔离网络设计和开发应用程…...

Python实现WebSocket通信

WebSocket是一种在单个TCP连接上进行全双工通信的协议,位于 OSI 模型的应用层。 与传统的HTTP请求-响应模型不同&#xff0c;WebSocket的最大特点就是&#xff0c;服务器可以主动向客户端推送信息&#xff0c;客户端也可以主动向服务器发送信息&#xff0c;实现实时性和互动性…...

MATLAB 自定义生成直线点云(详细介绍) (47)

MATLAB 自定义生成直线点云 (详细介绍)(47) 一、算法介绍二、具体步骤二、算法实现1.代码2.效果一、算法介绍 通过这里的直线生成方法,可以生成模拟直线的点云数据,并通过调整起点、终点、数量和噪声水平等参数来探索不同类型的直线数据。这种方法可以用于测试、验证和开…...

UniTask 异步任务

文章目录 前言一、UniTask是什么&#xff1f;二、使用步骤三、常用的UniTask API和示例1.编写异步方法2.处理异常3.延迟执行4.等待多个UniTask或者一个UniTas完成5.异步加载资源示例6.手动控制UniTask的完成状态7.UniTask.Lazy延迟任务的创建8.后台线程切换Unity主线程9.不要返…...

【git分支管理策略】如何高效的管理好代码版本

目录 1.分支管理策略 2.我用的分支管理策略 3.一些常见问题 1.分支管理策略 分支管理策略就是一些经过实践后总结出来的可靠的分支管理的办法&#xff0c;让分支之间能科学合理、高效的进行协作&#xff0c;帮助我们在整个开发流程中合理的管理好代码版本。 目前有两套Git…...

css的transition详解

CSS的transition属性是一个简写属性&#xff0c;用于设置四个过渡效果属性&#xff0c;以在元素的状态改变时创建平滑的动画效果。这四个属性分别是&#xff1a; transition-property&#xff1a; 定义应用过渡效果的CSS属性名称。当指定的CSS属性改变时&#xff0c;过渡效果将…...

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做代理的时候&#xff0c;会发现nginx在访问不同ip请求的时候会带setCookie 导致后端就是放开cookie验证&#xff0c;在访问玩这个链接他更新了cooki…...

InstructGPT的流程介绍

1. Step1&#xff1a;SFT&#xff0c;Supervised Fine-Tuning&#xff0c;有监督微调。顾名思义&#xff0c;它是在有监督&#xff08;有标注&#xff09;数据上微调训练得到的。这里的监督数据其实就是输入Prompt&#xff0c;输出相应的回复&#xff0c;只不过这里的回复是人工…...

docker容器下部署hbase并在springboot中通过jdbc连接

我在windows的docker中部署了一个hbase服务&#xff0c;然后用springboot连接到此服务并访问数据。 详情可参考项目中的README.md。项目中提供了用于构建镜像的dockerfile&#xff0c;以及测试代码。 项目连接&#xff1a; https://gitee.com/forgot940629/hbase_phoenix_sprin…...

Qt——智能指针实战

目录 前言正文一、理论介绍1、QPointer2、QScopedPoint3、QSharedPoint4、QWeakPoint 二、实战演练1、QPoint2、QScopedPoint3、QSharedPointa、示例一b、示例二 4、QWeakPoint END、总结的知识与问题 参考 前言 智能指针的使用&#xff0c;对很多程序员来说&#xff0c;都算是…...

Unity Mobile Notifications推送问题

1.在部分机型点击通知弹窗进不去游戏 把这里改成自己的Activity 2.推送的时候没有横幅跟icon红点 主要是第一句话 注册的时候选项可以选择 defaultNotificationChannel new AndroidNotificationChannel(“default_channel”, “Default Channel”, “For Generic notifica…...

C++_回文串

目录 回文子串 最长回文子串 分割回文串 IV 分割回文串 II 最长回文子序列 让字符串成为回文串的最少插入次数 回文子串 647. 回文子串 思路&#xff0c;i j表示改范围内是否为回文串&#xff0c; ②倒着遍历是为了取出dp[i 1][j - 1] ③i j 只有一对&#xff0c;不会重复…...

【阅读论文】When Large Language Models Meet Vector Databases: A Survey

摘要 本调查探讨了大型语言模型&#xff08;LLM&#xff09;和向量数据库&#xff08;VecDB&#xff09;之间的协同潜力&#xff0c;这是一个新兴但迅速发展的研究领域。随着LLM的广泛应用&#xff0c;出现了许多挑战&#xff0c;包括产生虚构内容、知识过时、商业应用成本高昂…...

兼职副业大揭秘:六个潜力满满的赚钱途径

亲爱的朋友&#xff0c;你对兼职副业充满好奇与期待&#xff0c;这非常好&#xff01;在此&#xff0c;我将为你分享一些能够助你赚取额外收入的兼职副业建议。以下是六个颇具潜力的兼职副业方向&#xff0c;希望能为你的探索之路提供些许启发。 1&#xff0c;网络调查与市场洞…...

C++ Qt开发:QUdpSocket实现组播通信

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QUdpSocket组件实现基于UDP的组播通信…...

excel 表中有图片并在筛选特定行时,只显示该行的图片

建议&#xff1a;选中excel 表中某张图片&#xff0c;CtrlA&#xff0c;选中所有图片。再右键&#xff0c;在菜单中选设置对象格式 在属性里按下图设置&#xff0c; 生效之后&#xff0c;筛选某个产品的时候&#xff0c;就不会显示其他的不符合筛选条件的产品的图片了。...

Node.js——事件的监听与触发

事件的监听与触发1、EventEmitter对象2、添加和触发监听事件2.1、添加监听事件2.2、添加单次监听事件2.3、触发监听事件3、删除监听事件1、EventEmitter对象 在JavaScript中&#xff0c;通过事件可以处理许多用户的交互&#xff0c;比如鼠标的单击、键盘按键的按下、对鼠标移动…...

微电网调度(风、光、储能、电网交互)附MatlabPython代码

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f34a;个人信条&#xff1a;格物致知,完整Matlab代码及仿真咨询…...

扩散模型之(十八)ControlNet 原理与指南

概述在当今瞬息万变的科技环境中&#xff0c;如何在人类创造力和机器精确性之间取得平衡变得日益重要。而这正是我们ControlNet发挥作用的地方——它如同“引导之手”&#xff0c;为基于扩散的文本到图像合成模型提供指导&#xff0c;从而解决传统图像生成模型中常见的局限性。…...

利用HunyuanVideo-Foley为游戏开发赋能:动态环境音效与技能音效生成实践

利用HunyuanVideo-Foley为游戏开发赋能&#xff1a;动态环境音效与技能音效生成实践 1. 游戏音效开发的痛点与机遇 在游戏开发过程中&#xff0c;音效设计往往是最容易被低估却又至关重要的环节之一。传统音效制作需要大量预录制音频素材&#xff0c;一个中型游戏项目动辄需要…...

NormalReconstructZ节点]原理解析与实际应用

的数据丢失问题&#xff0c;确保光照计算的准确性&#xff0c;是高质量实时渲染不可或缺的一环。该节点的设计充分考虑了现代图形硬件的特性&#xff0c;能够在保持高质量视觉效果的同时&#xff0c;显著降低内存带宽和存储空间的需求&#xff0c;特别适合移动平台和性能敏感的…...

如何用Win11Debloat让你的Windows系统速度提升70%:终极优化指南

如何用Win11Debloat让你的Windows系统速度提升70%&#xff1a;终极优化指南 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutt…...

DAMO-YOLO智能视觉系统作品集:多场景零售货架检测效果惊艳展示

DAMO-YOLO智能视觉系统作品集&#xff1a;多场景零售货架检测效果惊艳展示 1. 零售视觉检测的新标杆 走进现代零售空间&#xff0c;商品陈列的艺术背后隐藏着复杂的运营挑战。传统的人工巡检方式已经难以满足快节奏零售环境的需求&#xff0c;这正是DAMO-YOLO智能视觉系统大放…...

AI与数据库融合:从经典论文到前沿实践

1. AI与数据库融合的起源与演进 数据库和人工智能这两个看似独立的领域&#xff0c;其实早在计算机科学发展的初期就已经产生了交集。上世纪70年代&#xff0c;当关系型数据库理论刚刚确立时&#xff0c;研究者们就开始探索如何让数据库系统具备一定的"智能"。当时的…...

Pencil原型工具全攻略:从环境搭建到高级配置

Pencil原型工具全攻略&#xff1a;从环境搭建到高级配置 【免费下载链接】pencil DEPRECATED: Multiplatform GUI Prototyping/Wireframing 项目地址: https://gitcode.com/gh_mirrors/pen/pencil Pencil原型工具&#xff1a;开源价值定位与核心特性解析 核心价值&…...

SQL 基础及 MySQL DBA 运维实战 - 6:Mycat代理技术

MySQL DBA运维实战&#xff1a;集群与代理技术深度解析 引言 在现代互联网应用中&#xff0c;数据库的高可用性、可扩展性和性能是企业级应用的核心需求。随着业务量的增长&#xff0c;单一数据库服务器往往无法满足需求&#xff0c;此时数据库集群和代理技术成为解决这些问题…...