=========================================================================

個人主頁點擊直達：小白不是程序媛

C++系列專欄：C++干貨鋪

代碼倉庫：Gitee

=========================================================================?

目錄

優(yōu)先隊列（priority_queue?）的介紹和使用

priority_queue的介紹

priority_queue的使用

大堆?

小堆

priority_queue的模擬實現(xiàn)

仿函數(shù)的介紹和使用

仿函數(shù)的介紹?

仿函數(shù)的使用

---

優(yōu)先隊列（priority_queue?）的介紹和使用

priority_queue的介紹

1. 優(yōu)先隊列是一種容器適配器，根據(jù)嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。

2. 此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優(yōu)先隊列中位于頂部的元素)。

3. 優(yōu)先隊列被實現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先隊列的頂部。

4. 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：

• empty()：檢測容器是否為空
• size()：返回容器中有效元素個數(shù)
• front()：返回容器中第一個元素的引用
• push_back()：在容器尾部插入元素?
• pop_back()：刪除容器尾部元素

5. 標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。

6. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作?

priority_queue的使用

優(yōu)先級隊列默認使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了堆算法將vector中元素構造成堆的結構，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。

注意：

默認情況下priority_queue是大堆。

函數(shù)名稱	函數(shù)作用
priority_queue()	構造一個空的優(yōu)先級隊列
empty( )	檢測優(yōu)先級隊列是否為空，是返回true，否則返回 false
top( )?	返回優(yōu)先級隊列中最大(最小元素)，即堆頂元素
push(x)	在優(yōu)先級隊列中插入元素x
pop()	刪除優(yōu)先級隊列中最大(最小)元素，即堆頂元素

大堆?

	priority_queue<int,vector<int>> q1;q1.push(5);q1.push(23);q1.push(45);q1.push(7);q1.push(9);q1.push(2);q1.push(53);q1.push(34);cout << q1.size() << endl;while (!q1.empty()){cout << q1.top() << " ";q1.pop();}

小堆

	priority_queue<int,vector<int>,greater<int>> q1;q1.push(5);q1.push(23);q1.push(45);q1.push(7);q1.push(9);q1.push(2);q1.push(53);q1.push(34);cout << q1.size() << endl;while (!q1.empty()){cout << q1.top() << " ";q1.pop();}

?

---

priority_queue的模擬實現(xiàn)

通過對priority_queue的底層結構就是堆，因此此處只需對對進行通用的封裝即可。?

	template <class T, class Container=vector<T>>class priority_queue{public:void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent)//{size_t child = parent * 2 + 1;//while (child < _con.size()){if (child + 1 < _con.size() &&_con[child] < _con[child + 1]){++child;}if(_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 +1 ;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

但是我們編寫完成后發(fā)現(xiàn)，只能實現(xiàn)大堆/小堆的一種；實現(xiàn)另一種時候需要自己改變函數(shù)中的符號，比較麻煩；在C語言中我們會使用函數(shù)指針，回調函數(shù)解決此問題；但是函數(shù)指針比較難以理解和使用，C++就出現(xiàn)了仿函數(shù)。

---

仿函數(shù)的介紹和使用

仿函數(shù)的介紹?

仿函數(shù)(functor)，就是使一個類的使用看上去像一個函數(shù)。其實現(xiàn)就是類中實現(xiàn)一個operator(),這個類就有了類似函數(shù)的行為，就是一個仿函數(shù)類了。?

有些時候，我們在寫代碼時會發(fā)現(xiàn)，某些功能實現(xiàn)的代碼會不斷的在不同的成員函數(shù)中用到，可又不好將這些代碼獨立出來成為類的一個成員函數(shù)，但又很想復用這些代碼。寫一個公共的函數(shù)是一個解決方法，不過函數(shù)用到的一些變量，就可能成為公共的全局變量。而且為了復用這么一片代碼，就要單立出一個函數(shù)，也不好維護，這時就可以用仿函數(shù)了。寫一個簡單類，除了那些維護一個類的函數(shù)成員外，就只是實現(xiàn)一個operator()，在類實例化時，就將要用的，非參數(shù)的元素傳入類中。這樣就免去了對一些公共變量全局化的維護。同時，又可以使那些代碼獨立出來，以便下次復用。而且，這些仿函數(shù)還可以用關聯(lián)、聚合、依賴的類之間的關系，與用到他們的類組合在一起，這樣有利于資源的管理（這點可能是它相對于函數(shù)最顯著的優(yōu)點了）。如果再配合上模板技術和policy編程思想，就更是威力無窮了，大家可以慢慢的體會。

仿函數(shù)的使用

template <class T>
class functor
{
public :bool operator()(const T& x, const T& y){return x > y;}
};
int main()
{functor<int> com;cout << com(2,3)<< endl;cout << com.operator()(3, 2) << endl;return 0;
}

根據(jù)仿函數(shù)的功能和特性我們可以配合priority_queue的模板，模擬實現(xiàn)和STL庫中的priority_queue。只需要在模板中加入一個比較器，默認缺省為實現(xiàn)大堆，在實例化時候可以選擇大小堆這樣就可以不用直接修改符號了。

	template <class T, class Container=vector<T>,class Compare=Less<T>>class priority_queue{public:void adjust_up(int child)//{Compare com;int parent = (child - 1) / 2;//while (child > 0){if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent)//{Compare com;size_t child = parent * 2 + 1;//while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if(com (_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 +1 ;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

//大堆
template <class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
//小堆
template <class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

---

今天對C++中priority_queue和仿函數(shù)的介紹、使用、模擬實現(xiàn)的分享到這就結束了，希望大家讀完后有很大的收獲，也可以在評論區(qū)點評文章中的內容和分享自己的看法。您三連的支持就是我前進的動力，感謝大家的支持！！?!?