在刷Leetcode过程中,有道题的解法中使用了优先队列,使用的方式看不懂,遂记录学习优先队列的基础知识
优先队列不同于队列的先进先出,其中的遵循先进‘最值’出。入队,出队操作过程中的使用堆排序。总是保证最值在队列第一位。
使用时 引入#include<queue>
定义priority_queue< Type, Container, 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.
主要在于函数对象有以下的优势:
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}
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; }