【C++】优先级队列以及仿函数

server/2024/12/30 1:07:30/

本篇我们来介绍一下优先级队列 priority_queue 。优先级队列的底层是数据结构中的,在C++中它是一个容器适配器,这个容器适配器比之前的栈和队列更复杂。

1.priority_queue的介绍

1.1 优先级队列的底层

因为优先级队列就是堆,堆的底层是数组,所以优先级队列的默认适配器也是数组

 需要用到访问下标的,数组一定是最好的选择。不了解堆的,建议先看下面这篇博客。

 数据结构中的堆:【数据结构】堆的概念、结构、模拟实现以及应用

1.2 文档介绍

文档介绍:priority_queue - C++ Reference

在C++中优先级队列的相关接口就是如上这些。这里的top,如果大的值优先级高,也就是大堆,top返回的就是堆里面的最大值,如果是小的数优先级高,也就是小堆,返回的就是最小值。

2.priority_queue的使用

使用优先级队列的时候需要包含头文件 #include <queue>

	priority_queue<int> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(10);pq.push(8);pq.push(4);

数据结构中的实现逻辑如下。 用到的是向上调整算法。

 再通过top和pop的配合,把这些数打印出来。

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

 优先级队列默认大的值优先级高,在数据结构中的意思就是,默认为大堆。

如果想换成小的优先级高,就是小堆,我们就要传greeter

priority_queue<int, vector<int>, greater<int>> pq;

改成greater,用同样的用例试试。

结果就是升序排列。 

 在数据结构中小堆就是要用到向下移调整,这里就不具体演示了,详情请看数据结构那篇博客。

3.priority_queue的模拟实现 

3.1 做准备工作

建立一个头文件priority_queue.h,一个源文件test.cpp,存放内容如下。

在 priority_queue.h 包含需要的头文件,所有实现用命名空间隔开。

#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace lyj
{template<class T, class Container = vector<T>>class priority_queue{public:private:Container _con;};
}

3.2 父节点和子节点的对应关系

假设父节点在数组的下标为i:

左孩子在数组的下标:2*i + 1;右孩子在数组的下标:2*i + 2;

假设子节点在数组中的下标为j:

父节点在数组中的下标:(j - 1) / 2;

3.2 插入数据

以大的数优先级高为例,在插入数据之前,这个堆一定已经是一个大堆了。这里的实现逻辑与数据结构中介绍的逻辑一样。

在 priority_queue.h 中实现。

3.2.1 Swap交换

因为需要交换数据,所以我们写一个交换函数。

void Swap(T& x1, T& x2)
{T tmp = x1;x1 = x2;x2 = tmp;
}

3.2.2 AdjustUp向上调整

把向上调整的代码也重新封装。

void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0 && _con[child] > _con[parent]){Swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}
}

因为有默认的this指针,所以对比数据结构中C语言实现的堆的向上调整,现在我们只要传一个参数过去。

3.3.3 push插入

插入数据直接用_con的插入,插入完之后,要进行调整,保证这始终是个堆。

void push(const T& x)
{_con.push_back(x); //插入数据AdjustUp(_con.size() - 1);//向上调整
}

test.cpp中测试一下。

void test1()
{lyj::priority_queue<int> pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);pq.push(5);
}int main()
{test1();return 0;
}

3.2 删除数据

在数据结构中介绍过,删除数据是删除堆顶数据。删除数据的逻辑是将收尾数据交换,交换后要删的数据在最后,然后再尾删,后用向下调整算法,将堆恢复。

在 priority_queue.h 中实现。

3.2.1 向下调整

 向下调整的逻辑和数据结构中一致。

void AdjustDown(size_t parent)
{size_t child = parent * 2 + 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 = parent * 2 + 1;}else{break;}}
}

参数我们只需要传一个parent就可以了。

3.2.2 pop删除

void pop()
{Swap(_con[0], _con[_con.size() - 1]);//首尾交换_con.pop_back();//删除AdjustDown(0); //向下调整
}

test.cpp中测试一下。

void test1()
{lyj::priority_queue<int> pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);pq.push(5);pq.pop();pq.pop();
}

3.2.3 top、empty和size

