cpp STL: priority_queue自定义排序函数

priority_queue是C++的一种STL容器，实现为堆。在leetcode刷题中非常常用。有些时候我们需要塞入自定义的数据结构。这样就需要对其的排序方式做一个重新定义。
假设有以下数据结构

struct node {
    int x;
    int y;
};

对比方式为只看x的大小。把x的值大的放在堆顶。
则对比函数cmp写法如下：

1. 仿函数（函数对象）

用这种方式，需要显示的定义优先队列的容器类型（vector）以及比较函数（cmp）。

#include<iostream>
#include<queue>
using namespace std;
//函数对象类
template <typename T>
class cmp {
public:
    //重载 () 运算符
    bool operator()(T a, T b) {
        return a.x < b.x;
    }
};
struct node {
    int x;
    int y;
};
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node, vector<node>, cmp<node>> pq; // 显式指定容器类型和比较函数
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

2. 使用自定义类型比较关系

重载需要比较类型的$<$符号，之后在类型直接写类型名称即可。

#include<iostream>
#include<queue>
using namespace std;
struct node {
    int x;
    int y;
    bool operator < (node b) const { // 这里后面的const必须加
        return this->x < b.x;
    }
};
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node> pq; // 只写类型名称即可
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

3. 使用lambda表达式

使用lambda表达式需要在pq对象构造的时候，将lambda表达式作为参数传入其中。即pq(cmp)。

#include<iostream>
#include<queue>
#include<functional>
using namespace std;

struct node {
    int x;
    int y;
};
int main() {
    auto cmp = [](node x, node y) {
        return x.x < y.x;
    };
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    priority_queue<node, vector<node>, decltype(cmp)> pq(cmp); // 需要在pq对象创建的时候将lambda表达式作为参数传入
    // priority_queue<node, vector<node>, function<bool(node, node)> > pq(cmp); // 和上面的效果相同，但是用function需要包含头文件functional
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

4. 函数指针（和上面的相比有些多余，刷题不是很实用）

这种方式和lambda表达式的方式很类似。

#include<iostream>
#include<queue>
#include<functional>
using namespace std;

struct node {
    int x;
    int y;
};
bool cmp(node x, node y) {
    return x.x < y.x;
}
int main() {
    node a = {1,2};
    node b = {0,2};
    node c = {1,3};
    node d = {2,5};
    node e = {3,6};
    bool (*funcp)(node x, node y) = cmp;
    priority_queue<node, vector<node>, decltype(*funcp)> pq(*funcp);
    pq.push(a);
    pq.push(b);
    pq.push(c);
    pq.push(d);
    pq.push(e);
    while (!pq.empty()) {
        cout << pq.top().x << "," << pq.top().y << endl;
        pq.pop();
    }
    return 0;
}

结果：

@└────> # ./pq
3,6
2,5
1,3
1,2
0,2

reference：

https://blog.csdn.net/Strengthennn/article/details/119078911