消息队列MQ

STL-优先队列(priority_queue)

本文主要是介绍STL-优先队列(priority_queue),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在刷Leetcode过程中,有道题的解法中使用了优先队列,使用的方式看不懂,遂记录学习优先队列的基础知识

  1. 定义

    优先队列不同于队列的先进先出,其中的遵循先进‘最值’出。入队,出队操作过程中的使用堆排序。总是保证最值在队列第一位。

    使用时 引入#include<queue>

    定义priority_queue< Type, Container, Functional>

    其中:

    1. Type为队列的元素数据类型
    2. Container 指定实现priority_queue的容器类型,priority_queue需要基于可以随机存取的容器实现(如vector,deque,list不可以)
    3. 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;
    }
    
    
  2. 基本使用

    其操作函数与队列相似

    q.push(1);//入队
    q.pop();//出队,符合条件的最值出队
    q.top();//返回队头元素,符合条件的最值
    q.empty();//是否为空
    q.size();//返回队列中元素个数
    
  3. 自定义比较函数

    在上面第1节的例子中,给出了两种自定义比较函数的方式,一个是使用函数对象,一个是使用匿名函数

    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;
          }
      }
      
    2. 匿名函数

      匿名函数是C++11中引入的,利用Lambda表达式,可以方便的定义和创建匿名函数,其表达式的声明为

      [capture list](param list) mutable exception->return type{fuction body}
      
      1. capture list 捕获的外部变量列表
      2. param list 形参列表
      3. mutable(指示符): 是否可以修改捕获的变量。默认情况下,Lambda函数总是一个const函数,mutable可以取消其常量性。在使用该修饰符时,参数列表不可省略(参数为空)
      4. exception: 异常设定
      5. return type: 返回类型,可以不需要声明返回值(连同→ \rightarrow→一起省略),此时返回类型相当于使用decltyp根据返回值推断得到。
      6. 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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!