程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> STL學習之priority_queue適配器

STL學習之priority_queue適配器

編輯：C++入門知識

priority_queue
優先隊列是容器適配器類型，根據某些嚴格的弱排序條件，專門設計了第一個元素總最大元素的容器。

很像堆，可以檢索最大的堆元素（在優先隊列中的最頂的元素）並且可以無限制的插入元素。

優先隊列作為容器適配器，用一個具體的容器類的封裝對象作為其底層容器，提供一個具體的訪問容器元素的成員函數集合。元素都是從具體的容器的“尾部”進行彈出（pop）操作，這個“尾部”就是所謂的優先隊列的頂。

底層容器可以是任何的標准容器類模板或者其他的具體的設計容器類。僅有的要求是需要支持下面的操作：

front()
push_back()
pop_back()
     因此可以使用vector,deque這樣標准容器類模板。默認的，如果對一個特殊的priority_queue類沒有指定容器類，使用vector標准類模板。
     為了時刻保持堆的內部結構，需要支持迭代器的隨機訪問。當適當的時候通過調用make_heap,push_heap和pop_heap算法由容器適配器自動執行。
     在c++標准的模板類的定義中，優先隊列是有三個模板參賽的模板：
[cpp]
template< class T. class Cotainer = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
參數：
T:元素類型。
Container:用於存儲和訪問元素的底層容器對象類型。
Compare:Comparison 類：com(a,b)類，comp是此類的對象並且a和b是容器的元素，如果a在b之前放入容器，返回true。這個可以是一個類執行函數調用操作或者指向函數的指針。默認為less<T>，less<T>的返回和小於（a<b）操作類似。priority_queue對象當元素插入或者刪除的時候使用此表達式去確保在優先隊列中彈出的元素始終是最大的元素。
priority_queue::priority_queue
[cpp] view plaincopy
explicit priority_queue( const Compare& x = Compare(), const Container& y = Container() );
template< class InputIterator>
priority_queue( InputIterator first, InputIterator last, const Compare& x = Compare(), const Container& y = Container() );
構造一個priority_queue容器適配器對象。
容器適配器把容器對象當作數據。如果有的話，容器對象是參數y的一個拷貝，否則是一個空的容器。
priority_queue滿足堆優先（彈出的元素總是容器中的最大的元素）操作，但是確切的序列准則可能會因合適的y參數被修改。
（Because priority_queues satisfy the heap property the element popped from it is always the highest in the container. But the exact ordering    criterium to determine this may be any that follow a strict weak ordering, which may be modified with an appropiatey parameter.
）。
參數
x
    被用於嚴格的若排序的Comparision 對象。
y
     容器對象。
     容器是第二個類模板參數（為priority_queue提供的底層容器類型）；默認情況下為vector<T>。
first,last
     在一個序列中的第一個和最後一個位置的輸入迭代器，采用[first,last)區間。
舉例：
[cpp]
#include <iostream>
#include <queue>

using namespace std;
class MyCmp
{
bool reverse;
public:
MyCmp(const bool& revParam=false)
{
     reverse = revParam;
}
bool operator() (const int& lhs, const int& rhs) const
{
    if (reverse) return (lhs < rhs);
    else return (lhs < rhs);
}
};

int main(void)
{
int myInts[] = {10,20,60,15};

priority_queue<int> first;
priority_queue<int> second(myInts, myInts+4);
priority_queue<int, vector<int>, greater<int> > third(myInts, myInts+4);

priority_queue<int, vector<int>, MyCmp> fourth;

typedef priority_queue<int, vector<int>, MyCmp> mypq_type;
mypq_type fifth(MyCmp());
mypq_type sixth(MyCmp(true));

return 0;
}
無執行結果。
priority_queue::top
[cpp] view plaincopy
const value_type& top() const;

返回priority_queue的最“頂”元素的一個常引用。這個最“頂”元素是priority_queue中比較高（compares higher），並且當調用priority_queue:pop調用時彈出的元素。
這個成員函數實際調用底部容器對象的fron成員函數。
舉例：
[cpp]
#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
   priority_queue<int> myqu;

   myqu.push(10);
   myqu.push(20);
   myqu.push(15);

     while(!myqu.empty())
     {
        cout << "myqu.top() is now "<< myqu.top() << endl;
        myqu.pop();
     }
   return 0;
}
執行結果：
[cpp]
www.2cto.com
myqu.top() is now 20
myqu.top() is now 15
myqu.top() is now 10
從程序中也可以看出，執行pop的時候，也是按照排序的順序彈出的。