C++STL之優先隊列

首先先講一下仿函數

仿函數

仿函數(functor)，就是使一個類的使用看上去像一個函數。其實作就是類中實作一個operator()，這個類就有了類似函數的行為，就是一個仿函數類了。仿函數的主要功能是為了搭配STL算法使用，單獨使用仿函數的情況比較少。 (感謝百度百科)

可能你看了以後也還是不太明白它到底是幹什麼的，怎麼作用的，那麼我就來簡單講一下

仿函數就是帶有一個或多個重載小括号的成員函數的一個結構體或類，又叫做仿函數類

仿函數類既可以當函數用，又可以當結構體用，好處是這樣就可以通過傳遞模闆類來給STL傳遞一個你寫的函數

如下

#include <bits/stdc++.h>
using namespace std;
struct disp{
	void operator()(int x){
		cout<<x<<endl;
	}
};
int main(){
	disp()(2);
	return 0;
}
           

實作了一個輸出 int x 的函數功能

對于傳遞模闆類就要說到今天的正題了--優先隊列--priority_queue

優先隊列，本質不是隊列，而是堆，且預設大根(頂)堆

聲明定義：priority_queue <T,Container,Compare>

T是資料類型

Container是underlying container，底層容器，用來作為優先隊列的内部實作

Compare是資料排列方式的比較，需要傳入仿函數類

需要注意的點有如下幾條：

①當T類型擁有小于号的比較功能時，Container和Compare可省略，預設為vector和less

②Container不是随意一個都可以，必須是有疊代器減法功能的容器才行

    （看了優先隊列内部代碼後，發現功能的實作過程中有疊代器減法）

    這類容器一般都是記憶體位址連續(疊代器連續)，一般可由下标通路

    部落客已知的有 deque，vector，array

    其中array記憶體大小需要設定，并非無限，是以不常用

    對于deque和vector用于priority_queue的差別

    部落客可以負責任的告訴你：沒有差別！priority_queue内部的實作不涉及二者差異的部分

    并且priority_queue帶給使用者的接口也很狹窄，不涉及deque和vector的功能

③T類型如果是你自定義的結構體或類，例如node

    那麼下面說的是必須的

    你要麼node裡重載小于号，要麼寫一個仿函數類

    less<node>這種東西可沒有

優先隊列的聲明與定義：

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
struct node{
	int x;
	bool operator<(node a)const{
		return x<a.x;
	}
};
struct node2{
	int x;
	friend bool operator<(node2 a,node2 b){
		return a.x<b.x;
	}
};
struct cmp{
	bool operator()(int a,int b){
		return a<b;
	}
};
int main(){
	priority_queue<int> q0;
	priority_queue<int,vector<int>,less<int>> q1;
	priority_queue<int,deque<int>,less<int>> q2;
	priority_queue<int,array<int,100>,less<int>> q3;
	priority_queue<int,vector<int>,cmp> q4;
	priority_queue<node> q5;
	priority_queue<node2> q6;
	return 0;
}
           

以上所有寫法全是大根堆(top大)，小根同理

然後注意！node裡那個成員函數必須寫const！！！

常成員函數與非常成員函數是不同的函數，内部實作用的是常成員函數！

友元函數的話就不需要擔心這個了，常還是非常隻有成員函數有

再就是 如果寫 const node &的話會快很多，遇到卡時間的題會很有效，但是寫或不寫都不會涉及編譯bug

常成員函數的那個const一定不能缺！不能缺！

然後總有人會問，為啥less大根，來看下less和greater的内部代碼

/// One of the @link comparison_functors comparison [email protected]
  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

/// One of the @link comparison_functors comparison [email protected]
  template<typename _Tp>
    struct greater : public binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
    };
           

怎麼說呢，舉個例子吧

比方說 a[5]={3,1,5,4,2};

sort(a,a+5,less<int>());

結果就是：1,2,3,4,5

對于隊列，queue也好，deque也好

下标小的是front(疊代器begin)，下标大的是back(疊代器end)

對于priority_queue，top不是front，而是back，是以這東西和隊列沒啥關系，鬼知道名字怎麼起的

類似于stack，是在後端操作的

priority_queue按less從小到大排的話，後端就是大的，于是就是大根堆

講了這麼多大家大概已經徹底了解這個這個priority_queue是啥，大概如何實作的吧

最後就該講最簡單的部分了

一些操作(成員函數)：

priority_queue<int> q;
q.push(x);//壓入堆頂
q.emplace(x);//壓入堆頂
q.empty();//是否空
q.size();//個數
q.swap(q2);//交換
q.top();//堆頂元素的引用
           

好，大概就這些，我覺得算是挺詳細的了，應該能對大家學習有很大幫助