C++ | 仿函数与priority_queue

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

目录

前言

一、初始仿函数

1、仿函数是什么

2、仿函数的使用 

二、优先级队列

1、 优先级队列的基本概念

2、堆的储存结构与结点之前关系

3、堆的使用

4、堆的模拟实现


前言

        本文主要介绍优先级队列与仿函数,优先级队列实际上是我们在数据结构中学的堆;在介绍优先级队列之前,我们必须的初步的认识学习一下什么叫仿函数,与仿函数的使用;

一、初始仿函数

1、仿函数是什么

        仿函数实际上是一个重载了()的类;仿函数也叫对象函数;我们通过对象访问成员函数的方式调用函数;与其相对的是C语言的函数指针,因为C语言的函数指针在某些情况下太过于复杂,于是C++设计出了仿函数;

2、仿函数的使用 

        我们通过一下代码来学习仿函数的定义与使用; 

#include <functional>
// 带模板参数的仿函数
template<class T>
struct Greater
{
	// 重载()
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

void test_func()
{
	int x = 3;
	int y = 10;
	// 创建一个仿函数对象
	Greater<int> Gre;
	// 通过对象调用仿函数
	cout << Gre(x, y) << endl;
	// 通过匿名对象调用仿函数
	cout << Greater<int>()(x, y) << endl;
}
int main()
{
	test_func();
	return 0;
}

        我们通过重载对象里的圆括号,来实现用对象来模拟函数功能;而我们的优先级队列也巧妙的使用了仿函数,来实现通过模板参数控制我们实现的是大堆还是小堆;

二、优先级队列

1、 优先级队列的基本概念

        优先级队列在数据结构中又被称为堆,堆是一种完全二叉树结构;分为大堆与小堆;

大堆:父节点大于子节点

小堆:父节点小于父节点

C++ | 仿函数与priority_queue,C++,c++,开发语言

C++ | 仿函数与priority_queue,C++,c++,开发语言

        大小堆并没有要求左右孩子大小顺序,也就是说在任意堆中,左孩子可能大于右孩子,也可能小于右孩子;

2、堆的储存结构与结点之前关系

        一般情况下,我们用顺序结构储存堆,通过下标关系来定位孩子与父亲之间的关系;

父亲下标 = (孩子下标 - 1)/ 2

左孩子下标 = (父亲下标 * 2) + 1

右孩子下标 = (父亲下标 * 2) + 2

        我们可以通过下图尝试使用以上规则是否适用;

C++ | 仿函数与priority_queue,C++,c++,开发语言

3、堆的使用

堆有如下几个接口;使用成本也不高;

C++ | 仿函数与priority_queue,C++,c++,开发语言

void test_priority_queue()
{
	// 创建优先级队列
	std::priority_queue<int, vector<int>, greater<int>> pq;
	// 插入数据
	pq.push(13);
	pq.push(17);
	pq.push(23);
	pq.push(27);
	pq.push(33);
	pq.push(35);
	pq.push(43);
	pq.push(47);
	pq.push(54);
	pq.push(56);
	// 判空
	while (!pq.empty())
	{
		// 获得堆顶数据
		cout << pq.top() << " ";
		// 取出堆顶数据
		pq.pop();
	}
	cout << endl;

}

4、堆的模拟实现

