C++ priority_queue自定义排序

Posted on Edited on Symbols count in article: 1.4k Reading time ≈ 1 mins.

C++ priority_queue自定义排序总结

方法一：函数指针

以下几种都可以，具体可参考《C++ Primer》

1
2
3
4
5
6
7
8
9
10
typedef int elem;
bool cmp(elem a, elem b) {
    return a < b;
}
priority_queue<elem, vector<elem>, decltype(&cmp)> q(arr.begin(), arr.end(), cmp);
priority_queue<elem, vector<elem>, decltype(cmp)*> q(arr.begin(), arr.end(), cmp);
priority_queue<elem, vector<elem>, bool(*)(elem, elem)> q(arr.begin(), arr.end(), cmp);
// 构造函数前两个可以不填，但是必须传入cmp
// 前面模板只是告诉它是一个函数指针bool(*)(elem, elem)，但并没有传入函数地址（实体）
priority_queue<elem, vector<elem>, bool(*)(elem, elem)> q(cmp);

**对于cmp和&cmp你应该这样理解，cmp是函数的首地址，它的类型是bool(elem, elem)，&cmp表示一个指向函数cmp这个对象的地址，它的类型是bool(*)(elem, elem)，因此test和&test所代表的地址的值是一样的，但类型不一样！**

方法二：重载运算符

1
2
3
4
5
6
7
8
struct elem {
    int a;
    int b;
    bool operator<(const elem& another) const {
        return this->b < another.b;
    }
};
priority_queue<elem, vector<elem>, less<elem>> q;

注意：operator函数要有const，这是能构成重载的，否则未找到对应函数报错

方法三：仿函数

1
2
3
4
5
6
7
8
9
10
11
struct elem {
    int a;
    int b;
};
struct cmp {
    bool operator()(const elem& left, const elem& right) {
        return left.b < right.b;
    }
};
priority_queue<elem, vector<elem>, cmp> q;
priority_queue<elem, vector<elem>, cmp> q(arr.begin(), arr.end()); // 不需要传入cmp参数

方法四：匿名函数（类似仿函数）

1
2
auto cmp = [](const item& a, const item& b) {return a.first < b.first; }; // 实例
priority_queue<item, vector<item>, decltype(cmp)> pq(arr.begin(), arr.end(), cmp); // decltype解析类型，并需要传入实例