【C++/STL】优先级队列的介绍与模拟实现仿函数

✨                                                       万物与我皆是自由诗       🌏 

📃个人主页:island1314

🔥个人专栏:C++学习

🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏  💞 💞 💞


目录

🚀前言

一、优先级队列

✨1、什么是优先级队列

✨2、优先级队列使用

二、仿函数

✨1,什么是仿函数 

✨2,仿函数的简单示例

三、优先级队列模拟实现


🚀前言

点击跳转到文章【C++/STL】stack/queue的使用及底层剖析&&双端队列&&容器适配器

前面我们已经学习了list容器的相关知识,本文主要介绍STL中另外两种重要的结构,stack和queue。但是在STL中这两者并没有划分在容器范围内,而是将其称为容器适配器。

注意:使用优先级队列要包含头文件 < queue >

一、优先级队列

✨1、什么是优先级队列

       优先级队列是一种特殊的队列,其中的元素都被赋予了优先级。元素的优先级决定了它们在队列中的顺序。在优先级队列中,元素按照优先级从高到低的顺序出队列。

优先级队列可以通过不同的数据结构来实现,常用的有二叉堆、二叉搜索树和斐波那契堆等。

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

✨2、优先级队列使用

函数声明接口说明
priority_queue()/priority_queue(first,last)构造一个优先级队列
empty( )检测优先级队列是否为空,是返回true,否则返回false
top( )返回优先级队列中最大(最小元素),即堆顶元素
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素,即堆顶元素

 测试代码如下:

这里的建堆一般有两种方式:
(1) 一种是一个一个push进vector容器再进行向上调整建堆
(2) 另一种是直接用迭代器区间构造直接建堆(推荐用这种)

#include<iostream>
using namespace std;
#include<vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
	// 默认情况下,创建的是大堆
	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1; 

	//使用范围for入队列
	for (auto e : v)q1.push(e);

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

	// 建小堆,将第三个模板参数换成greater比较方式
    //迭代器区间构造,直接建堆
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
}

注意:优先级队列默认的大堆,降序排列,如果要升序,就要换仿函数。下图中第三个模板参数就是传仿函数。

使用算法库里的 less 和 greater 算法,需要包含头文件< functional >

二、仿函数

✨1,什么是仿函数 

仿函数也叫函数对象,是一个重载了 运算符operator() 的类或结构体,可以使得类的对象像函数一样使用,通过重载函数调用运算符,仿函数可以实现自定义的操作行为。

✨2,仿函数的简单示例

operator()并没有参数的个数和返回值,所以使用是十分灵活的

💞样例1:

// 仿函数/函数对象:重载了oparator()的类,类的对象可以像函数一样使用
// operator()特点,参数个数和返回值根据需求确定,不固定,很多样化
class Func
{
public:
	//void operator()() //()函数调用参数列表括号运算
	//{
	//	cout << "Func调用" << endl;
	//}
	void operator()(int n = 1) //有参
	{
		while (n--)
		{
			cout << "Func调用" << endl;
		}
	}
};

int main()
{
	Func f1;
	f1();//使得对象像函数一样使用
	f1.operator()(); //显示调用

	cout << endl;

	Func f2;
	f2(3);
	return 0;
}

💞样例2:模拟实现求平方的功能

// 定义仿函数类
struct Square {
    int operator()(int a) const 
    {
        return a * a;
    }
};

int main()     
{
    Square square;  // 创建仿函数对象
    int result = square(5);  // 调用仿函数
    return 0;
}

通过仿函数,我们可以实现更灵活和自定义的操作行为,并且可以与STL算法等标准库函数配合使用,提高代码的可读性和可维护性。

三、优先级队列模拟实现

     优先级队列模拟实现和队列类似,所不同的是每次插入数据后都会使用算法将队列中的数据调整为一个堆,每次删除也是删除堆顶元素,然后将剩余的元素再次调整为一个堆,这样每次堆顶的元素就是所有数据中优先级最高的那一个了,

#pragma once
#include<vector>
#include<functional>

namespace qian
{
    template<class T>
    struct less
    {
        bool operator()(const T& left, const T& right)
        {
            return left < right;
        }
    };

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

    template <class T, class Container = std::vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        priority_queue() //= default;
            :c()
        {}

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            //:c(first,last) //和下面的一样,都是将数据输入c中
        {
            while (first != last)
            {
                c.push_back(*first);
                ++first;
            }

            for (int i = c.size() / 2 - 1; i >= 0; i--) {
                AdjustDown(i);
            }
        }

