[ C++ ] STL---仿函数与priority_queue

目录

仿函数

示例一：

示例二 :

常见的仿函数

priority_queue简介

priority_queue的常用接口

priority_queue的模拟实现

基础接口

push()

堆的向上调整算法

堆的插入

pop()

堆的向下调整算法

堆的删除

priority_queue最终实现

仿函数

仿函数（Functor）是一个类/结构体，其内部重载了operator()运算符，使其可以像函数一样被调用；

  1. 由于模版参数接收类型，仿函数是一个类，可以通过 类名/类名<数据类型> 传递给模版参数；
  2. 仿函数是一个类，则其可以定义对象，对象调用operator()完成控制作用；

示例一：

//带模版参数的仿函数
template<class T>
struct Greater
{
	//重载operator()
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
void Func()
{
	int x = 10;
	int y = 20;
	//创建一个仿函数对象
	Greater<int> Great;
	//通过对象调用仿函数
	cout << Great(x, y) << endl;
	//cout<<Great.operator()(x,y)<<endl;
	//通过匿名对象调用仿函数
	cout << Greater<int>()(x, y) << endl;
}
int main()
{
	Func();
	return 0;
}

示例二 :

//此模版参数接收数据类型
template<class T>
struct Greater
{
	//重载operator()称为仿函数/函数对象
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
//此模版参数接收仿函数类型
template<class compare>
class A
{
public:
	void func(int a, int b)
	{
		compare com;
		cout << com(a, b) << endl;
		//com(a,b)--->com.operator()(a,b)--->com为仿函数对象
	}
};

int main()
{
	//A类中传递仿函数类型Greater<T>-->仿函数类中传递数据类型Greater<int>
	A<Greater<int>> aa1;
	aa1.func(10, 20);

	A<Greater<int>>aa2;
	aa2.func(20, 10);
	return 0;
}

具有相同功能的代码可以在不同的类中用到，但是不好将功能相同的代码实现成某一个类的成员函数，仿函数实现了一个简单的类，将需要复用的代码实现在operator()重载函数中，外部函数需要使用时只要用这个类实例化出一个对象，就可以像使用函数一样来使用这个对象，完成对应功能；

常见的仿函数

template <class T> 
struct less 
{
  bool operator() (const T& x, const T& y) const 
  {
       return x<y;
  }
};
//std::less<T>: 对于基本数据类型和自定义类型，默认使用<运算符进行比较;

template <class T> 
struct greater 
{
  bool operator() (const T& x, const T& y) const 
  {
       return x>y;
  }
};
//std::greater<T>: 对于基本数据类型和自定义类型，默认使用>运算符进行比较;

除了c++标准库所提供的仿函数外，可以自定义仿函数来实现自定义的元素比较规则，自定义仿函数需要满足严格弱排序的要求，即：

  • 比较关系必须是可传递的：对于任意元素a、b和c，如果a与b比较相等，b与c比较相等，则a与c比较也相等；
  • 比较关系不能是部分顺序：对于任意元素a和b，它们不能同时大于、小于或等于彼此；
  • 比较关系必须是可比较的：比较关系的结果必须对所有元素定义明确的大小关系；

priority_queue简介

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的；

2. 优先队列的底层数据结构为堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)；

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的"尾部"弹出，其称为优先队列的顶部；

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作:

  • empty()：检测容器是否为空
  • size()：返回容器中有效元素个数
  • front()：返回容器中第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求；默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector；

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构；容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作；

注意：

