STL的priority_queue用法

priority_queue是個STL容器，會按照自己所指定的排序方法存在此容器中，它的樣板聲明帶有三個參數

priority_queue<Type, Container, Functional>

Type為類別型態，Container為儲存容器的型態，Functional為元素比較的方式。Container必須為vector或是deque，預設為vector，例如：

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> p;
    int numbers[10] = { 3, 6, 5, 555, 211, 321, 48, 99, 6773, 4};

    for (int i = 0; i < 10; ++i)
    {
        p.push(numbers[i]);
    }

    while (!p.empty())
    {
        cout << p.top() << " ";
        p.pop();
    }
    return 0;
}

輸出：

6773 555 321 211 99 48 6 5 4 3

Functional的型式，STL有做了兩個仿函數，less為由大排到小，greater為由小排到大，若是為自定義的類別，那麼就要重載＞或＜，也可以自己寫個仿函數進去，例如：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class CTest
{
public:
    CTest() {}
    ~CTest() {}
    CTest(const CTest& rhs) { m_test = rhs.GetTest(); }
    CTest& operator= (const CTest& rhs) { m_test = rhs.GetTest(); return *this; }

    void SetTest(const int input) { m_test = input; }
    int GetTest() const { return m_test; }
    // 重載＞
    friend bool operator> (const CTest& lhs, const CTest& rhs) { return lhs.GetTest() > rhs.GetTest(); }

private:
    int m_test;
};

// 自己寫仿函數
struct cmp
{
    bool operator() (const CTest& lhs, const CTest& rhs) { return lhs.GetTest() < rhs.GetTest(); }
};

int main()
{
    CTest XD[10];
    // p_greater使用自定義的類別，採用greater<T>
    priority_queue< CTest, vector<CTest>, greater<CTest> > p_greater;
    // p_functors使用自定義的類別，採用仿函數
    priority_queue< CTest, vector<CTest>, cmp > p_functors;
    int numbers[10] = { 3, 6, 5, 555, 211, 321, 48, 99, 6773, 4};

    for (int i = 0; i < 10; ++i)
    {
        XD[i].SetTest(numbers[i]);
        p_greater.push(XD[i]);
        p_functors.push(XD[i]);
    }
    cout << "Greater：\n";
    while (!p_greater.empty())
    {
        cout << p_greater.top().GetTest() << " ";
        p_greater.pop();
    }

    cout << endl << "Functors：\n";

    while (!p_functors.empty())
    {
        cout << p_functors.top().GetTest() << " ";
        p_functors.pop();
    }
    return 0;
}

輸出：

Greater：
3 4 5 6 48 99 211 321 555 6773
Functors：
6773 555 321 211 99 48 6 5 4 3

挺有趣的一個容器！要記起來。