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

個(gè)人主頁點(diǎn)擊直達(dá)：小白不是程序媛

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

代碼倉庫：Gitee

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

目錄

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

priority_queue的介紹

priority_queue的使用

大堆?

小堆

priority_queue的模擬實(shí)現(xiàn)

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

仿函數(shù)的介紹?

仿函數(shù)的使用

---

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

priority_queue的介紹

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

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

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

4. 底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過隨機(jī)訪問迭代器訪問，并支持以下操作：

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

5. 標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實(shí)例化指定容器類，則使用vector。

6. 需要支持隨機(jī)訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時(shí)自動(dòng)調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動(dòng)完成此操作?

priority_queue的使用

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

注意：

默認(rèn)情況下priority_queue是大堆。

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

大堆?

	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的模擬實(shí)現(xiàn)

通過對priority_queue的底層結(jié)構(gòu)就是堆，因此此處只需對對進(jìn)行通用的封裝即可。?

	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)，只能實(shí)現(xiàn)大堆/小堆的一種；實(shí)現(xiàn)另一種時(shí)候需要自己改變函數(shù)中的符號，比較麻煩；在C語言中我們會使用函數(shù)指針，回調(diào)函數(shù)解決此問題；但是函數(shù)指針比較難以理解和使用，C++就出現(xiàn)了仿函數(shù)。

---

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

仿函數(shù)的介紹?

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

有些時(shí)候，我們在寫代碼時(shí)會發(fā)現(xiàn)，某些功能實(shí)現(xiàn)的代碼會不斷的在不同的成員函數(shù)中用到，可又不好將這些代碼獨(dú)立出來成為類的一個(gè)成員函數(shù)，但又很想復(fù)用這些代碼。寫一個(gè)公共的函數(shù)是一個(gè)解決方法，不過函數(shù)用到的一些變量，就可能成為公共的全局變量。而且為了復(fù)用這么一片代碼，就要單立出一個(gè)函數(shù)，也不好維護(hù)，這時(shí)就可以用仿函數(shù)了。寫一個(gè)簡單類，除了那些維護(hù)一個(gè)類的函數(shù)成員外，就只是實(shí)現(xiàn)一個(gè)operator()，在類實(shí)例化時(shí)，就將要用的，非參數(shù)的元素傳入類中。這樣就免去了對一些公共變量全局化的維護(hù)。同時(shí)，又可以使那些代碼獨(dú)立出來，以便下次復(fù)用。而且，這些仿函數(shù)還可以用關(guān)聯(lián)、聚合、依賴的類之間的關(guān)系，與用到他們的類組合在一起，這樣有利于資源的管理（這點(diǎn)可能是它相對于函數(shù)最顯著的優(yōu)點(diǎn)了）。如果再配合上模板技術(shù)和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的模板，模擬實(shí)現(xiàn)和STL庫中的priority_queue。只需要在模板中加入一個(gè)比較器，默認(rèn)缺省為實(shí)現(xiàn)大堆，在實(shí)例化時(shí)候可以選擇大小堆這樣就可以不用直接修改符號了。

	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ù)的介紹、使用、模擬實(shí)現(xiàn)的分享到這就結(jié)束了，希望大家讀完后有很大的收獲，也可以在評論區(qū)點(diǎn)評文章中的內(nèi)容和分享自己的看法。您三連的支持就是我前進(jìn)的動(dòng)力，感謝大家的支持！！?!?