23. C++STL 9 (priority_queue的使用和适配实现详解)

⭐本篇重点：

1 priority_queue的使用与底层原理

2 使用容器来适配 priority_queue

⭐本篇代码：c++学习 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

⭐标⭐是比较重要的部分

目录

一. priority_queue（优先级队列）的使用与原理

1.1 priority_queue的底层原理⭐

1.2 STL中 priority_queue的原型与函数接口

1.3 prioirty_queue的使用举例

 二. 使用模板模拟实现priority_queue

2.1 priority_queue的代码框架

2.2 比较器的仿函数和默认适配容器

2.3 向下调整算法 adjustdown ⭐

2.4 向上调整算法adjustup⭐

2.5 push

2.6 pop

2.7 代码与测试1 

2.8 测试2 

三. 简单总结一下STL六大组件

四. 下篇内容： 模板的进阶使用

 

一. priority_queue（优先级队列）的使用与原理

1.1 priority_queue的底层原理⭐

        priority_queue（优先级队列）的本质是一个二叉堆。对于堆的介绍和理解以及堆的常见用法，可以看我的这两篇文章：

6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）_c++实现堆的向上调整-CSDN博客

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）_堆排序c++代码实现-CSDN博客

        简单来说，堆是一个使用数组来表示完全二叉树的数据结构。堆分为大根堆，小根堆。堆常用于堆排序，处理TopK问题，频繁的插入和删除元素场景下获取最大，最小元素。

 

1.2 STL中 priority_queue的原型与函数接口

在文档中priority_queue的函数原型如下：

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

其中，第一个参数是priority_queue存储的数据。

第二个参数是priority_queue的适配器（使用什么容器适配priority_queue）。

第三个参数是如何去比较这个优先级队列的比较函数

 

priority_queue的函数接口如下表：

函数接口说明
push()在priority_queue中插入一个数据
pop()在priority_queue中删除一个数据
size()获取priority_queue中元素的个数
empty()判断priority_queue是否为空
top()获取priority_queue堆顶的数据

注意： 在STL中，priority_queue的默认是大根堆。

 

1.3 prioirty_queue的使用举例

举例代码1：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void test1()
{
	//1. 测试默认的大根堆 priority_queue
	//数据类型是int，使用vector适配，比较函数设置为默认
	priority_queue<int, vector<int>> pq1;
	
	//在优先级队列中插入10个随机数字
	for (int i = 0; i < 10; i++)
	{
		pq1.push(rand() % 10000);
	}

	//priority_queue没有迭代器。只能边删除边访问
	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;
}

int main()
{
	srand((unsigned int)time(0));
	test1();
}

测试结果：

913e5d03332d4706b8b5ed7b3c2f17bf.png

 举例代码2

通过第三个参数来控制大根堆，小根堆

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

template<class T>
struct Compare
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

void test1()
{
	//2. 使用系统自带的greater生成小根堆
	priority_queue<int, vector<int>, greater<int>> pq1;
	
	//在优先级队列中插入10个随机数字
	for (int i = 0; i < 10; i++)
	{
		pq1.push(rand() % 10000);
	}

	//priority_queue没有迭代器。只能边删除边访问
	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;

	//2.使用仿函数生成自定义的比较函数
	priority_queue<int, vector<int>, Compare<int>> pq2;

	for (int i = 0; i < 10; i++)
	{
		pq2.push(rand() % 10000);
	}

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;
}

int main()
{
	srand((unsigned int)time(0));
	test1();
}

测试结果如下：

de5f472d343a4cabbf8af49d30e9821c.png

 二. 使用模板模拟实现priority_queue

2.1 priority_queue的代码框架

根据优先级队列的原型和接口，我们可以写出其框架。代码如下

类模板中有三个参数，T是数据类型，Container是使用的适配器，Compare是比较器

#pragma once
#include <vector>

namespace YZC
{	
	//小于比较的仿函数
	template<class T>
	struct less
	{};

	//大于比较的仿函数
	template<class T>
	struct greater
	{};

	//priority_queue容器适配器
	template<class T, class Container, class Compare>
	class priority_queue
	{
	public:
		void push(const T& x)
		{}

		T pop()
		{}

		T& top()
		{}

		void size()
		{}

		bool empty()
		{}
	private:
		Container<T> _con;	//适配的成员变量
	};
}

2.2 比较器的仿函数和默认适配容器

        在这里，使用vector作为默认的适配容器。使用less作为默认的比较器

