C++ priority_queue

一、概述

priority_queue，首先它是一個queue，即只允許在低端加入元素，並從頂端取出元素，除此之外別無其他存取元素的途徑（故priority_queue不提供遍歷功能，也不提供迭代器）；再次它具有priority，即queue中的元素具有一定的priority：其內的元素自動依照元素的權值排列，權值最高者，排在最前面。

注：在queue並非是依照嚴格的權值遞減的順序排列，而是每次保持頂端（對頭）元素為queue中權值最高的元素（其內部采用heap來實現）。

二、實現

由於priority_queue完全以底部容器為根據，在加上heap處理規則，所以其實現較簡單，且缺省情況下以vector為底部容器。

聯系適配器（adapter）的定義：具有這種【修改某物接口，形成另一種風貌】之性質者，稱為adapter。因為，STL priority_queue被歸類為：container adapter 。

其SGI（Silicon Graphics Computer Systems, Inc.） STL中的priority_queue的源碼如下：

template<class T, class Sequeue = vector<T>, class Compare = less<typename Sequeue::value_type> >  
class priority_queue  
{  
public:  
    typedef typename Sequeue::value_type value_type;  
    typedef typename Sequeue::size_type size_type;  
    typedef typename Sequeue::reference reference;  
    typedef typename Sequeue::const_reference const_reference;  
protected:  
    Sequeue c; //底層容器   
    Compare comp; //元素大小比較標准   
public:  
    priority_queue(): c() { }  
    explicit priority_queue(const Compare& x) : c(), comp(x) {}  
  
    template<class InputIterator>  
    priority_queue(InputIterator first, InputIterator last, const Compare& x)  
        :c(first, last), comp(x){make_heap(c.begin(), c.end(), comp); }  
    priority_queue(InputIterator first, InputIterator last) //使用默認的comp比較標准   
        :c(first, last){make_heap(c.begin(), c.end(), comp); }  
  
    bool empty() const {return c.empty(); }  
    size_type size() const {return c.size(); }  
    const_reference top() const {return c.front(); }  
    void push(const value_type& x)  
    {  
        __STL_TRY  
        {  
            c.push_back(x); //先加入容器（vector）   
            push_heap(c.begin(), c.end(), comp); //再利用heap對容器排序   
        }  
        __STL_UNWIND(c.clear());  
    }  
    void pop()  
    {  
        ———STL_TRY  
        {  
            pop_heap(c.begin(), c.end(), comp); //先退出heap（排序）   
            c.pop_back(); //再從容器中刪除   
        }  
        __STL_UNWIND(c.clear());  
    }  
};  

三、測試實例

#include <iostream>   
#include <queue>   
using namespace std;  
  
class myComparison  
{  
    bool reverse;  
public:  
    myComparison(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()  
{  
    int myInts[] = {10, 60, 50 ,20};  
  
    priority_queue<int> first;  
  
    priority_queue<int> second(myInts, myInts+4);  
    cout << "second size: " << second.size() << endl;  
    cout << "second top: " << second.top() << endl;  
    second.push(100);  
    cout << "second top: " << second.top() << endl;  
  
    priority_queue<int, vector<int>, greater<int> > third(myInts, myInts+4);  
    cout << "third size: " << third.size() << endl;  
    cout << "third top: " << third.top() << endl;  
    third.push(100);  
    cout << "third top: " << third.top() << endl;  
  
    //using myComparison   
    priority_queue<int, vector<int>, myComparison > fourth;  
  
    typedef priority_queue<int, vector<int>, myComparison> myPq_type;  
    myPq_type fifth(myComparison() );  
  
    myPq_type sixth(myInts, myInts+4, myComparison(true) );  
    cout << "sixth top: " << sixth.top() << endl;  
    sixth.pop();  
    cout << "sixth top: " << sixth.top() << endl;  
  
    return 0;  
}  

輸出結果：