首页 > 其他分享 >Cpp::STL—容器适配器priority_queue的讲解和模拟实现(17)

Cpp::STL—容器适配器priority_queue的讲解和模拟实现(17)

时间：2024-10-22 13:17:21浏览次数：3  
标签：容器 const 17 parent 适配器 queue child size con

文章目录

前言

  承接上一篇容器适配器的内容，本篇我们再来学一个优先级队列！
  学习它需要我们对之前的堆的内容有一个较为全面的掌握，如果你不是很有信心的话，我建议你回去看看
  正文开始！

一、优先级队列的使用

介绍

在这里插入图片描述
我们需要对其有一个这样的认识：

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

  • 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)

  • 优先级队列已经不能称为队列，不符合FIFO特性拉

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

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

  • empty():检测容器是否为空

  • size():返回容器中有效元素个数

  • front():返回容器中第一个元素的引用

  • push_back():在容器尾部插入元素

  • pop_back():删除容器尾部元素

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

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

我们来看看它的三个模板参数，第二个代表底层存储数据的容器，默认为vector，第三个就厉害了，这叫做仿函数（其实就是一个专门用作比较大小的类，我们后面会讲）

第二个容器必须支持随机访问迭代器（Random Access Iterator），以及 front()，push_back()，pop_back() 的操作

使用

  优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue

默认情况下，priority_queue用到的是大堆

#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
	//默认less 大堆
	//如果要改建立小堆也很简单，第三个参数设置为greater<int>
	priority_queue<int> pq;//实例化堆
	pq.push(1);//插入值
	pq.push(4);
	pq.push(2);
	pq.push(3);
 
	//堆不为空时打印堆顶元素，大堆打印出来为降序
	while (!pq.empty())
	{
		cout << pq.top() << " ";//打印堆顶元素
		pq.pop();//删除堆顶元素
	}
	cout << endl;
	
	return 0;
}

构造方式有两种，一种是直接构造一个空对象，另一种是通过迭代器区间去构造
在这里插入图片描述
在这里插入图片描述

一道题目

  我们之前就说过，堆这种数据结构很适合处理TopK问题，比如说现在给你一个数组 nums 和大小 k ，请帮我求出这个数组第k大的数，你有没有什么思路？

答案是首先先建立一个大小为k的小堆（注意是小堆！！），那么堆顶元素必定是这k个数最小的，现在再把数组剩下的元素走一遍，如果比堆顶元素大，就pop一下，push新数据，这样走完后，小堆里的k个数必定是这个数组里面最大的k个数，而堆顶又是这k个数中最小的那个，即第k大数

力扣215.数组中的第k个最大元素
去试试吧！~

二、仿函数的讲解

对内置类型

  仿函数是通过类中运算符重载()实现特定的功能，通过使用匿名对象使用，它的对象可以想函数一样去使用，使得很难区分是调用函数还是调用匿名对象

你可以顾名思义一下，仿函数就是用对象来模仿函数的一种方式，通过类来实现

// 定义一个仿函数模板类
template<class T>
struct Less
{
    // 重载函数调用操作符
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
 
int main()
{
	Less<int> lessfunc;//创建有名对象
	cout << lessfunc(1, 2) << endl;//有名对象调用类成员函数
	cout << lessfunc.operator()(1, 2) << endl;//显示调用
	cout << Less<int>()(1, 2) << endl;//匿名对象，前面一个括号构造对象，后面调用函数
	cout << Less<int>().operator()(1, 2) << endl;
	
	return 0;
}

我们定义了一个名为 Less 的仿函数类，它重载了 operator() 来实现前面一个数是否小于后面一个数的功能

  仿函数广泛用于C++标准库中，特别是在算法（std::sort）中作为比较函数或者操作函数，以及在容器（如 std::set 或者 std::map）中作为排序准则
在这里插入图片描述

仿函数的一个主要优点是它们可以保持状态，这意味着它们可以在多次调用之间保存和修改信息。这使得它们非常灵活和强大。此外，由于它们是类的实例，它们也可以拥有额外的方法和属性

对自定义类型