代码如下：其中两个仿函数比较简单，less返回a < b，gerater返回a > b 即可

#pragma once
#include <vector>

namespace YZC
{	
	//小于比较的仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& a, const T&b)
		{
			return a < b;
		}
	};

	//大于比较的仿函数
	template<class T>
	struct greater
	{
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};

	//priority_queue容器适配器
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void push(const T& x)
		{}

		T pop()
		{}

		T& top()
		{}

		void size()
		{}

		bool empty()
		{}
	private:
		Container _con;	//适配的成员变量
	};
}

2.3 向下调整算法 adjustdown ⭐

        为了保持堆结构的完整性，我们需要使用调整算法进行调整。其中一个是向下调整算法。该算法用于将一个左右子树都满足堆结构的根节点向下调整，让整个堆都满足堆结构。

        调整算法的逻辑可以看我的这篇文章。6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）_c++实现堆的向上调整-CSDN博客

        简单的说，就是将根节点向下浮动，在不满足堆结构的情况下（大根堆交换子节点中大的数据，小根堆交换子节点中小的数据）

代码如下：部分难以理解的逻辑在注释中

        void adjustdown(size_t root)
		{
			Compare com{};	//比较器，less是大根堆，greater是小根堆
			size_t parent = root;
			size_t child = root * 2 + 1;	//默认是其左孩子

			while (child < _con.size())
			{
				//child+1 < _con.size() 用于判断有无右孩子，使用com来获取比较的结果
				//由于默认是less的大根堆，我们要获取大的孩子,当
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}
				//这样child默认是较大的孩子

				//此时如果父亲比孩子小，就需要交换
				if (com(_con[parent], _con[child]))
				{
					//交换父子节点
					swap(_con[parent], _con[child]);
					
					//重新更新父子节点
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					//说明这个结构是正确的不需要交换，直接跳出循环即可
					break;
				}

			}
		}

2.4 向上调整算法adjustup⭐

        将插入到最后的节点，通过向上调整让整个优先级队列结构合法

代码如下：

        void adjustup(size_t child)
		{
			Compare cmp{};
			//将最后一个节点的数据向上移动
			size_t parent = (child - 1) >> 1;
			while (child > 0)
			{
				//默认使用仿函数less，子节点比父节点大就要交换
				if (cmp(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);

					child = parent;
					parent = (child - 1) >> 1;
				}
				else
				{
					//说明整个结构是合法的
					break;
				}
			}
		}

2.5 push

        priority_queue每一次插入数据都在尾部插入数据，所以我们需要插入数据后，对这个数据进行向上调整

代码如下：

        void push(const T& x)
		{
			//1.插入数据
			_con.push_back(x);
			//2.向上调整
			adjustup(static_cast<size_t>(_con.size() - 1);
		}

2.6 pop

        这个函数用于删除priority_queue堆顶的数据。根据二叉堆的结构，在删除堆顶数据之后需要重新调整整个堆。

        所以我们的思路应该是：1 交换堆顶数据和最后一个数据（保证删除堆顶数据之后除了堆顶的左右子树都是合法堆结构）2 删除交换到堆尾的数据，然后对堆顶使用向下

代码如下：

        T pop()
		{
			assert(_con.size() > 0);	//有数据才能删除
			T ret = _con[0];	//保存堆顶数据用于返回
			//1.交换堆顶堆尾的数据
			swap(_con[0], _con[_con.size() - 1]);

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

			//3.重新向下调整堆顶
			adjustdown(0);

			return ret;
		}

2.7 top size empty

        这三个函数比较简单：

        T& top()
		{
			return _con[0];
		}

		void size()
		{
			return _con.size();
		}

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

2.7 代码与测试1 

        头文件 test.h

#pragma once
#include <vector>
#include <cassert>
using namespace std;

namespace YZC
{	
	//小于比较的仿函数
	template<class T>
	struct less
	{
		bool operator()(const T& a, const T&b)
		{
			return a < b;
		}
	};

	//大于比较的仿函数
	template<class T>
	struct greater
	{
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};

	//priority_queue容器适配器
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void push(const T& x)
		{
			//1.插入数据
			_con.push_back(x);
			//2.向上调整
			adjustup(static_cast<size_t>(_con.size() - 1));
		}

		T pop()
		{
			assert(_con.size() > 0);	//有数据才能删除
			T ret = _con[0];	//保存堆顶数据用于返回
			//1.交换堆顶堆尾的数据
			swap(_con[0], _con[_con.size() - 1]);

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

			//3.重新向下调整堆顶
			adjustdown(0);

			return ret;
		}

		T& top()
		{
			return _con[0];
		}

		void size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		void adjustdown(size_t root)
		{
			Compare cmp{};	//比较器，less是大根堆，greater是小根堆
			size_t parent = root;
			size_t child = root * 2 + 1;	//默认是其左孩子

			while (child < _con.size())
			{
				//child+1 < n 用于判断有无右孩子，使用com来获取比较的结果
				//由于默认是less的大根堆，我们要获取大的孩子,当
				if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1]))
				{
					child++;
				}
				//这样child默认是较大的孩子

				//此时如果父亲比孩子小，就需要交换
				if (cmp(_con[parent], _con[child]))
				{
					//交换父子节点
					swap(_con[parent], _con[child]);

					//重新更新父子节点
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					//说明这个结构是正确的不需要交换，直接跳出循环即可
					break;
				}

			}
		}

		void adjustup(size_t child)
		{
			Compare cmp{};
			//将最后一个节点的数据向上移动
			if (child == 0)	return;	//

			size_t parent = (child - 1) >> 1;
			
			while (child > 0)
			{
				//默认使用仿函数less，子节点比父节点大就要交换
				if (cmp(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);

					child = parent;
					parent = (child - 1) >> 1;
				}
				else
				{
					//说明整个结构是合法的
					break;
				}
			}
		}

		Container _con;	//适配的成员变量
	};

	void test1()
	{
		priority_queue<int> pq1{};
		for (int i = 0; i < 10; i++)
			pq1.push(rand() % 10000);

		while (!pq1.empty())
		{
			cout << pq1.top() << " ";
			pq1.pop();
		}
		cout << endl;
	}
}