        bool empty() const
        {
            return c.empty();
        }

        size_t size() const
        {
            return c.size();
        }

        const T& top() const
        {
            return c[0]; //上下一样的
            //return c.front();
        }

        void AdjustUp(int child)
        {
            int parent = (child - 1) >> 1;
            while (child > 0)
            {
                if (comp(c[parent], c[child]))
                {
                    std::swap(c[parent], c[child]);
                    child = parent;
                    parent = (child - 1) >> 1;
                }
                else break;
            }
        }

        void AdjustDown(int parent)
        {
            int child = parent * 2 + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && comp(c[child], c[child + 1]))
                { 
                    ++child;
                }
                if (comp(c[parent], c[child]))
                {
                    std::swap(c[parent], c[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else break;
            }
        }


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

        void pop()
        {
            if (empty()) return;
            std::swap(c.front(), c.back());
            c.pop_back();
            AdjustDown(0);
        }

    private:
        Container c;
        Compare comp;
    };

};

测试代码如下:

void test_priority_queue()
{
	int a[] = { 2,1,7,6,0,4,3,9,8,5 };
	// 默认是大堆
	qian::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));
	// 小堆
	qian::priority_queue<int, vector<int>, qian::greater<int>> q2(a, a + sizeof(a) / sizeof(int));

	cout << "大堆:" << " ";
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;

	cout << "小堆:" << " ";
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
	cout << endl;

}

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

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

相关文章

深入理解TCP协议格式(WireShark分析)

传输控制协议&#xff08;TCP&#xff09;是互联网中最为关键的通信协议之一。了解TCP协议的细节不仅对于网络工程师至关重要&#xff0c;对于任何涉及网络通信的软件开发人员而言都是必备的知识。本文旨在深入探讨TCP协议&#xff0c;从协议的基本概述到其工作机制&#xff0c…

多维度多场景文档门户,鸿翼ECM文档云打造文档管理新范式

​在现代企业运营中&#xff0c;内容协作的效率直接影响到组织的整体表现和竞争力。传统的文档管理系统都是通过目录结构的方式进行文件管理&#xff0c;在实际业务中无法满足用户多视角、多维度、多场景的文档业务需求。因此&#xff0c;搭建结合文档体系的业务门户是许多企业…

AI绘画【光影模型】,穿越赛博迷雾,重塑光影艺术本真魅力

有时候是不是觉得单纯依靠大模型产生的图片作品光线方面平平无奇&#xff0c;依靠提示词&#xff0c;各种权重的调整费了九牛二虎之力才抽到一张感觉还算满意的作品。这个时候我们可以考虑结合相关Lora来进行。今天带来了一款光影氛围灯效果Lora——None-光染摄影&#xff0c;该…

进程的概念

一.进程和程序的理解 首先抛出结论&#xff1a;进程是动态的&#xff0c;暂时存在于内存中&#xff0c;进程是程序的一次执行&#xff0c;而进程总是对应至少一个特定的程序。 程序是静态的&#xff0c;永久的存在于磁盘中。 程序是什么呢&#xff1f;程序其实就是存放在我们…

Windows如何查看端口是否占用,并结束端口进程

需求与问题&#xff1a;前后端配置了跨域操作&#xff0c;但是仍然报错&#xff0c;可以考虑端口被两个程序占用&#xff0c;找不到正确端口或者后端接口书写是否规范&#xff0c;特别是利用Python Flask书写时要保证缩进是否正确&#xff01; Windows操作系统中&#xff0c;查…

Matlab中collectPlaneWave函数的应用

查看文档如下&#xff1a; 可以看出最多5个参数&#xff0c;分别是阵列对象&#xff0c;信号幅度&#xff0c;入射角度&#xff0c;信号频率&#xff0c;光速。 在下面的代码中&#xff0c;我们先创建一个3阵元的阵列&#xff0c;位置为&#xff1a;&#xff08;-1,0,0&#x…

代码随想录算法训练Day57|LeetCode200-岛屿数量、LeetCode695-岛屿的最大面积

岛屿数量 题目描述 力扣200-岛屿数量 给你一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 岛屿总是被水包围&#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此…

设计模式之单例模式(Java)

单例模式实现方式&#xff1a;懒汉式、饿汉式、双重检查、枚举、静态内部类&#xff1b; 懒汉式&#xff1a; /*** 懒汉式单例模式* author: 小手WA凉* create: 2024-07-06*/ public class LazySingleton implements Serializable {private static LazySingleton lazySinglet…

