STL priority_queue自定義排序實現方法詳解

前面講解 priority_queue 容器介面卡時，還遺留一個問題，即當 <function> 標頭檔案提供的排序方式（std::less<T> 和 std::greater<T>）不再適用時，如何自定義一個滿足需求的排序規則。

首先，無論 priority_queue 中儲存的是基礎資料型別（int、double 等），還是 string 類物件或者自定義的類物件，都可以使用函數物件的方式自定義排序規則。例如：

#include<iostream>
#include<queue>
using namespace std;
//函數物件類
template <typename T>
class cmp
{
public:
    //過載 () 運算子
    bool operator()(T a, T b)
    {
        return a > b;
    }
};

int main()
{
    int a[] = { 4,2,3,5,6 };
    priority_queue<int,vector<int>,cmp<int> > pq(a,a+5);
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

執行結果為：

2 3 4 5 6

注意，C++ 中的 struct 和 class 非常類似，前者也可以包含成員變數和成員函數，因此上面程式中，函數物件類 cmp 也可以使用 struct 關鍵字建立：

struct cmp
{
    //過載 () 運算子
    bool operator()(T a, T b)
    {
        return a > b;
    }
};

可以看到，通過在 cmp 類（結構體）過載的 () 運算子中自定義排序規則，並將其範例化後作為 priority_queue 模板的第 3 個引數傳入，即可實現為 priority_queue 容器介面卡自定義比較函數。

除此之外，當 priority_queue 容器介面卡中儲存的資料型別為結構體或者類物件（包括 string 類物件）時，還可以通過過載其 > 或者 < 運算子，間接實現自定義排序規則的目的。

注意，此方式僅適用於 priority_queue 容器中儲存的為類物件或者結構體變數，也就是說，當儲存型別為類的指標物件或者結構體指標變數時，此方式將不再適用，而只能使用函數物件的方式。

要想徹底理解這種方式的實現原理，首先要搞清楚 std::less<T> 和 std::greater<T> 各自的底層實現。實際上，<function> 標頭檔案中的 std::less<T> 和 std::greater<T> ，各自底層實現採用的都是函數物件的方式。比如，std::less<T> 的底層實現程式碼為：

template <typename T>
struct less {
    //定義新的排序規則
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
};

std::greater<T> 的底層實現程式碼為：

template <typename T>
struct greater {
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs > _rhs;
    }
};

可以看到，std::less<T> 和 std::greater<T> 底層實現的唯一不同在於，前者使用 < 號實現從大到小排序，後者使用 > 號實現從小到大排序。

那麼，是否可以通過過載 < 或者 > 運算子修改 std::less<T> 和 std::greater<T> 的排序規則，從而間接實現自定義排序呢？答案是肯定的，舉個例子：

#include<queue>
#include<iostream>

using namespace std;

class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
};
//新的排序規則為：先按照 x 值排序，如果 x 相等，則按 y 的值排序
bool operator < (const node &a, const node &b) {
    if (a.x > b.x) return 1;
    else if (a.x == b.x)
        if (a.y >= b.y) return 1;
    return 0;
}

int main() {
    //建立一個 priority_queue 容器介面卡，其使用預設的 vector 基礎容器以及 less 排序規則。
    priority_queue<node> pq;
    pq.push(node(1, 2));
    pq.push(node(2, 2));
    pq.push(node(3, 4));
    pq.push(node(3, 3));
    pq.push(node(2, 3));
    cout << "x y" << endl;
    while (!pq.empty()) {
        cout << pq.top().x << " " << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

輸出結果為：

x y
1 2
2 2
2 3
3 3
3 4

可以看到，通過過載 < 運算子，使得 std::less<T> 變得適用了。

讀者還可以自行嘗試，通過過載 > 運算子，賦予 std::greater<T> 和之前不同的排序方式。

當然，也可以以友元函數或者成員函數的方式過載 > 或者 < 運算子。需要注意的是，以成員函數的方式過載 > 或者 < 運算子時，該成員函數必須宣告為 const 型別，且引數也必須為 const 型別，至於引數的傳值方式是採用按參照傳遞還是按值傳遞，都可以（建議採用按參照傳遞，效率更高）。

例如，將上面程式改為以成員函數的方式過載 < 運算子：

class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
    bool operator < (const node &b) const{
        if ((*this).x > b.x) return 1;
        else if ((*this).x == b.x)
            if ((*this).y >= b.y) return 1;
        return 0;
    }
};

同樣，在以友元函數的方式過載 < 或者 > 運算子時，要求引數必須使用 const 修飾。例如，將上面程式改為以友元函數的方式過載 < 運算子。例如：

class node {
public:
    node(int x = 0, int y = 0) :x(x), y(y) {}
    int x, y;
    friend bool operator < (const node &a, const node &b);
};
//新的排序規則為：先按照 x 值排序，如果 x 相等，則按 y 的值排序
bool operator < (const node &a, const node &b){
    if (a.x > b.x) return 1;
    else if (a.x == b.x)
        if (a.y >= b.y) return 1;
    return 0;
}

總的來說，以函數物件的方式自定義 priority_queue 的排序規則，適用於任何情況；而以過載 > 或者 < 運算子間接實現 priority_queue 自定義排序的方式，僅適用於 priority_queue 中儲存的是結構體變數或者類物件（包括 string 類物件）。