        堆的模拟实现也不是很难,与前面的stack与queue一样,堆也是适配器容器,我们仅仅只需实现向上调整与向下调整两个接口即可,其他接口均复用;

#include <vector>
#include <functional>

namespace MySpace
{
	template<class T, class Container = std::vector<T>, class Compara = std::less<T>>
	class priority_queue
	{
	private:
		void adjust_up(size_t child)
		{
			// 计算父节点下标
			size_t parent = (child - 1) / 2;
			// 假若孩子结点已经为根节点了,则无法继续向上调整了
			while (child > 0)
			{
				// 通过仿函数比较父节点与子节点的大小关系
				if (Compara()(_con[parent], _con[child]))
				{
					// 条件满足,交换两个结点的值
					std::swap(_con[child], _con[parent]);
					// 计算下一个父节点,查看是否还需要向上调整
					child = parent;
					parent = (child - 1) / 2;
				}
				else // 否则退出循环,调整完毕
				{
					break;
				}
			}
		}
		void adjust_down(size_t parent)
		{
			// 计算孩子结点的下标
			size_t child = parent * 2 + 1;
			// 如果孩子结点大于最后一个数据的下一个位置的下标直接退出循环
			while (child < _con.size())
			{
				// 查看右孩子是否存在,若存在,是否比左孩子大或小
				if (child + 1 < _con.size() && Compara()(_con[child], _con[child + 1]))
				{
					child++;
				}
				// 拿大的(小的)那个孩子进行比较,查看是否需要交换
				if (Compara()(_con[parent], _con[child]))
				{
					// 交换父节点与子节点的数据
					std::swap(_con[child], _con[parent]);
					// 跟新父节点与子节点下标
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	public:
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
		const T& top() const
		{
			return _con.front();
		}
	private:
		Container _con;
	};

}

        在push函数中,我们插入一个数据会插入到尾部,此时我们需要向上调整,使堆重新恢复堆结构;

C++ | 仿函数与priority_queue,C++,c++,开发语言

        我们结合前面的知识,计算出父节点的下标,依次通过仿函数比较是否需要进行调整数据;关于向下调整,具体思路也一样,代码有具体注释;文章来源地址https://www.toymoban.com/news/detail-554002.html

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

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

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

相关文章

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

    本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。 priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆 在库的实现中,使用vector作为该优先级队列的适配容器。 由于priority_queue也是一个适配器,所以它的接口函数

    2024年02月16日
    浏览(47)
  • 【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

    这篇文章我们接着上一篇的内容,再来学一个STL里的容器适配器—— priority_queue (优先级队列) 1.1 priority_queue的介绍 我们上一篇文章学了 queue (队列),那优先级队列也是在 queue 里面的: 和 queue 一样, priority_queue 也是一个容器适配器,那他和 queue 有什么区别呢?我们一

    2024年02月07日
    浏览(48)
  • C++ queue&priority_queue

    目录 一、介绍 二、queue使用 三、模拟实现 四、优先级队列 五、priority_queue使用 OJ题:215. 数组中的第K个最大元素 快速排序 优先级队列 TOPK 六、模拟实现priority_queue 1、仿函数 2、优先级队列类 3、测试函数 1、队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,

    2024年02月01日
    浏览(49)
  • C++中的queue与priority_queue

      队列是一种容器适配器,专门用于上下文先进先出的操作中。队列的特性是先进先出,从容器的一端插入,另一端提取元素。   队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队

    2024年02月04日
    浏览(42)
  • stack_queue | priority_queue | 仿函数

    栈不在是一个容器,而是一个容器适配器 , stack的模板中第二个deque暂时不知道干什么的,后面会说 说明stack是一个容器适配器,并且为了保证严格的先进后出,所以不存在迭代器 这里假设我们不认识 deque,那么如果stack频繁使用pop尾删,将vector T 设置成缺省值也是非常适合

    2024年01月16日
    浏览(38)
  • C++ STL priority_queue

    目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数  1.什么是仿函数  2.控制大小堆  3.TopK问题 四.模拟实现priority_queue  1.priority_queue的主要接口框架  2.堆的向上调整算法  3.堆的向下调整算法  4.仿函数控制大小堆  五.priority_queue模拟实现整体代码和测试 priority_queue-

    2024年02月07日
    浏览(42)
  • STL之priority_queue与仿函数

    1.介绍 函数对象,又称仿函数,是可以像函数一样使用的对象,其原理就是重载了函数调用符: () 因此在此类中,一定有 operator() 的成员函数。 2.示例 如果T是内置类型,则直接进行比较。如果T是自定义类型,则会调用其operator()。 先创建一个_less类型的对象smaller,对于sma

    2024年02月10日
    浏览(41)
  • C++优先队列(priority_queue)详解

    目录 一、 定义 二、优先队列内元素访问 三、优先队列常用函数 四、优先队列内元素的优先级          优先队列(priority_queue),底层的数据结构为 堆(heap) ,以此 保证队首元素一定是当前队列所有元素中优先级最高的。 我们也可以随时往优先队里面加入(push)元素,其队

    2024年02月16日
    浏览(42)
  • C++中的优先队列(priority_queue)

    什么是优先队列 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有优先级最高先出的性质。通常采用堆数据结构来实现。

    2024年02月15日
    浏览(47)
  • 【C++】priority_queue使用与模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月16日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包