C++深入刨析優(yōu)先級隊列priority

第C++深入刨析優(yōu)先級隊列priority目錄一、priority_queue的介紹二、priority_queue的使用三、priority_queue的模擬實現(xiàn)四、容器適配器4.1、什么是適配器4.2、適配模式4.3、STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)

一、priority_queue的介紹

priority_queue官方文檔介紹

翻譯：

優(yōu)先隊列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個元素總是它所包含的元素中最大的。此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優(yōu)先隊列中位于頂部的元素)。優(yōu)先隊列被實現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為優(yōu)先級隊列的底層容器類，priority_queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的尾部彈出，其稱為優(yōu)先隊列的頂部。底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計的容器類。容器應(yīng)該可以通過隨機訪問迭代器訪問，并支持以下操作:

empty()：檢測容器是否為空。

size()：返回容器中有效元素個數(shù)。

front()：返回容器中第一個元素的引用。

push_back()：在容器尾部插入元素。

pop_back()：刪除容器尾部元素。

標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。需要支持隨機訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時自動調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。

二、priority_queue的使用

優(yōu)先級隊列默認(rèn)使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了堆算法（堆的創(chuàng)建與應(yīng)用）將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意:默認(rèn)情況下priority_queue是大堆。

??????：常用的函數(shù)接口

priority_queue()/priority_queue(first,last),構(gòu)造優(yōu)先級隊列。empty()，檢測優(yōu)先級隊列是否為空，若是返回True。top()，返回優(yōu)先級隊列中最大（最小）元素，即堆頂元素。push()，在優(yōu)先級隊列中插入元素。pop()，刪除優(yōu)先級隊列中最大（最小）元素，即堆頂元素。

下面我們就舉一個例子:

存放自定義類型，這樣更具代表性！

templateclassT

classgreater

public:

booloperator()(constTp1,constTp2)const

returnp1

structperson

person(stringname="",intage=-1)

:_name(name)

,_age(age)

booloperator(constpersonp)const

return_agep._age;

booloperator(constpersonp)const

return_agep._age;

string_name;

int_age;

ostreamoperator(ostreamout,constpersonp)

out"name:"p._name"""age:"p._ageendl;

returnout;

voidtest02()

personarr[]={{"pxl",23},

{"dyx",21},

{"wjz",24},

{"ztd",20}};

priority_queueperson,vectorperson,greaterpersonpq(arr,arr+sizeof(arr)/sizeof(arr[0]));//小堆

pq.push(person("yzc",22));

cout"堆頂元素是："pq.top()endl;

while(!pq.empty())

coutpq.top()endl;

pq.pop();

intmain()

test02();//自定義類型

system("pause");

return0;

}

??????注意點：

如果存放自定義類型，我們想要自定義類型像內(nèi)置類型一樣進行各種運算，那么就要在類中重載相應(yīng)的運算符。輸出自定義類型，需要重載流輸出。在priority_queue的第三個參數(shù)時，我們可以用庫中的greater函數(shù)（頭文件：functional），也可以我們自己寫一個仿函數(shù)（如上述代碼）。

三、priority_queue的模擬實現(xiàn)

templateclassT

structless

booloperator()(constTx,constTy)const

returnx

templateclassT

structgreater

booloperator()(constTx,constTy)const

returnx

//優(yōu)先級隊列--大堆小堆

templateclassT,classContainer=vectorT,classCompare=lessT

classpriority_queue

public:

voidAdjustUp(intchild)

ComparecomFunc;

intparent=(child-1)/2;

while(child0)

//if(_con[parent]_con[child])

if(comFunc(_con[parent],_con[child]))

swap(_con[parent],_con[child]);

child=parent;

parent=(child-1)/2;

else

break;

voidpush(constTx)

_con.push_back(x);

AdjustUp(_con.size()-1);

voidAdjustDown(intparent)

ComparecomFunc;

size_tchild=parent*2+1;

while(child_con.size())

//if(child+1_con.size()_con[child]_con[child+1])

if(child+1_con.size()comFunc(_con[child],_con[child+1]))

++child;

//if(_con[parent]_con[child])

if(comFunc(_con[parent],_con[child]))

swap(_con[parent],_con[child]);

parent=child;

child=parent*2+1;

else

break;

voidpop()

assert(!_con.empty());

swap(_con[0],_con[_con.size()-1]);

_con.pop_back();

AdjustDown(0);

constTtop()

return_con[0];

size_tsize()

return_con.size();

boolempty()

return_con.empty();

private:

Container_con;

};

代碼解釋：

這里模擬實現(xiàn)底層容器缺省參數(shù)使用vector，比較規(guī)則使用Less。這里的比較方式均是自己實現(xiàn)的仿函數(shù)。

四、容器適配器

4.1、什么是適配器

適配器是一種設(shè)計模式（設(shè)計模式是一套被反復(fù)使用的，多數(shù)人知曉的，經(jīng)過分類編目的，代碼設(shè)計經(jīng)驗的總結(jié)），該模式是講一個類的接口轉(zhuǎn)換成客戶希望的另一個接口。

4.2、適配模式

在計算機編程中，適配器模式（有時候也稱包裝樣式或者包裝）將一個類的接口適配成用戶所期待的。一個適配允許通常因為接口不兼容而不能在一起工作的類工作在一起，做法是將類自己的接口包裹在一個已存在的類中。適配器模式主要應(yīng)用于，當(dāng)接口里定義的方法無法滿足客戶的需求，或者說接口里定義的方法的名稱或者方法界面與客戶需求有沖突的情況。兩類模式：對象適配器模式-在這種適配器模式中，適配器容納一個它我包裹的類的實例。在這種情況下，適配器調(diào)用被包裹對象的物理實體。類適配器模式-這種適配器模式下，適配器繼承自已實現(xiàn)的類（一般多重繼承）。在計算機編程中，適配器包括：容器適配器、