admin管理员组文章数量:1623784
目录
一、重载运算符 <
二、使用函数指针
三、使用 lambda 表达式(建议记忆)
四、实际以链表节点Node举例
在 C++ 中,可以通过重载运算符 <
或自定义比较函数来定义 priority_queue 的排序规则。priority_queue对于基本数据类型,默认为大顶堆。
以下是几种自定义比较函数的方法:
一、重载运算符 <
可以在元素类型中重载运算符 <
,然后使用默认构造函数创建 priority_queue 对象即可。
例如,如果要按照元素值从大到小排序(小顶堆),则可以这样定义:
struct MyType {
int val;
bool operator<(const MyType& other) const {
return val > other.val; // 从大到小排序
}
};
priority_queue<MyType> pq;
二、使用函数指针
可以使用函数指针作为第三个模板参数,指定比较函数。
例如,如果要按照元素值从大到小排序(小顶堆),则可以这样定义:
struct MyType {
int val;
};
bool cmp(const MyType& a, const MyType& b) {
return a.val > b.val; // 从小到大排序
}
priority_queue<MyType, vector<MyType>, decltype(&cmp)> pq(&cmp);
三、使用 lambda 表达式(建议记忆)
C++11 引入了 lambda 表达式,可以方便地定义匿名函数,用于自定义比较函数。可以将 lambda 表达式作为第三个模板参数或传递给构造函数。
例如,如果要按照元素值从大到小排序(小顶堆),则可以这样定义:
auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
建议记忆,更灵活,更方便。
四、实际以链表节点Node举例
talk is cheap:
#include<queue>
#include <iostream>
using namespace std;
struct Node {
int val;
Node *next;
Node(int val) : val(val), next(nullptr) {};
// 大顶堆:重载<
bool operator<(const Node &node) const {
return this->val < node.val;
}
};
// 大顶堆:使用函数指针
bool cmp(const Node *node1, const Node *node2) {
return node1->val < node2->val;
}
int main() {
/* 默认类型,默认比较函数 */
// 默认大顶堆
priority_queue<int> maxHeap0;
priority_queue<int, vector<int>, less<int>> maxHeap1;
// 小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap0;
/* 自定义类型,自定义比较函数 */
// 大顶堆:Lambda表达式,表达less
auto lam = [](Node *node1, Node *node2) {
return node1->val < node2->val;
};
priority_queue<Node*, vector<Node*>, decltype(lam)> maxHeap2(lam); // 牢记写法
// 大顶堆:自定义函数,其实跟lambda表达式原理一样
priority_queue<Node*, vector<Node*>, decltype(&cmp)> maxHeap4(&cmp);
maxHeap4.emplace(new Node(2));
maxHeap4.emplace(new Node(1));
maxHeap4.emplace(new Node(3));
cout << maxHeap4.top()->val << endl;
// 大顶堆:重载<,表达less
// 这种缺点就是不能priority_queue<Node*>,因为Node*的大小比较并没有定义
priority_queue<Node> maxHeap5;
maxHeap5.emplace(Node(5));
maxHeap5.emplace(Node(6));
maxHeap5.emplace(Node(4));
cout << maxHeap5.top().val << endl;
return 0;
}
版权声明:本文标题:一文看懂priority_queue自定义比较函数有几种方法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728895282a1178330.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论