STL之priority_queue与仿函数

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

一.仿函数

1.介绍

函数对象,又称仿函数,是可以像函数一样使用的对象,其原理就是重载了函数调用符:()

因此在此类中,一定有operator()的成员函数。

2.示例

template<class T>
struct _less
{
    //lhs:left-hand side
	bool operator() (const T& lhs, const T& rhs)
	{
		return lhs < rhs;
	}
};

如果T是内置类型,则直接进行比较。如果T是自定义类型,则会调用其operator<()。
STL之priority_queue与仿函数

先创建一个_less类型的对象smaller,对于smaller(),则调用其operator()函数

二.priority_queue

1.介绍

STL之priority_queue与仿函数

priority_queue,也是一种容器适配器:class Container = vector<T>,底层默认为vector

同时,对于其元素存储,类似于大/小 堆(父节点大于(小于)子节点的值),根据某种排序标准,使它的第一个元素总是其所有元素中最大/小的。

是按大还是小来存储,通过第3个模板参数来规定

class Compare= less<T>,缺省为less,即第一个元素总是最大的(其他插入的元素都比第一个less)。

2.成员函数

STL之priority_queue与仿函数

3.模拟实现

可以根据大小堆的算法,进行模拟实现
数据结构——堆

#include <vector>
#include <functional>
namespace yyjs
{
	template<class T, class Container = std::vector<T>,class Compare = std::less<T>>
	class priority_queue
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& top() const
		{
			return _con.front();
		}
		T& top() 
		{
			return _con.front();
		}
        
		//从child位置开始向上调整,直到符合Compare的规则
		void AdjustUp(size_t child)
		{
            //根据二叉树,求出父节点的位置
			size_t parent = (child - 1) / 2;
            
            //如果当前当前节点不是根节点,且其父节点与当前节点进行比较,符合规则
			while (child > 0 && _cmp(_con[parent], _con[child]))
			{
                //交换当前节点与其父节点的值
                std::swap(_con[parent], _con[child]);
                child = parent;
                parent = (child - 1) / 2;	
			}
		}
    	//尾插入一个节点,并将这个节点按规则进行调整
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(size() - 1);
		}
        //从parent位置开始向下进行调整,使其符合Compare规则
		void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;//左孩子
			//当其子节点在有效范围内
            while (child < size())
			{	
                //如果有右节点其右节点更大(小),选择右节点
				if (child + 1 < size() && _cmp(_con[child],_con[child + 1]))
				{
					child++;
				}
                //当前节点与其子节点进行比较,符合规则,进行交互
				if (_cmp(_con[parent], _con[child]))
				{
					::swap(_con[parent],_con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
        //删除第一个元素,然后将剩余元素按规则调整
		void pop()
		{
            //先交换首尾元素,然后再删尾元素
			std::swap(_con.back(), _con.front());
			_con.pop_back();
            //把交换上去的首元素向下调整,使符合规则
			AdjustDown(0);
		}

	private:
		Container _con;
		Compare _cmp;
	};
}

4.使用

STL之priority_queue与仿函数

三.其他

1.typename Container::value_type

STL之priority_queue与仿函数

在less的显示实例化时,所传入的typename Container::value_type类型,所代表的是:Container类中定义的value_type类型

因为class Container = vector<T>,以vector示例:
STL之priority_queue与仿函数

using:相当于typedef

由此可见typename Container::value_type其实就相当于T类型,只是库中的更加规范


🦀🦀观看~~文章来源地址https://www.toymoban.com/news/detail-495616.html

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

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

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

相关文章

  • 【STL】priority_queue的使用及模拟实现

    目录 前言 priority_queue的使用 功能解析 基本接口 写点题目 模拟实现 结构解析 插入删除 调整函数结合仿函数 仿函数介绍 结合使用 其他功能 接口补齐 迭代器区间构造 🍾打开 queue 头文件后,我们发现除了我们之前介绍过的普通队列以外,还有一个 priority_queue 。 🍾其又名为

    2024年02月08日
    浏览(40)
  • 【STL详解 —— priority_queue的使用与模拟实现】

    std::priority_queue 是 C++ 标准库中的容器适配器,它提供了一种基于堆的优先级队列实现。优先级队列是一种特殊的队列,其中的元素按照一定的优先级顺序排列,而不是按照它们被插入的顺序。 在 std::priority_queue 中,插入元素时会根据元素的值自动进行排序,最大(或最小)

    2024年04月17日
    浏览(31)
  • 【C++】STL之priority_queue类源码剖析

    目录 概述 算法 源码 PriorityQueue.h test.cpp 测试结果 priority_queue:优先级队列,包含在头文件queue中 优先级队列类似于堆结构,优先级最高的元素被置为堆顶,最优先被弹出top()和删除pop() 优先级队列的默认调整策略是大根堆,也就是最大值在堆顶 自定义类型需要用户自己提供

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

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

    2024年02月07日
    浏览(45)
  • c++11 标准模板(STL)(std::priority_queue)(四)

    template     class T,     class Container = std::vectorT,     class Compare = std::lesstypename Container::value_type class priority_queue; priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。 可用用户提供的 Compare 更改顺序,例如,用 std::greaterT 将导致最小元

    2024年02月01日
    浏览(45)
  • 【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

    ⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象

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

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

    2024年02月16日
    浏览(49)
  • 容器适配器---deque和STL ---stack queue priority_queue的模拟实现 C++

    目录 一、容器适配器 deque原理 deque的缺陷 deque的优势 二、stack的模拟实现  三、queue的模拟实现 四、优先级队列的模拟实现 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户

    2024年02月02日
    浏览(55)
  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 例如我们常见的充电器就是一种适配器,它将我们常用的220V交流电压转化为4,5V (或者其他更高的电

    2023年04月26日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包