  假设现在有个日期类

class Date
{
public:
	Date(int year = 1970, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend std::ostream& operator<<(std::ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};

创建数据为 Date 的优先级队列（大堆），取堆顶元素（判断是否能对自定义类型进行正确调整）
在这里插入图片描述
我们发现这是没问题的，因为在实际比较时，调用的是 Date 自己的比较逻辑

但是问题是我们经常存放的不是自定义类型，而是自定义类型的指针，这时候还能正常比较吗
在这里插入图片描述
答案是不行的，因为此时调用的是指针的比较逻辑，而指针所存储的地址是比较随机的，这时候一共有两种方法，一种是我们下篇要学的模板特化，一种就是专门为Date*写一个仿函数

//小于
template<class T>
struct pDateLess
{
	bool operator()(const T& p1, const T& p2)
	{
		return (*p1) < (*p2);
	}
};

//大于
template<class T>
struct pDateGreater
{
	bool operator()(const T& p1, const T& p2)
	{
		return (*p1) > (*p2);
	}
};

在这里插入图片描述

成功解决，很神奇吧！

三、模拟实现priority_queue

  既然已经对优先级队列有了个大致的认识，不如我们再来好好实现一下它，对它有个更底层的认识！

  优先级队列 priority_queue 属于容器适配器的一种，像栈和队列一样，没有迭代器，同时也不需要实现自己的具体功能，调用底层容器的功能就行了，不过因为堆比较特殊，需要具备 向上调整 和 向下调整 的能力，确保符合堆的规则

向上调整 和 向下调整 都是实现的一个难点，且为了避免与库里面的优先级队列冲突，我们把它封装到自己的命名空间里面

两个仿函数

  明白了仿函数的概念和意义后，应该可以很自然的写出两种仿函数，并且我们要访问内部函数，干脆直接 struct 就行

	template<class T>
	struct Myless
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	struct Mygreater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

构造函数

  因为有两种，一种用迭代器，一种为空，迭代器会覆盖掉默认的构造参数，我们这里借助default来强制生成默认构造函数

	template<class T, class Container = vector<T>, class Compare = Myless<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			// 1.把数据全部存放到存储数据的容器中
			while (first != last) {
				_con.push_back(*first);
				++first;
			}
			// 2.向下调整建堆，默认为大堆
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}
	private:
		Container _con;
	};

向上调整和向下调整

  为了跟我们以前的堆的比较形成对比，我在每个使用仿函数的地方都给出了之前的语句

		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0) {
				//if (_con[parent] < _con[child]){
				//if (comfunc.operator()(_con[parent], _con[child])){
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare comfunc;
			int child = parent * 2 + 1;
			while (child < _con.size()) {
				// 1.先选出左右孩子节点中较大的那个
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
					child += 1;
				}
				// 2.将较大的那个节点跟父节点比较
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

插入数据和删除数据

  这也要考验你对堆的了解是否深入了！

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

其他常用接口

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

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

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

总概一览

namespace HQ
{
	template<class T>
	struct Myless
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	struct Mygreater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	template<class T, class Container = vector<T>, class Compare = Myless<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			// 1.把数据全部存放到存储数据的容器中
			while (first != last) {
				_con.push_back(*first);
				++first;
			}
			// 2.向下调整建堆，默认为大堆
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}

		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0) {
				//if (_con[parent] < _con[child]){
				//if (comfunc.operator()(_con[parent], _con[child])){
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare comfunc;
			int child = parent * 2 + 1;
			while (child < _con.size()) {
				// 1.先选出左右孩子节点中较大的那个
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
					child += 1;
				}
				// 2.将较大的那个节点跟父节点比较
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

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

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

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

}

使用效果如下：
在这里插入图片描述

总结

  我写完这篇后，自认为还是蛮有成就感的，你呢？