操作系统中的权限说明

什么是权限 权限在操作系统中是一个重要的功能&#xff0c;它允许你控制谁可以读取、写入或执行某个文件。不同的操作系统和文件系统可能有不同的权限模型&#xff0c;但在类Unix系统&#xff08;如Linux和macOS&#xff09;中&#xff0c;文件权限通常由三部分组成&#xff1a…

提升系统稳定性:熔断、降级和限流策略详解

文章目录 前言一、熔断&#xff08;Circuit Breaker&#xff09;二、降级&#xff08;Degradation&#xff09;三、限流&#xff08;Rate Limiting&#xff09;四、应用案例五、小结推荐阅读 前言 随着互联网业务的快速发展&#xff0c;系统稳定性和高可用性成为现代分布式系统…

Spring源码十三:非懒加载单例Bean

上一篇Spring源码十二&#xff1a;事件发布源码跟踪中&#xff0c;我们介绍了Spring中是如何使用观察者设计模式的思想来实现事件驱动开发的&#xff1a;实际上就是将所有监听器注册到广播器中&#xff0c;并通过监听该事件的监听器来处理时间的。结合前面十二篇文章我们将Spri…

电表读数检测数据集VOC+YOLO格式18156张12类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;18156 标注数量(xml文件个数)&#xff1a;18156 标注数量(txt文件个数)&#xff1a;18156 标…

cs224n作业4

NMT结构图&#xff1a;&#xff08;具体结构图&#xff09; LSTM基础知识 nmt_model.py&#xff1a; 参考文章&#xff1a;LSTM输出结构描述 #!/usr/bin/env python3 # -*- coding: utf-8 -*-""" CS224N 2020-21: Homework 4 nmt_model.py: NMT Model Penchen…

【0基础学爬虫】爬虫基础之scrapy的使用

【0基础学爬虫】爬虫基础之scrapy的使用 大数据时代&#xff0c;各行各业对数据采集的需求日益增多&#xff0c;网络爬虫的运用也更为广泛&#xff0c;越来越多的人开始学习网络爬虫这项技术&#xff0c;K哥爬虫此前已经推出不少爬虫进阶、逆向相关文章&#xff0c;为实现从易到…

九浅一深Jemalloc5.3.0 -- ④浅*配置

目前市面上有不少分析Jemalloc老版本的博文&#xff0c;但最新版本5.3.0却少之又少。而且5.3.0的架构与5之前的版本有较大不同&#xff0c;本着“与时俱进”、“由浅入深”的宗旨&#xff0c;我将逐步分析最新release版本Jemalloc5.3.0的实现。 另外&#xff0c;单讲实现代码是…

多功能工具网站

江下科技在线应用-免费PDF转换成Word-word转pdf-无需下载安装 (onlinedo.cn)https://www.onlinedo.cn/

荞面打造的甜蜜魔法:甜甜圈

食家巷荞面甜甜圈是一款具有特色的美食。它以荞面为主要原料&#xff0c;相较于普通面粉&#xff0c;荞面具有更高的营养价值&#xff0c;富含膳食纤维、维生素和矿物质。荞面甜甜圈的口感可能会更加扎实和有嚼劲&#xff0c;同时带着荞面特有的谷物香气。在制作过程中&#xf…

vue侦听器watch()

侦听器watch&#xff08;&#xff09; 侦听器侦听数据变化&#xff0c;我们可以使用watch 选项在每次响应式属性变化时触发一个函数。 <template><h3>侦听器watch</h3><hr> <p>{{nessage}}</p> <button click"exchage">…

缓存-缓存的使用与基本详解

1.缓存使用 为了系统性能的提升&#xff0c;我们一般都会将部分数据放入缓存中&#xff0c;加速访问。而db承担数据落盘工作。 哪些数据适合放入缓存&#xff1f; 即时性、数据一致性要求不高的访问量大且更新频率不高的数据&#xff08;读多&#xff0c;写少&#xff09; …

IDEA安装IDE Eval Reset插件,30天自动续期,无限激活

第一步&#xff1a; 下载idea 注意&#xff1a;版本要是2021.2.2以下 第二步&#xff1a;快捷键CtrlAlts打开设置 第三步&#xff1a;打开下图中蓝色按钮 第四步&#xff1a;点击弹窗的 “” &#xff0c;并输入 plugins.zhile.io 点击 “ok” 第五步&#xff1a;搜索IDE Ea…