STL-优先队列(priority_queue)
2021/7/27 6:06:07
本文主要是介绍STL-优先队列(priority_queue),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
在刷Leetcode过程中,有道题的解法中使用了优先队列,使用的方式看不懂,遂记录学习优先队列的基础知识
-
定义
优先队列不同于队列的先进先出,其中的遵循先进‘最值’出。入队,出队操作过程中的使用堆排序。总是保证最值在队列第一位。
使用时 引入
#include<queue>
定义priority_queue< Type, Container, Functional>
其中:
- Type为队列的元素数据类型
- Container 指定实现priority_queue的容器类型,priority_queue需要基于可以随机存取的容器实现(如vector,deque,list不可以)
- Functional 时自定义比较,优先队列按照哪种规则进行排序。
如果使用默认按照数值大小排序大顶堆。Container, Functional可以省略。
完整示例:
#include<queue> using namespace std; int main(){ auto cmp=[](int a, int b){return a<b;}; priority_queue<int, vector<int>, decltype(cmp)>q(cmp); //该priority_queue基于容器vector创建, 数据类型为int; //使用decltype加lambda匿名函数自定义cmp函数 //又或者使用运算符重载 operator struct CmpOp{ bool operator()(int a, int b){//使用operator重载了()运算符,构建了函数对象 return a>b; } } priority_queue<int, vector<int>, CmpOp> q; }
-
基本使用
其操作函数与队列相似
q.push(1);//入队 q.pop();//出队,符合条件的最值出队 q.top();//返回队头元素,符合条件的最值 q.empty();//是否为空 q.size();//返回队列中元素个数
-
自定义比较函数
在上面第1节的例子中,给出了两种自定义比较函数的方式,一个是使用函数对象,一个是使用匿名函数
-
函数对象
当做函数使用的对象, 即一个重载了括号操作符
()
的类。当用该类的对象调用此操作符时,其表现形式如同普通函数调用一般,因此取名叫函数类,class FucPrint{ public: void operator()(){ cout<<"test FucPrint."<<endl; } }; FucPrint print_t; print_t(); //会打印一下信息. //test FucPrint.
主要在于函数对象有以下的优势:
- 函数对象可以有自己的状态。我们可以在类中定义状态变量,这样一个函数对象在多次的调用中可以共享这个状态。但是函数调用没这种优势,除非它使用全局变量来保存状态。
- 函数对象有自己特有的类型,而普通函数无类型可言。这种特性对于使用C++标准库来说是至关重要的。这样我们在使用STL中的函数时,可以传递相应的类型作为参数来实例化相应的模板,从而实现我们自己定义的规则。
STL中的priority_queue的比较函数使用就是函数对象,在上面例子中,使用的是结构体(c++中结构体可以视为一种对象,只不过他的成员都是公开的),改成类对象的形式为:
class CmpOp{ public: bool operator()(int a, int b){ return a>b; } }
-
匿名函数
匿名函数是C++11中引入的,利用Lambda表达式,可以方便的定义和创建匿名函数,其表达式的声明为
[capture list](param list) mutable exception->return type{fuction body}
- capture list 捕获的外部变量列表
- param list 形参列表
- mutable(指示符): 是否可以修改捕获的变量。默认情况下,Lambda函数总是一个const函数,mutable可以取消其常量性。在使用该修饰符时,参数列表不可省略(参数为空)
- exception: 异常设定
- return type: 返回类型,可以不需要声明返回值(连同→ \rightarrow→一起省略),此时返回类型相当于使用decltyp根据返回值推断得到。
- function body: 函数体
Lambda表达式通过在最前面的方括号[]来明确指明其内部可以访问的外部变量,这一过程也称过Lambda表达式“捕获”了外部变量。类似参数传递方式(值传递、引入传递、指针传递),在Lambda表达式中,外部变量的捕获方式也有值捕获、引用捕获、隐式捕获。
捕获外部变量形式
[] 不捕获任何外部变量 [变量名, ...] 以值的方式捕获指定外部变量 [this] 以值的形式捕获this指针 [=] 以值的方式捕获函数体中所有外部变量 [&] 以引用的方式捕获函数体中所有外部变量 [&, a] 以值的形式捕获外部变量a,以引用的形式捕获其他外部变量 [=, &a] 以引用的形式捕获外部变量a,以值的形式捕获其他外部变量 lambda表达式会自动转变成一个类——它每一个成员变量都对应着一个捕获的变量。这个类根据lambda表达式的参数列表重载了
operator()
如上面的这个
[](int a, int b){return a<b;} //编译器内部生成的类,类似 class someLambda{ public: bool operator()(int a, int b){ return a<b; } }
对于捕获外部变量的情况
[&](char a, char b){return character[a]<character[b];} // class someLambda{ someLambda(char* &character)_cha(character){} public: bool operator(){char a, char b}{ return _cha[a]<_cha[b]; } private: char *_cha; }
-
这篇关于STL-优先队列(priority_queue)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-27[开源] 一款轻量级的kafka可视化管理平台
- 2024-10-23Kafka消息丢失资料详解:初学者必看教程
- 2024-10-23Kafka资料新手入门指南
- 2024-10-23Kafka解耦入门:新手必读教程
- 2024-10-23Kafka入门:新手必读的简单教程
- 2024-10-23Kafka入门:新手必读的简单教程
- 2024-10-23Kafka消息丢失入门:新手必读指南
- 2024-10-23Kafka消息队列入门:新手必看的简单教程
- 2024-10-23Kafka消息队列入门与应用
- 2024-10-23Kafka重复消费入门:轻松掌握Kafka重复消息处理技巧