怎么在C++項(xiàng)目中利用priority_queue自定義排序

這篇文章給大家介紹怎么在C++項(xiàng)目中利用priority_queue自定義排序，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

首先，無論 priority_queue 中存儲(chǔ)的是基礎(chǔ)數(shù)據(jù)類型（int、double 等），還是 string 類對(duì)象或者自定義的類對(duì)象，都可以使用函數(shù)對(duì)象的方式自定義排序規(guī)則。例如：

#include<iostream>
#include<queue>
using namespace std;
//函數(shù)對(duì)象類
template <typename T>
class cmp
{
public:
  //重載 () 運(yùn)算符
  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;
}

運(yùn)行結(jié)果為：
2 3 4 5 6

注意，C++ 中的 struct 和 class 非常類似，前者也可以包含成員變量和成員函數(shù)，因此上面程序中，函數(shù)對(duì)象類 cmp 也可以使用 struct 關(guān)鍵字創(chuàng)建：

struct cmp
{
  //重載 () 運(yùn)算符
  bool operator()(T a, T b)
  {
    return a > b;
  }
};

可以看到，通過在 cmp 類（結(jié)構(gòu)體）重載的 () 運(yùn)算符中自定義排序規(guī)則，并將其實(shí)例化后作為 priority_queue 模板的第 3 個(gè)參數(shù)傳入，即可實(shí)現(xiàn)為 priority_queue 容器適配器自定義比較函數(shù)。

除此之外，當(dāng) priority_queue 容器適配器中存儲(chǔ)的數(shù)據(jù)類型為結(jié)構(gòu)體或者類對(duì)象（包括 string 類對(duì)象）時(shí)，還可以通過重載其 > 或者 < 運(yùn)算符，間接實(shí)現(xiàn)自定義排序規(guī)則的目的。

注意，此方式僅適用于 priority_queue 容器中存儲(chǔ)的為類對(duì)象或者結(jié)構(gòu)體變量，也就是說，當(dāng)存儲(chǔ)類型為類的指針對(duì)象或者結(jié)構(gòu)體指針變量時(shí)，此方式將不再適用，而只能使用函數(shù)對(duì)象的方式。

要想徹底理解這種方式的實(shí)現(xiàn)原理，首先要搞清楚 std::less<T> 和 std::greater<T> 各自的底層實(shí)現(xiàn)。實(shí)際上，<function> 頭文件中的 std::less<T> 和 std::greater<T> ，各自底層實(shí)現(xiàn)采用的都是函數(shù)對(duì)象的方式。比如，std::less<T> 的底層實(shí)現(xiàn)代碼為：

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

std::greater<T> 的底層實(shí)現(xiàn)代碼為：

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

可以看到，std::less<T> 和 std::greater<T> 底層實(shí)現(xiàn)的唯一不同在于，前者使用 < 號(hào)實(shí)現(xiàn)從大到小排序，后者使用 > 號(hào)實(shí)現(xiàn)從小到大排序。

那么，是否可以通過重載 < 或者 > 運(yùn)算符修改 std::less<T> 和 std::greater<T> 的排序規(guī)則，從而間接實(shí)現(xiàn)自定義排序呢？答案是肯定的，舉個(gè)例子：

#include<queue>
#include<iostream>
using namespace std;
class node {
public:
  node(int x = 0, int y = 0) :x(x), y(y) {}
  int x, y;
};
//新的排序規(guī)則為：先按照 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() {
  //創(chuàng)建一個(gè) priority_queue 容器適配器，其使用默認(rèn)的 vector 基礎(chǔ)容器以及 less 排序規(guī)則。
  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;
}

輸出結(jié)果為：
x y
1 2
2 2
2 3
3 3
3 4

可以看到，通過重載 < 運(yùn)算符，使得 std::less<T> 變得適用了。
讀者還可以自行嘗試，通過重載 > 運(yùn)算符，賦予 std::greater<T> 和之前不同的排序方式。

當(dāng)然，也可以以友元函數(shù)或者成員函數(shù)的方式重載 > 或者 < 運(yùn)算符。需要注意的是，以成員函數(shù)的方式重載 > 或者 < 運(yùn)算符時(shí)，該成員函數(shù)必須聲明為 const 類型，且參數(shù)也必須為 const 類型，至于參數(shù)的傳值方式是采用按引用傳遞還是按值傳遞，都可以（建議采用按引用傳遞，效率更高）。

例如，將上面程序改為以成員函數(shù)的方式重載 < 運(yùn)算符：

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;
  }
};

同樣，在以友元函數(shù)的方式重載 < 或者 > 運(yùn)算符時(shí)，要求參數(shù)必須使用 const 修飾。例如，將上面程序改為以友元函數(shù)的方式重載 < 運(yùn)算符。例如：

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);
};
//新的排序規(guī)則為：先按照 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;
}

關(guān)于怎么在C++項(xiàng)目中利用priority_queue自定義排序就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。