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 类对象)。