源文件 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include "test.h"

int main()
{
	srand((unsigned int)time(0));
	YZC::test1();
	return 0;
}

测试结果如下：

f5683efc0c3448fdb4b1c2f5511cba5e.png

2.8 测试2 

        使用less来实现一个小根堆

	void test1()
	{
		priority_queue<int, vector<int>, greater<int>> pq1{};
		for (int i = 0; i < 10; i++)
			pq1.push(rand() % 10000);

		while (!pq1.empty())
		{
			cout << pq1.top() << " ";
			pq1.pop();
		}
		cout << endl;
	}

fc0d2569abb946a1b3ad3c7a75a2be69.png

        测试使用deque做适配，并且使用string测试类类型 

	void test1()
	{
		//测试string类，并且使用deque
		priority_queue<string, deque<string>, less<string>> pq1{};
		for (int i = 0; i < 10; i++)
		{
			string s;
			s += 'a' + rand() % 26;
			pq1.push(s);
		}

		while (!pq1.empty())
		{
			cout << pq1.top() << " ";
			pq1.pop();
		}
		cout << endl;
	}

测试结果如下

4b550db54e424c9997adf22633cb8ae2.png

三. 简单总结一下STL六大组件

容器：vector string list deque map set  

迭代器：iterator const_iterator reverse_iterator reverse_const_iterator

适配器：stack queue priority_queue

仿函数：less greater

算法：find sort reverse

空间配置器：无

四. 下篇内容： 模板的进阶使用

 

 

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

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

相关文章

十四、Pod的升级和回滚

十四、Pod的升级和回滚

当集群中的某个服务需要升级时，我们需要停止目前与该服务相关的所有Pod，然后下载新版本镜像并创建新的Pod。如果集群规模比较大，则这个工作变成了一个挑战，而且先全部停止然后逐步升级的方式会导致较长时间的服务不可用。Kubernetes提供了滚动升级功能来解决上述问题。 如…
阅读更多...
中间件--MongoDB部署及初始化js脚本（docker部署，docker-entrypoint-initdb.d，数据迁移，自动化部署）

中间件--MongoDB部署及初始化js脚本（docker部署，docker-entrypoint-initdb.d，数据迁移，自动化部署）

一、概述 MongoDB是一种常见的Nosql数据库&#xff08;非关系型数据库&#xff09;&#xff0c;以文档&#xff08;Document&#xff09;的形式存储数据。是非关系型数据库中最像关系型数据库的一种。本篇主要介绍下部署和数据迁移。 在 MongoDB 官方镜像部署介绍中&#xff…
阅读更多...
MES系统通过eDrawings Pro API开发图纸批量转换工具，实现3D在线查看

