【C++】STL使用仿函数控制优先级队列priority_queue

这篇具有很好参考价值的文章主要介绍了【C++】STL使用仿函数控制优先级队列priority_queue。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。



前言

本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。


一、priority_queue的底层实现

priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆
【C++】STL使用仿函数控制优先级队列priority_queue,C++,c++,开发语言,STL,priority_queue,仿函数,数据结构,容器
在库的实现中,使用vector作为该优先级队列的适配容器。

由于priority_queue也是一个适配器,所以它的接口函数也可以对其他容器的函数进行封装使用。

【C++】STL使用仿函数控制优先级队列priority_queue,C++,c++,开发语言,STL,priority_queue,仿函数,数据结构,容器
下面来对priority_queue进行模拟实现。


#pragma once

//优先级队列底层是堆,heap
namespace bit
{
	//仿函数
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& t1, const T& t2)
		{
			return t1 < t2;
		}

	};

	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& t1, const T& t2)
		{
			return t1 > t2;
		}

	};

	//类名不是类型
	template<class T, class Container = vector<T>, class Compare = Less<T> >
	//默认大堆
	class PriorityQueue
	{
		//com是一个仿函数
		Compare com;
		void AdjustDown(int parent)
		{
			int child = parent * 2 + 1;
			while (child > 0)
			{
				//可能右孩子存在且大于左孩子
				if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
				{
					++child;
				}
				//如果孩子存在且孩子大于父亲,交换
				if (child < _con.size() && com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustUp(int child)
		{
			Compare com;
			//类名实例化类对象,该类型是一个仿函数,实例化的com可以调用仿函数的比较方法
			//记录父亲的下标
			int parent = (child - 1) / 2;

			while (child > 0)
			{	
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
				}
				child = parent;
				parent = (child - 1) / 2;
			}
		}

	public:

		PriorityQueue()
		{}

		//默认建大堆
		template<class InputIterator>
		PriorityQueue(InputIterator first, InputIterator end)
		{
			//插入数据
			while (first != end)
			{
				_con.push_back(*first);
				++first;
			}
			//向下调整建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				AdjustDown(i);
			}
		}

		void push(const T& val)
		{
			//插入元素
			_con.push_back(val);
			//然后向上调整
			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			//1.堆顶和堆尾交换
			swap(_con[0], _con[_con.size() - 1]);

			//2.删除堆尾
			_con.pop_back();

			//3.向下调整,恢复堆
			AdjustDown(0);
		}

		T& top() 
		{
			 return _con[0];
		}
		
		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;

注解:

  • 1.在进行构造时,我们使用迭代区间进行构造
    • (1)向空间中插入数据
    • (2)向下调整建堆,建N个数据,从第一个非叶子节点开始进行建堆,每次都向下调整,时间复杂度O(N)。

push函数的实现:
向堆尾插入一个元素,插入的元素可能会改变堆的结构,所以我们需要将该元素向上调整,以维护堆的特性。

pop函数的实现:
删除堆顶元素,首先将堆顶元素和堆的最后一个元素进行交换,然后进行尾删,删除后原来的堆尾的元素现在在堆顶,我们需要将其进行向下调整以维持堆的状态。

empty函数:
判断堆是否为空即可。

size函数:
计算堆的元素个数。

top函数:
取堆顶元素,也就是取第一个元素。

priority_queue容器的作用:有需要使用堆的地方就可以使用该容器。

二、使用仿函数控制priority_queue的底层

什么是仿函数?
仿函数:仿造的函数,它并不是一个真正意义上的函数。能够重载operator(),内部实现自己想要的方法,然后实例化出一个方法对象,调用该对象作为参数,此时就可以调用该方法类对象内部实现的operator()方法了。

由于库中的优先级队列的底层结构是堆,且默认是大堆,我们在模拟实现和使用时,如果遇到需要使用小堆的场景,需要改变的东西很多,比如向上调整算法和向下调整算法的比较方法。
现在我们需要指定一个方法,这个方法可以由我们控制,从而实现大小堆。

仿函数:

//仿函数
template<class T>
class Less
{
public:
	bool operator()(const T& t1, const T& t2)
	{
		return t1 < t2;
	}

};

template<class T>
class Greater
{
public:
	bool operator()(const T& t1, const T& t2)
	{
		return t1 > t2;
	}

};

这里实现了两个类,并重载了一个比较方法。
在priority_queue模板的实现中,我们可以多传递一个模板参数:class Compare,也就是多传递一个比较方法。然后我们自己写一个比较方法传递过去,然后在priority_queue的实现中实例化一个方法对象来控制堆的生成。


总结

本文章讲解了仿函数控制priority_queue容器的底层实现的过程以及priority_queue的底层实现。

只要有堆的地方就可以使用priority_queue容器。文章来源地址https://www.toymoban.com/news/detail-602330.html

到了这里,关于【C++】STL使用仿函数控制优先级队列priority_queue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • STL:双端队列&容器适配器&仿函数&优先级队列

    双端队列可以在头部和尾部进行插入删除操作 与vector相比,头插效率高,不需要搬移元素 与list相比,空间利用率高 deque逻辑上空间是连续的,物理上并不是,是由一段段小空间拼接而成的 双端队列的迭代器比较复杂 cur:指向空间中被遍历的那个元素 first:指向空间开始

    2024年02月16日
    浏览(46)
  • 『C++ - STL』之优先级队列( priority_queue )

    什么是优先级队列,从该名中可以知道他一定有队列的一定属性,即先入先出(LILO),而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队,这就是优先级队列; 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中,这个

    2024年02月07日
    浏览(44)
  • 【C++初阶10-stack&queue】STL中的栈和队列(附优先级队列

    本期分享:STL中的栈和队列。 在数据结构初阶时,我们已经学习这来那个两种数据结构,如今来看STL中的,不过是更加标准化。而实现起来,会简单得超乎你想象! 文中不足错漏之处望请斧正! STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。 比如

    2024年02月06日
    浏览(47)
  • 【C++进阶(六)】STL大法--栈和队列深度剖析&优先级队列&适配器原理

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 和C语言学习期间的学习顺序一样 顺序表,链表过了就是栈和队列 但是栈和队列非常特殊,它的内部结构 并不是靠自己实现的,而是一种 适配

    2024年02月08日
    浏览(42)
  • [C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

    priority_queue文档介绍 翻译: 1. 优先队列是一种 容器适配器 ,根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于 堆 , 在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配

    2024年02月04日
    浏览(46)
  • 【C++】STL优先级队列(priority_queue)功能介绍以及模拟实现

    点进来的小伙伴不知道学过数据结构里的堆没有,如果学过的话,那就好说了,优先级队列就是堆,如果没学过,没关系,可以参考一下我之前写的一篇关于堆的博客,可以点进去看看:【数据结构】堆(包含堆排序和TOPK问题) 那么了解过堆了的话,我就不讲那么细致了,

    2024年02月16日
    浏览(49)
  • 【C++】详解priority_queue(优先级队列)与函数对象

    目录 一、priority_queue 的介绍和使用 1.1priority_queue 的介绍 2.2priority_queue 的使用 二、仿函数 2.1什么是仿函数 2.2仿函数的作用 三、函数对象的特点(知识点多) 3.1分析特点5(比较普通函数与函数对象) 3.1.1利用普通函数传递参数 拓展之:深度剖析函数利用模板的本质 3.1.2利用

    2024年02月08日
    浏览(40)
  • 【STL】优先级队列剖析及模拟实现

    ✍ 作者 : 阿润菜菜 📖 专栏 : C++ 优先队列是一种 容器适配器 ,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的(默认大堆)。优先级队列的内部实现通常是用 堆 来维护元素的优先级,使得每次出队的元素都是当前队列中优先级最高的元素。 优先

    2023年04月22日
    浏览(43)
  • 【STL】优先级队列&反向迭代器详解

    目录 一,栈_刷题必备 二,stack实现 1.什么是容器适配器 2.STL标准库中stack和queue的底层结构  了解补充:容器——deque  1. deque的缺陷 2. 为什么选择deque作为stack和queue的底层默认容器 三,queue实现 1. 普通queue  2,优先级队列(有难度) 1. 功能 2. 模拟实现 1). 利用迭代器_构造

    2024年02月13日
    浏览(40)
  • 【C++_STL】优先级队列&反向迭代器详解

    目录 一,栈_刷题必备 二,stack实现 1.什么是容器适配器 2.STL标准库中stack和queue的底层结构  了解补充:容器——deque  1. deque的缺陷 2. 为什么选择deque作为stack和queue的底层默认容器 三,queue实现 1. 普通queue  2,优先级队列(有难度) 1. 功能 2. 模拟实现 1). 利用迭代器_构造

    2024年02月09日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包