admin管理员组文章数量:1624338
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;
}
结果:
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;
}
结果:
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;
}
结果:
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;
}
结果:
reference:
https://blog.csdn/Strengthennn/article/details/119078911
本文标签: 自定义函数stlpriorityqueue
版权声明:本文标题:【C++ STL】priority_queue自定义排序函数 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728895610a1178368.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论