MES系统通过eDrawings Pro API开发图纸批量转换工具，实现3D在线查看

声明&#xff1a;部分代码来源于网络&#xff0c;如有疑问&#xff0c;请联系本人删除。 通过C#结合eDrawings API提供接口&#xff0c;实现图纸转换为换.jpg、.tif、.bmp、.stl、.exe、.html、.zip、.edrw、.eprt 和 .eas格式工具&#xff0c;尤其是.html格式&#xff0c;可以…
阅读更多...
Java阶段三06

Java阶段三06

第3章-第6节 一、知识点 理解MVC三层模型、理解什么是SpringMVC、理解SpringMVC的工作流程、了解springMVC和Struts2的区别、学会使用SpringMVC封装不同请求、接收参数 二、目标 理解MVC三层模型 理解什么是SpringMVC 理解SpringMVC的工作流程 学会使用SpringMVC封装请求…
阅读更多...
【计算机网络】期末速成(2)

【计算机网络】期末速成(2)

部分内容来源于网络&#xff0c;侵删~ 第五章 传输层 概述 传输层提供进程和进程之间的逻辑通信&#xff0c;靠**套接字Socket(主机IP地址&#xff0c;端口号)**找到应用进程。 传输层会对收到的报文进行差错检测。 比特流(物理层)-> 数据帧(数据链路层) -> 分组 / I…
阅读更多...
word poi-tl 表格功能增强，实现表格功能垂直合并

word poi-tl 表格功能增强，实现表格功能垂直合并

目录 问题解决问题poi-tl介绍 功能实现引入依赖模版代码效果图 附加&#xff08;插件实现&#xff09;MergeColumnData 对象MergeGroupData 类ServerMergeTableData 数据信息ServerMergeTablePolicy 合并插件 问题 由于在开发功能需求中&#xff0c;word文档需要垂直合并表格&…
阅读更多...
记一次：使用C#创建一个串口工具

记一次：使用C#创建一个串口工具

前言&#xff1a;公司的上位机打不开串口&#xff0c;发送的时候设备总是关机&#xff0c;因为和这个同事关系比较好&#xff0c;编写这款软件是用C#编写的&#xff0c;于是乎帮着解决了一下&#xff08;是真解决了&#xff09;&#xff0c;然后整理了一下自己的笔记 一、开发…
阅读更多...
LLama系列模型简要概述

LLama系列模型简要概述

LLama-1&#xff08;7B, 13B, 33B, 65B参数量&#xff1b;1.4T tokens训练数据量&#xff09; 要做真正Open的AI Efficient&#xff1a;同等预算下&#xff0c;增大训练数据&#xff0c;比增大模型参数量&#xff0c;效果要更好 训练数据&#xff1a; 书、Wiki这种量少、质量高…
阅读更多...
【OpenCV】模板匹配

【OpenCV】模板匹配

理论 模板匹配是一种在较大图像中搜索和查找模板图像位置的方法。为此&#xff0c;OpenCV 带有一个函数 cv.matchTemplate&#xff08;&#xff09; 。它只是在输入图像上滑动模板图像&#xff08;如在 2D 卷积中&#xff09;&#xff0c;并比较模板图像下的模板和输入图像的补…
阅读更多...
从 Zuul 迁移到 Spring Cloud Gateway：一步步实现服务网关的升级

从 Zuul 迁移到 Spring Cloud Gateway：一步步实现服务网关的升级

从 Zuul 迁移到 Spring Cloud Gateway&#xff1a;一步步实现服务网关的升级 迁移前的准备工作迁移步骤详解第一步&#xff1a;查看源码第二步&#xff1a;启动类迁移第三步&#xff1a;引入 Gateway 依赖第四步 编写bootstrap.yaml第五步&#xff1a;替换路由配置第六步&#…
阅读更多...
网站中的QQ在线客服接入

网站中的QQ在线客服接入

1. 开通QQ通讯组件 QQ通讯组件官网&#xff1a;https://shang.qq.com 默认未开通通讯组件&#xff0c;登陆上QQ之后会提示开通&#xff0c;点击开通即可 2. 唤起QQ临时会话&#xff08;对方不是自己的QQ好友也能唤起&#xff09; 复制链接地址 http://wpa.qq.com/msgrd?v3&…
阅读更多...
赋能加速AI应用交付，F5 BIG-IP Next for Kubernetes方案解读