在 priority_queue.h 中实现。

const T& top() 
{return _con[0];
}
bool empty() const
{return _con.empty();
}
size_t size() const
{return _con.size();
}

test.cpp中测试一下。

void test2()
{lyj::priority_queue<int> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(10);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

 

4.仿函数

我们前面说过,优先级队列默认为大堆,但是给第三个参数传greater过去,就可以改成小堆,这里说的less和greater就是仿函数。

目前我们只实现了一个大堆,要实现小堆就要把对比的逻辑全部改掉,但是库里面只需要传参数就可以了,如果我们想模拟实现的更接近库里面的优先级队列,就要先说说这个仿函数。

4.1 仿函数的介绍

仿函数本质是一个类,这个类重载了operator(),这个括号重载的是函数调用时参数列表的括号,它的对象可以像函数一样使用。

比如说我们现在要重载operator()实现两个数的比较

class Less
{
public:bool operator()(int x, int y){return x < y;}
};

我们还可以改造一下,用类模板。

template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};

这个仿函数的类没有成员变量,所以大小是1字节。

我们来使用一下。

Less<int> lessF; //实例化出对象
cout << lessF(3, 2) << endl; //对象的使用

我们只看 cout << lessF(3, 2) << endl; 这句代码,会觉得我们是在使用一个函数,其实不是,这是一个类的对象,这个类的对象可以像函数一样使用。所以我们也把这个对象叫做函数对象

完整的写法是下面这样的。运算符重载。

cout << lessF.operator()(1, 2) << endl;

我们还可以写一个Greater类,里面的operator()也是实现两个数的比较,比较逻辑和Less相反。

template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

4.2 仿函数的简单应用

有哪些使用场景呢?比如说我们这里有个冒泡排序,现在默认排升序

void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){int flag = 0;for (int j = 0; j < n - 1 - i; j++){if (a[j + 1] < a[j]){int tmp = a[j + 1];a[j + 1] = a[j];a[j] = tmp;flag = 1;}}if (flag == 0){return;}}
}

我们想变成排降序,就要将代码 if (a[j + 1] < a[j]) 改成 if (a[j + 1] > a[j]) 

现在我们添加一个模板参数Compare cmp。

template<class Compare>
void BubbleSort(int* a, int n, Compare cmp)
{//...
}

 用cmp来控制比较大小的逻辑。

for (int j = 0; j < n - 1 - i; j++)
{
//	if (a[j] < a[j + 1]) 小于,排降序if (cmp(a[j], a[j + 1])){int tmp = a[j + 1];a[j + 1] = a[j];a[j] = tmp;flag = 1;}
}

我们在调用这个BubbleSort的时候,通过传的第三个参数,就是我们的仿函数,来控制比较逻辑

int main()
{Less<int> lessF; //实例化Greater<int> greaterF;int a[] = { 3, 6, 2, 7, 8, 1, 9, 4 };BubbleSort(a, 8, lessF); //降序BubbleSort(a, 8, greaterF); //升序return 0;
}

这里其实是走了一个回调的过程。

在传参数的时候还可以用匿名对象。

int a[] = { 3, 6, 2, 7, 8, 1, 9, 4 };
BubbleSort(a, 8, Less<int>()); //传匿名对象
BubbleSort(a, 8, Greater<int>()); //传匿名对象

 这个用在优先级队列里是怎样的呢?

4.3 priority_queue用仿函数实现

首先我们把自己实现的两个仿函数Greater和Less放到priority_queue.h里。可以选择放在namespace里面也可以不放。

然后我们也要在priority_queue类模板多加一个模板参数Compare,并且给缺省值,默认大的数优先级高,就是大堆。

template<class T, class Container = vector<T>, class Compare = Less<T>>

传参数的时候注意一下函数传参和类模板传参不一样。 

函数参数要传匿名对象,类模板的参数要传类型

因为我们传过来的是一个类型,所以要自己再定义一个对象。先改向上调整的代码。

void AdjustUp(int child)
{Compare cmp; //定义对象int parent = (child - 1) / 2;
//	while (child > 0 && _con[parent] < _con[child])while (child > 0 && cmp(_con[parent], _con[child])){Swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}
}

