STL —— priority_queue

std::priority_queue 是一个模板类，定义在 <queue> 头文件中，它基于堆（heap）数据结构来实现优先队列的功能。默认情况下，std::priority_queue 使用 std::vector 作为其底层容器，并且使用比较器（默认是 std::less）来决定元素的优先级顺序。

基本操作
入队操作： 使用 push() 成员函数将元素推入优先队列中。
std::priority_queue<int> myPriorityQueue;
myPriorityQueue.push(10);
出队操作： 使用 pop() 成员函数从优先队列中移除顶部（优先级最高）的元素。
myPriorityQueue.pop();
访问队列顶部元素： 使用 top() 成员函数获取优先队列顶部（优先级最高）的元素，但不会将其从队列中移除。
int topElement = myPriorityQueue.top();
判断优先队列是否为空： 使用 empty() 成员函数检查优先队列是否为空。
if (!myPriorityQueue.empty()) {
    // 优先队列不为空
}
获取优先队列的大小： 使用 size() 成员函数获取优先队列中元素的数量。
int queueSize = myPriorityQueue.size();

2. 模拟实现

其模拟实现的方式也是按照容器适配器的模式来完成的，刚才提到过其底层是堆的形式，那么只需要用vector来模拟实现即可

2.1 入队操作

void adjust_up()
{
int child = _con.size() - 1;
int parent = (child - 1) / 2;
while (child > 0)
{
if (_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);
adjust_up();
}

2.2 出队操作

void adjust_down()
{
int parent = 0;
int child = (parent * 2) + 1;
while (child < _con.size())
{
if (child + 1 < size() && (_con[child] < _con[child + 1]))
{
++child;
}
if (_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();
adjust_down();
}

2.3 访问队列顶部元素

T& top()
{
return _con.front();
}

2.4 判断优先队列是否为空

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

2.5 获取优先队列的大小

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

3. 仿函数

仿函数是C++中的一个概念，它实际上是一个类或结构体，但其行为类似于函数。仿函数可以像函数一样被调用，因此也被称为函数对象。

仿函数的特点

类似函数： 仿函数实际上是一个类对象，但其重载了函数调用运算符 operator()，使得它可以像函数一样被调用。

灵活性： 仿函数可以包含状态，因此可以捕获和存储额外的信息，而这在普通函数中可能很难实现。

可定制性： 仿函数可以根据需要进行定制，比如可以重载不同的函数调用运算符，或者添加额外的成员函数。

使用场景

作为函数对象传递： 仿函数可以作为参数传递给算法函数，这在STL中非常常见。比如，std::sort 函数可以接受一个仿函数来定义排序的顺序。

定制排序规则： 当需要对容器中的元素进行排序时，可以使用仿函数来定义排序规则，比如按照自定义的比较方式排序。

条件判断： 仿函数可以用于条件判断，例如在算法中过滤元素时。

示例代码

下面是一个简单的示例，演示了如何定义和使用一个简单的仿函数：
#include <iostream>

// 定义一个简单的仿函数
struct MyFunctor {
    void operator()(int x) const {
        std::cout << "Value: " << x << std::endl;
    }
};

int main() {
    MyFunctor myFunc;

    // 调用仿函数
    myFunc(10);

    return 0;
}

仿函数替代函数指针

在许多情况下，仿函数可以替代函数指针，并提供更多的灵活性和可扩展性。

我们知道在C语言中的qsort中，只需要给出两个元素的比较大小的方式，就可以传递函数指针来进行大小的排序，然而在C++中，我们可以传递仿函数，并调用算法库中的sort来进行排序，例如以下的代码：

#include <iostream>
#include <vector>
#include <algorithm>

// 定义一个比较器仿函数
struct MyComparator 
{
    bool operator()(int a, int b) const 
    {
        return a % 10 < b % 10; // 按照个位数进行排序
    }
};

int main() 
{
    std::vector<int> nums = {15, 30, 25, 12, 7};

    // 使用仿函数进行排序
    // 传匿名对象
    std::sort(nums.begin(), nums.end(), MyComparator());

    // 打印排序后的结果
    for (int num : nums) 
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

4.利用仿函数实现优先级队列

按照这样的逻辑，我们就可以用仿函数来实现优先级队列，

如果按照升序排序，建小堆，传greater比较方式；
如果按照降序排序，建大堆，传less比较方式。

template<class T>
class less
{
public:
bool operator()(const T& left, const T& right)
{
return left < right;
}
};

template<class T>
class greater
{
public:
bool operator()(const T& left, const T& right)
{
return left > right;
}
};

template<class T, class Container = vector<T>, class Compare = greater<T>>
class priority_queue
{
public:
void adjust_up()
{
Compare com;
int child = _con.size() - 1;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_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);
adjust_up();
}

void adjust_down()
{
Compare com;
int parent = 0;
int child = (parent * 2) + 1;
while (child < _con.size())
{
if (child + 1 < size() && com(_con[child], _con[child + 1]))
{
++child;
}
if (com(_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();
adjust_down();
}

T& top()
{
return _con.front();
}

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

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

private:
Container _con;
};

5. 有关自定义类型的排序

在很多情况下，我们需要对一个自定义类型按照某种形式进行排序，例如，对于一种商品，可能对他的评价、价格、销量等情况进行排序，这个时候我们就可以运用仿函数了。

struct Goods
{
string _name; // 名字
double _price; // 价格
int _evaluate; // 评价

Goods(const char* str, double price, int evaluate)
:_name(str)
, _price(price)
, _evaluate(evaluate)
{}
};

struct compare_price_less
{
bool operator()(const Goods& gdp1, const Goods& gdp2)
{
return gdp1._price < gdp2._price;
}
};

struct compare_evaluate_less
{
bool operator()(const Goods& gde1, const Goods& gde2)
{
return gde1._evaluate < gde2._evaluate;
}
};

struct compare_name_greater
{
bool operator()(const Goods& gdn1, const Goods& gdn2)
{
return gdn1._name > gdn2._name;
}
};

int main()
{
vector<Goods> v = { { "苹果", 2.1, 5 }, { "香蕉", 3, 4 }, { "橙子", 2.2,
3 }, { "菠萝", 1.5, 4 } };

sort(v.begin(), v.end(), compare_name_greater());

sort(v.begin(), v.end(), compare_evaluate_less());

sort(v.begin(), v.end(), compare_price_less());
return 0;
}

原文地址：https://blog.csdn.net/m0_68617301/article/details/137817227

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：关于小米消金-我以为的小米消金和实际的小米消金
下一篇：为什么公司在访问控制中转向人工智能

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

STL —— priority_queue

1. 优先级队列简介

基本操作