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

Posted on by

前面講解 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 類對象）。

到此這篇關於C++ STL priority_queue自定義排序實現方法詳解的文章就介紹到這瞭,更多相關STL priority_queue自定義排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：