赋能加速AI应用交付，F5 BIG-IP Next for Kubernetes方案解读

随着AI工作负载的爆炸式增长&#xff0c;服务提供商和企业需要加速计算&#xff0c;以安全高效地在大规模云上交付高性能的AI应用。前段时间&#xff0c;F5公司宣布推出一项全新的创新AI应用交付和应用安全解决方案&#xff0c;即BIG-IP Next for Kubernetes。那么该方案有何性…
阅读更多...
域内DNS信息收集

域内DNS信息收集

目录 一、查询域内DNS记录 1. 使用 PowerView.ps1 2. 使用 adidnsdump 二、添加域内DNS记录 1. 使用 Invoke-DNSUpdate.ps1 在默认情况下，域内所有用户 都有权限读取 Active Directory 数据库中的 DNS 信息，包括所有记录。这是因为： DNS 记录被视为公共信息，用于解析域…
阅读更多...
Odoo ：一款免费且开源的食品生鲜领域ERP管理系统

Odoo ：一款免费且开源的食品生鲜领域ERP管理系统

文 / 贝思纳斯 Odoo金牌合作伙伴 引言 提供业财人资税的精益化管理&#xff0c;实现研产供销的融通、食品安全的追踪与溯源&#xff0c;达成渠道的扁平化以及直面消费者的 D2C 等数字化解决方案&#xff0c;以此提升运营效率与核心竞争力&#xff0c;支撑高质量的变速扩张。…
阅读更多...
在星闪W63/W63E开发板上运行第一个OpenHarmony程序

在星闪W63/W63E开发板上运行第一个OpenHarmony程序

目录 引言 demolink示例 程序修改 修改任务堆栈的大小 修改示例程序的build.gn 修改App的build.gn 修改ohos.cmake 修改config.py 编译程序 烧写程序 程序运行 结语 引言 在前面的博文星闪WS63E开发板的OpenHarmony环境构建-CSDN博客中介绍了如何构建W63E开发板的…
阅读更多...
Spring——@Autowired和@Configuration注解区别

Spring——@Autowired和@Configuration注解区别

摘要 本文主要介绍了Spring框架中Autowired和Configuration注解的区别。Autowired用于自动注入依赖&#xff0c;支持属性、构造器和方法注入。Configuration则用于定义配置类&#xff0c;允许在类中使用Bean注解声明Bean。文章详细解释了这两个注解的作用、使用场景和核心特性…
阅读更多...
机器学习--张量

机器学习--张量

机器学习–张量 机器学习的数据结构–张量 张量是机器学习程序中的数字容器&#xff0c;本质上就是各种不同维度的数组&#xff0c;如下图所示。 张量的维度称为轴&#xff08;axis&#xff09;&#xff0c;轴的个数称为阶&#xff08;rank&#xff09; 标量–0D张量 impor…
阅读更多...
标记数据集生成模型助力无数据情况下的大模型指令微调

标记数据集生成模型助力无数据情况下的大模型指令微调

在构建大模型应用时&#xff0c;通常有两种方式来改进效果&#xff0c;一种是构建外部知识库&#xff0c;利用RAG来完成。但RAG并不是万能的&#xff0c;对于特定领域的LLM应用&#xff0c;以及无需示例&#xff0c;就能完成特定任务等场合就需要进行微调。然而&#xff0c;微调…
阅读更多...
nvm安装指定版本显示不存在及nvm ls-remote 列表只出现 iojs 而没有 node.js 解决办法

nvm安装指定版本显示不存在及nvm ls-remote 列表只出现 iojs 而没有 node.js 解决办法

在使用 nvm install 18.20.3 安装 node 时会发现一直显示不存在此版本 Version 18.20.3 not found - try nvm ls-remote to browse available versions.使用 nvm ls-remote 查看可安装列表时发现&#xff0c;列表中只有 iojs 解决方法&#xff1a; 可以使用以下命令查看可安装…
阅读更多...
5.ABAP结构体和内表

5.ABAP结构体和内表

总学习目录请点击下面连接 SAP ABAP开发从0到入职&#xff0c;冷冬备战-CSDN博客 目录 5.1.结构化数据对象 定义 如何引用结构化的数据对象 拷贝 实战练习 创建 拷贝 调试代码 5.2.内表 行类型 键 表种类 存取类型 表类型 如何在本地定义表类型 内表三种可能的…
阅读更多...
最新文章

Copyright @ 2022~2023