标签：容器,const,17,parent,适配器,queue,child,size,con
From： https://blog.csdn.net/2301_80392199/article/details/143141306

相关文章

  • 历年CSP-J初赛真题解析 | 2017年CSP-J初赛完善程序（27-36）
    学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。附上汇总贴：历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客（快速幂）请完善下面的程序，该程序使用分治法求x......
  • 物理学基础精解【117】
    文章目录微积分无穷级数无穷级数的定义无穷级数的原理无穷级数的性质无穷级数的数学公式无穷级数的计算无穷级数的例子无穷级数的例题柯西判敛法基本原理应用于数列应用于函数序列应用于无穷级数局限性重要性判断级数是否收敛无穷级数收敛与发散无穷级数收敛与发散的定......
  • ActiveMQ消息模式Queue和Topic机制讲解
    Docker安装ActiveMQ镜像以及通过Java生产消费activemq示例_dockeractivemq-CSDN博客背景周末由于服务器异常宕机，导致业务系统重启后出现ActiveMQ中的数据没有被正常消费，运维认为是消息积压，便联系博主排查。最终发现并不存在消息积压，是因为采用ActiveMQTopic模式生产消费......
  • Leetcode—175. 组合两个表【简单】
    2024每日刷题（192）Leetcode—175.组合两个表实现代码#WriteyourMySQLquerystatementbelowSELECTPerson.firstName,Person.lastName,Address.city,Address.stateFROMPersonLEFTJOINAddressUSING(personId);运行结果之......
  • P4170 [CQOI2007] 涂色 区间 dp
    P4170[CQOI2007]涂色区间dp模板题，不理解为什么是蓝。将现在考虑的区间\([l,r]\)分为\([l,k]\)和\([k+1,r]\)，如果\(s_l=s_r\)就可以一起涂，少涂一次。方程：\[dp_{l,r}=\min_{k=l}^{r-1}dp_{l,k}+dp_{k+1,r}-[s_l=s_r]\]代码：#include<bits/stdc++.h>usingnamespac......
  • 优先级队列（priority_queue）
     priority_queue简介   优先级队列的底层结构其实就是堆，就是我们在学习二叉树的时候学习的堆。它是一种逻辑结构，底层还是vector，我们把它想象成一个堆结构。    我们在学习堆的时候，知道了它的父亲和左右孩子的关系。它如果存在孩子，则一定存在这一种关系，leftchi......
  • 20240917【省选】模拟
    难说T1暴力可以写dp只要你学过线性基那么你就会想怎么用线性基做，显然是要套点数据结构维护的。你要知道两个线性基可以在\(O(\log^2n)\)的时间内合并，得到的线性基是原来两个的交。可以用线段树维护，复杂度\(O((n+q)\logn\log^2a)\)，难说能不能过。没有修改，所以考虑用常熟......
  • 17track物流查询平台 last-event-id 参数逆向分析
    声明本文章中所有内容仅供学习交流使用，不用于其他任何目的，不提供完整代码，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！本文章未经许可禁止转载，禁止任何修改后二次传播，擅自使用本文讲解的技术而导致的任何意外，作......
  • SP9685 ZTC - Zombie’s Treasure Chest 题解
    洛谷题目传送门双倍经验简单题。对于空间大小为\(s1\timess2\)时，显然最多可得到的价值为\(\max(s2\timesv1,s1\timesv2)\)，剩下小于\(s1\timess2\)的部分选一个占用空间大的枚举就好。时间复杂度：\(O(T\lfloor\frac{m}{\max(s1,s2)}\rfloor)\)，其中\(m=n\bmo......
  • Linux | CentOS7安装Java17的详细步骤
    步骤1:更新系统在安装Java之前，确保系统包是最新的。sudoyumupdate-y步骤2:下载Java17从Oracle官方网站或AdoptOpenJDK下载Java17。如果使用OracleJDK，可以到Oracle网站下载。如果使用AdoptOpenJDK，可以使用以下命令：wgethttps://github.com/adoptium/temurin17-bina......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99