STL priority_queue自定义排序实现方法详解

概述前面在讲解 priority_queue 容器适配器时遗留了一个问题，即当 function 头文件提供的排序方式（std::lessT 和 std::greaterT）不再适用时，如何自定义一个满足需求的排序规则。 首先，无论 pr 前面讲解 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,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,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 类对象）。 总结

以上是内存溢出为你收集整理的STL priority_queue自定义排序实现方法详解全部内容，希望文章能够帮你解决STL priority_queue自定义排序实现方法详解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。