  1. 由于优先队列底层数据结构为堆，堆的删除是删除堆顶数据，首先将堆顶数据与最后一个数据交换位置，其次删除数组中最后一个元素，所以容器中要求pop_back()；
  2. 由于优先队列底层数据结构为堆，堆的插入是数组的尾元素的下一个位置插入数据，然后利用向上调整算法调整为堆，所以容器中要求push_back()；
  3. 默认情况下，priority_queue使用std::less作为比较函数，创建的是大堆；如果需要按照从小到大的顺序排列，可以使用std::greater作为比较函数，创建的是小堆；

堆的相关知识点回顾：数据结构之堆-CSDN博客

priority_queue官方文档：priority_queue - C++ Reference

priority_queue的常用接口

int main()
{
    //未给定仿函数比较方式,默认创建大根堆
	priority_queue<int, vector<int>> pq;
	//尾插数据
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(2);
	pq.push(3);
	cout << "size=" << pq.size() << endl;
	while (!pq.empty())
	{
		//取堆顶数据
		cout << pq.top() << " ";
		//删除堆顶元素
		pq.pop();
	}
	cout << endl;
	return 0;
}

运行结果：

int main()
{
    //给定比较方式为greater,创建小根堆
	priority_queue<int, vector<int>,greater<int>> pq;
	//尾插数据
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(2);
	pq.push(3);
	cout << "size=" << pq.size() << endl;
	while (!pq.empty())
	{
		//取堆顶数据
		cout << pq.top() << " ";
		//删除堆顶元素
		pq.pop();
	}
	cout << endl;
	return 0;
}

运行结果：

priority_queue的模拟实现

基础接口

#include <iostream>
#include <vector>
template<class T, class Container = vector<T>>
class priority_queue
{
public:
	//获取堆顶元素即数组首元素
	const T& top()
	{
		return _con[0];
	}
	//获取堆的数据个数即容器中的数据个数
	size_t size()
	{
		return _con.size();
	}
	//检测堆是否为空即容器是否为空
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

push()

堆的存储结构为数组，尾插时间复杂度O(1)，首先将元素插入到数组的尾部，其次利用堆的向上调整算法，将数组调整为大根堆/小根堆；

堆的向上调整算法

case 1:

当插入的数值M大于其父节点的值时，仍然为小堆，此时不做任何调整；

case 2:

当插入的数值M小于其父节点的值时，破坏了堆的逻辑结构，向上调整为小堆；

（假设M=5）

向上调整的过程中，只要出现待调整的孩子结点大于其父节点，便可停止调整，已经满足小堆的逻辑结构；

//向上调整为小堆
void adjustup(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[child] < _con[parent])
		{
			//交换
			swap(_con[child], _con[parent]);
			//向上走
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向上调整为大堆
void adjustup(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[child] > _con[parent])
		{
			//交换
			swap(_con[child], _con[parent]);
			//向上走
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的插入

void push(const T& val)
{
	//插入数据
	_con.push_back(val);

	//从插入值为val的孩子结点的下标开始向上调整为小堆/大堆
	adjustup(_con.size()-1);
}

pop()

堆的删除是删除堆顶数据，首先将堆顶元素与堆中最后一个元素交换，其次删除堆中最后一个元素，最后将堆顶元素利用向下调整算法调整到满足其逻辑结构为堆；

注：堆的向下调整算法的前提左右子树同为小堆/同为大堆；

堆的向下调整算法

case 1：左右子树皆为小堆，向下调整为小堆；

//向下调整为小堆
void adjustdown(size_t parent)
{
	size_t child = 2 * parent + 1;
	while (child < _con.size())
	{
		//假设法求同一层孩子节点最小者
		if (child + 1 < _con.size() && _con[child] > _con[child + 1])
		{
			child++;
		}
		//逻辑关系不满足小堆，交换调整
		if (_con[child] < _con[parent])
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

case 2：左右子树皆为大堆，向下调整为大堆；

//向下调整为大堆
void adjustdown(size_t parent)
{
	size_t child = 2 * parent + 1;
	while (child < _con.size())
	{
		//假设法求同一层孩子节点最大者
		if (child + 1 < _con.size() && _con[child] < _con[child + 1])
		{
			child++;
		}
		//逻辑关系不满足大堆，交换调整
		if (_con[child] > _con[parent])
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

堆的删除

void pop()
{
	//将堆顶元素与堆中最后一个元素交换
	swap(_con[0], _con[size() - 1]);
	//删除最后一个元素
	_con.pop_back();
	//将堆顶元素利用向下调整算法调整到满足其逻辑结构为堆
	adjustdown(0);
}

priority_queue最终实现

堆分为大根堆与小根堆，向上调整算法/向下调整算法对于大根堆/小根堆的实现只有各别符号的差别，外部使用优先队列（priority_queue）时，只能在内部手动修改相应的符号来控制生成的是大堆/小堆，对于使用者而言，只能创建大堆/小堆，两者只能实现一个，故引入第三个模版参数传递仿函数类型，指定比较方式，此时使用者只需给定比较方式便可在大小堆之间自由切换；

注意：由于容器中一开始没有数据，故不用建堆，它是每插入一个数据，调用向上调整法，删除数据，调用向下调整法，不断地插入和删除，并且使其保持堆的逻辑结构 ；

#include <iostream>
#include <vector>
#include <functional>
using namespace std;
template<class T, class Container =vector<T>, class Compare = 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[0];
	}
	T& top()
	{
		return _con[0];
	}
	//向上调整算法
	void adjustup(size_t child)
	{
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			//_con[parent]<_con[child],父节点小于其孩子节点，交换向上调整--->大堆
			if (_cmp(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& val)
	{
		_con.push_back(val);
		adjustup(_con.size() - 1);
	}
	//向下调整算法
	void adjustdown(size_t parent)
	{
		size_t child = parent * 2 + 1;
		while (child <_con.size())
		{
			 //child+1< _con.size()保证右孩子结点存在
			//less<T> _cmp ---> _con[child]<_con[child+1]--->child++ --->挑选大的孩子结点
			if (child + 1 < _con.size() && _cmp(_con[child], _con[child + 1]))
			{
				child++;
			}
			//_con[parent]<_con[child],父节点小于其孩子结点,交换向下调整---->大堆
			if (_cmp(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	void pop()
	{
		swap(_con[0], _con[_con.size()-1]);
		_con.pop_back();
		adjustdown(0);
	}
private:
	Container _con;
	Compare _cmp;//less<T> _cmp;
};

欢迎大家批评指正，博主会持续输出优质内容，谢谢大家观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/490493.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于stm32与TJC3224T124_011串口屏的PID调参器（附完整工程）

基于stm32与TJC3224T124_011串口屏的PID调参器（附完整工程）

电赛在即&#xff0c;每次比赛调PID都是一件比较繁琐的事。每次都要在程序中改完再烧录到板子上&#xff0c;特别耗时。正好最近发现实验室的一块串口屏比较好玩。 于是就做了这个调PID的东西。它可以通过串口直接修改PID的值&#xff0c;从而达到快速调PID的目的。下面我将完整…
阅读更多...
【Python】学习率调整策略详解和示例

【Python】学习率调整策略详解和示例

学习率调整得当将有助于算法快速收敛和获取全局最优&#xff0c;以获得更好的性能。本文对学习率调度器进行示例介绍。 学习率调整的意义基础示例无学习率调整方法学习率调整方法一多因子调度器余弦调度器 结论 学习率调整的意义 首先&#xff0c;学习率的大小很重要。如果它…
阅读更多...
音乐制作利器 ：FL Studio21中文编曲音乐制作软件免费下载

音乐制作利器 ：FL Studio21中文编曲音乐制作软件免费下载

一、引言 在音乐的世界里&#xff0c;每个人都有自己独特的音色和表达方式。而今天&#xff0c;我们要为你推荐一款能让您的音乐创作更上一层楼的神器——FL Studio21中文编曲音乐制作软件。这款功能强大的音乐制作软件&#xff0c;不仅拥有丰富的音色库和高效的编辑功能&#…
阅读更多...
Quartz

Quartz

Quartz 1.核心概念1.1 核心概念图1.2 demo 2.Job2.1为什么设计成JobDetailJob, 而不直接使用Job2.2 间隔执行时, 每次都会创建新的Job实例2.3 定时任务默认都是并发执行的&#xff0c;不会等待上一次任务执行完毕2.3.1 不允许并发执行 2.4 在运行时, 通过JobDataMap向Job传递数…
阅读更多...
Python自动化测试环境搭建

Python自动化测试环境搭建

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号&#xff1a;互联网杂货铺&#xff0c;回复1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 请事先自行安装好​​Pycharm​​​软件哦&#xff0c;我…
阅读更多...
深度学习模型部署(十二)CUDA编程-绪

深度学习模型部署(十二)CUDA编程-绪

CUDA 运行时 API 与 CUDA 驱动 API 速度没有差别&#xff0c;实际中使用运行时 API 较多&#xff0c;运行时 API 是在驱动 API 上的一层封装。​ CUDA 是什么&#xff1f;​ CUDA(Compute Unified Device Architecture) 是 nvidia 推出的一个通用并行技术架构&#xff0c;用它…
阅读更多...
基于冠豪猪优化器（CPO）的无人机路径规划

基于冠豪猪优化器（CPO）的无人机路径规划

该优化算法是2024年新发表的一篇SCI一区top论文具有良好的实际应用和改进意义。一键运行main函数代码自动保存高质量图片 1、冠豪猪优化器 摘要&#xff1a;受冠豪猪(crest Porcupine, CP)的各种防御行为启发&#xff0c;提出了一种新的基于自然启发的元启发式算法——冠豪猪…
阅读更多...
视觉轮速滤波融合1讲：理论推导

视觉轮速滤波融合1讲：理论推导

视觉轮速滤波融合理论推导 文章目录 视觉轮速滤波融合理论推导1 坐标系2 轮速计2.1 运动学模型2.2 外参 3 状态和协方差矩阵3.1 状态3.2 协方差矩阵 4 Wheel Propagation4.1 连续运动学4.2 离散积分4.2.1 状态均值递推4.2.2 协方差递推 5 Visual update5.1 视觉残差与雅可比5.2…
阅读更多...
蓝桥杯2023年第十四届省赛真题-买瓜|DFS+剪枝

蓝桥杯2023年第十四届省赛真题-买瓜|DFS+剪枝

题目链接&#xff1a; 0买瓜 - 蓝桥云课 (lanqiao.cn) 蓝桥杯2023年第十四届省赛真题-买瓜 - C语言网 (dotcpp.com) &#xff08;蓝桥官网的数据要求会高一些&#xff09; 说明&#xff1a; 这道题可以分析出&#xff1a;对一个瓜有三种选择&#xff1a; 不拿&#xff0c…
阅读更多...
Vue3基础笔记（2）事件

Vue3基础笔记（2）事件

一.事件处理 1.内联事件处理器 <button v-on:click"count">count1</button> 直接将事件以表达式的方式书写~ 每次单击可以完成自增1的操作~ 2.方法事件处理器 <button click"addcount(啦啦啦~)">count2</button> 如上&…
阅读更多...
每日必学Linux命令：mv命令

每日必学Linux命令：mv命令

mv命令是move的缩写&#xff0c;可以用来移动文件或者将文件改名&#xff08;move (rename) files&#xff09;&#xff0c;是Linux系统下常用的命令&#xff0c;经常用来备份文件或者目录。 一&#xff0e;命令格式&#xff1a; mv [选项] 源文件或目录 目标文件或目录二&am…
阅读更多...
Open WebUI大模型对话平台-适配Ollama

Open WebUI大模型对话平台-适配Ollama

什么是Open WebUI Open WebUI是一种可扩展、功能丰富、用户友好的大模型对话平台&#xff0c;旨在完全离线运行。它支持各种LLM运行程序&#xff0c;包括与Ollama和Openai兼容的API。 功能 直观的界面:我们的聊天界面灵感来自ChatGPT&#xff0c;确保了用户友好的体验。响应…
阅读更多...
轻松掌握C语言中的sqrt函数，快速计算平方根的魔法秘诀

轻松掌握C语言中的sqrt函数，快速计算平方根的魔法秘诀

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…
阅读更多...
第1章 实时3D渲染流水线

第1章 实时3D渲染流水线

前言 本书所剖析的Unity 3D内置着色器代码版本是2017.2.0f3&#xff0c;读者可以从Unity 3D官网下载这些着色器代码。这些代码以名为builtin_shaders-2017.2.0f3.zip的压缩包的形式提供&#xff0c;解压缩后&#xff0c;内有4个目录和1个license.txt文件。 目录CGIncludes存放了…
阅读更多...
苍穹外卖项目-01（开发流程，介绍，开发环境搭建，nginx反向代理，Swagger）

苍穹外卖项目-01（开发流程，介绍，开发环境搭建，nginx反向代理，Swagger）

目录 一、软件开发整体介绍 1. 软件开发流程 1 第1阶段: 需求分析 2 第2阶段: 设计 3 第3阶段: 编码 4 第4阶段: 测试 5 第5阶段: 上线运维 2. 角色分工 3. 软件环境 1 开发环境(development) 2 测试环境(testing) 3 生产环境(production) 二、苍穹外卖项目介绍 …
阅读更多...
Docker搭建LNMP环境实战（05）：CentOS环境安装Docker-CE

Docker搭建LNMP环境实战（05）：CentOS环境安装Docker-CE

前面几篇文章讲了那么多似乎和Docker无关的实战操作&#xff0c;本篇总算开始说到Docker了。 1、关于Docker 1.1、什么是Docker Docker概念就是大概了解一下就可以&#xff0c;还是引用一下百度百科吧&#xff1a; Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以…
阅读更多...
SE注意力模块学习笔记《Squeeze-and-Excitation Networks》

SE注意力模块学习笔记《Squeeze-and-Excitation Networks》

Squeeze-and-Excitation Networks 摘要引言什么是全局平均池化&#xff1f; 相关工作Deep architectures Squeeze-and-Excitation Blocks3.1. Squeeze: Global Information Embedding3.2. Excitation: Adaptive Recalibration3.3. Exemplars: SE-Inception and SE-ResNet 5. Im…
阅读更多...
百科词条编辑必备指南，让你轻松上手创建

百科词条编辑必备指南，让你轻松上手创建

1.注册账号&#xff1a;首先&#xff0c;你需要注册一个百科平台的账号。例如&#xff0c;对于百度百科&#xff0c;你需要有一个百度账号。 搜索词条&#xff1a;在百科全书平台上搜索您想要编辑的词条。如果词条已经存在&#xff0c;可以直接编辑&#xff1b;如果词条不存在&…
阅读更多...
(已解决)vue3使用富文本出现样式乱码

(已解决)vue3使用富文本出现样式乱码

我在copy代码到项目里面时候发现我的富文本乱码了 找了一圈不知道是哪里vue3不适配还是怎么&#xff0c;后来发现main.js还需要引入 import VueQuillEditor from vue-quill-editor // require styles 引入样式 import quill/dist/quill.core.css import quill/dist/quill.snow…
阅读更多...
计算机组成原理（超详解！！） 第三节 运算器（浮点加减乘）

计算机组成原理（超详解！！） 第三节 运算器（浮点加减乘）

1.浮点加法、减法运算 操作过程 1.操作数检查 如果能够判断有一个操作数为0&#xff0c;则没必要再进行后续一系列操作&#xff0c;以节省运算时间。 2.完成浮点加减运算的操作 (1) 比较阶码大小并完成对阶 使二数阶码相同&#xff08;即小数点位置对齐&#xff09;…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站