再用同样的逻辑改一下向下调整。

void AdjustDown(size_t parent)
{Compare cmp; //定义对象size_t child = parent * 2 + 1;while (child < _con.size()){//	if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1])){child++;}//	if (_con[parent] < _con[child])if (cmp(_con[parent], _con[child])){Swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

只需要改动这两个函数,其余不变

有了仿函数,我们就不用写两个类一个大堆一个小堆了。

test.cpp中测试一下。

void test2()
{lyj::priority_queue<int> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(10);pq.push(6);pq.push(3);pq.push(8);cout << pq.size() << endl;while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

 

默认是大堆,然后结合top和pop按降序把数据打印出来。

再测试一下小堆,参数列表改一下就行。

 现在就是小堆,然后结合top和pop按升序把数据打印出来。

现在我们优先级队列的模拟实现就算完成了,我们下篇再见~ 


http://www.ppmy.cn/server/152954.html

相关文章

Transmission Web Control 下载及安装教程

Transmission Web Control 下载及安装教程 transmission-web-control maintained fork of ronggang/transmission-web-control [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/tra/transmission-web-control 1、项目介绍 Transmission Web Control 是一个自定义…

P8795 [蓝桥杯 2022 国 A] 选素数

题目描述&#xff1a; 小蓝有一个数 x&#xff0c;每次操作小蓝会选择一个小于 x 的素数 p&#xff0c;然后在 x 成为 p 的倍数前不断将 x 加 1&#xff0c;&#xff08;如果 x 一开始就是 p 的倍数则 x 不变&#xff09;。 小乔看到了小蓝进行了 2 次上述操作后得到的结果 n…

公交车信息管理系统:实现交通数据的智能化处理

概述 在对系统进行设计之前&#xff0c;需要对选题进行需求分析、可行性分析、流程分析、数据字典等内容。根据需求分析阶段&#xff0c;大致确定用户使用系统所需要具有的功能模块需求&#xff0c;由此规划出系统需要设计的相关功能模块。根据可行性分析阶段&#xff0c;确定系…

计算机网络•自顶向下方法:计算机网络和因特网

因特网的具体构成 终端&#xff08;host&#xff09;也称端系统&#xff08;end system&#xff09;&#xff1a;运行应用程序 通信链路&#xff1a;光纤&#xff0c;铜线&#xff0c;电磁波&#xff0c; 主要指标为传输速率&#xff0c;也称带宽(bandwidth) 交换设备&#x…

前端开发 之 12个鼠标交互特效上【附完整源码】

前端开发 之 12个鼠标交互特效上【附完整源码】 文章目录 前端开发 之 12个鼠标交互特效上【附完整源码】一&#xff1a;彩色空心爱心滑动特效1.效果展示2.HTML完整代码 二&#xff1a;彩色实心爱心滑动特效1.效果展示2.HTML完整代码 三&#xff1a;粒子连结特效1.效果展示2.HT…

精准提升:从94.5%到99.4%——目标检测调优全纪录

&#x1f680; 目标检测模型调优过程记录 在进行目标检测模型的训练过程中&#xff0c;我们面对了许多挑战与迭代。从初始模型的训练结果到最终的调优优化&#xff0c;每一步的实验和调整都有其独特的思路和收获。本文记录了我在优化目标检测模型的过程中进行的几次尝试&#…

如何在Windows系统上安装和配置Node.js及Node版本管理器(nvm)

Node.js是一个基于Chrome V8引擎的JavaScript运行时环境&#xff0c;广泛用于开发高性能的网络应用。它使得JavaScript不仅能在浏览器端运行&#xff0c;还能在服务器端执行。对于开发者来说&#xff0c;Node.js是现代Web应用的核心之一。安装和配置Node.js后&#xff0c;很多开…

Blazor 直接读取并显示HTML 文件内容

如果你想在 Blazor 中直接读取 并显示HTML 文件&#xff0c;可以使用 .NET 的文件读取方法&#xff0c;比如 File.ReadAllText。Blazor Server&#xff08;服务端&#xff09;可以通过服务器的文件系统访问文件。 以下是针对 Blazor Server 的解决方案&#xff1a; 1. 使用 Fi…