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

2024-03-27 00:28
文章标签 实现 模拟 stl 迭代 反向 queue priority 类及

本文主要是介绍[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类及反向迭代器的模拟实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/850362。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注，收藏不迷路💖 Kubernetes的PodSecurityPolicy（PSP）是一个关键的安全特性，它在Pod创建之前实施安全策略，确保P
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2