[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。

相关文章

Flutter实现文字镂空效果的详细步骤

Flutter实现文字镂空效果的详细步骤

《Flutter实现文字镂空效果的详细步骤》：本文主要介绍如何使用Flutter实现文字镂空效果,包括创建基础应用结构、实现自定义绘制器、构建UI界面以及实现颜色选择按钮等步骤,并详细解析了混合模... 目录引言实现原理开始实现步骤1：创建基础应用结构步骤2：创建主屏幕步骤3：实现自定义绘制器步骤4：构建U
阅读更多...
SpringBoot中四种AOP实战应用场景及代码实现

SpringBoot中四种AOP实战应用场景及代码实现

《SpringBoot中四种AOP实战应用场景及代码实现》面向切面编程(AOP)是Spring框架的核心功能之一,它通过预编译和运行期动态代理实现程序功能的统一维护,在SpringBoot应用中,AO... 目录引言场景一：日志记录与性能监控业务需求实现方案使用示例扩展：MDC实现请求跟踪场景二：权限控制与
阅读更多...
Android实现定时任务的几种方式汇总(附源码)

Android实现定时任务的几种方式汇总(附源码)

《Android实现定时任务的几种方式汇总(附源码)》在Android应用中,定时任务（ScheduledTask）的需求几乎无处不在：从定时刷新数据、定时备份、定时推送通知,到夜间静默下载、循环执行... 目录一、项目介绍1. 背景与意义二、相关基础知识与系统约束三、方案一：Handler.postDel
阅读更多...
使用Python实现IP地址和端口状态检测与监控

使用Python实现IP地址和端口状态检测与监控

《使用Python实现IP地址和端口状态检测与监控》在网络运维和服务器管理中,IP地址和端口的可用性监控是保障业务连续性的基础需求,本文将带你用Python从零打造一个高可用IP监控系统,感兴趣的小伙... 目录概述：为什么需要IP监控系统使用步骤说明1. 环境准备2. 系统部署3. 核心功能配置系统效果展
阅读更多...
Python实现微信自动锁定工具

Python实现微信自动锁定工具

《Python实现微信自动锁定工具》在数字化办公时代,微信已成为职场沟通的重要工具,但临时离开时忘记锁屏可能导致敏感信息泄露,下面我们就来看看如何使用Python打造一个微信自动锁定工具吧... 目录引言：当微信隐私遇到自动化守护效果展示核心功能全景图技术亮点深度解析1. 无操作检测引擎2. 微信路径智能获
阅读更多...
Python中pywin32 常用窗口操作的实现

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句
阅读更多...
在 Spring Boot 中实现异常处理最佳实践

在 Spring Boot 中实现异常处理最佳实践

《在SpringBoot中实现异常处理最佳实践》本文介绍如何在SpringBoot中实现异常处理,涵盖核心概念、实现方法、与先前查询的集成、性能分析、常见问题和最佳实践,感兴趣的朋友一起看看吧... 目录一、Spring Boot 异常处理的背景与核心概念1.1 为什么需要异常处理？1.2 Spring B
阅读更多...
Python位移操作和位运算的实现示例

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项：2. 位运算2.1
阅读更多...
如何在 Spring Boot 中实现 FreeMarker 模板

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出（如HTML、XML、邮件内容等）,本文... 目录什么是 FreeMarker 模板？在 Spring Boot 中实现 FreeMarker 模板1. 环
阅读更多...
Qt实现网络数据解析的方法总结

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理（处理粘包/拆包）3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2