C++ 用户定义类型的优先队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9178083/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Priority queue for user-defined types
提问by Programmer
I have the below struct
我有以下结构
struct node{
float val;
int count;
}
I have several objects of this struct. Now, I want to insert these objects into a priority queue of STL such that the priority queue orders the items by count. Any idea on how to do so? Preferably a min heap is preferred. I know how to do the above for primitive data types, not structs
我有这个结构的几个对象。现在，我想将这些对象插入到 STL 的优先级队列中，以便优先级队列按计数对项目进行排序。关于如何这样做的任何想法？优选地，最小堆是优选的。我知道如何对原始数据类型执行上述操作，而不是结构
回答by Ivaylo Strandjev
Overload the < operator:
重载 < 运算符：
bool operator<(const node& a, const node& b) {
return a.count > b.count;
}
I have reversed the comparison to achieve min heap wihtout passing extra arguments to the priority queue. Now you use it like this:
我已经颠倒了比较以实现最小堆而不将额外的参数传递给优先级队列。现在你像这样使用它：
priority_queue<node> pq;
...
Edit: take a look at this post which seems to be almost exact duplicate: STL Priority Queue on custom class
编辑：看看这篇文章，它似乎几乎完全重复：STL Priority Queue on custom class
回答by Uday Hiwarale
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Boxer{
public:
string name;
int strength;
};
struct Comp{
bool operator()(const Boxer& a, const Boxer& b){
return a.strength<b.strength;
}
};
int main(){
Boxer boxer[3];
boxer[0].name="uday", boxer[0].strength=23;
boxer[1].name="manoj", boxer[1].strength=33;
boxer[2].name="rajiv", boxer[2].strength=53;
priority_queue< Boxer, vector<Boxer>, Comp> pq;
pq.push(boxer[0]);
pq.push(boxer[1]);
pq.push(boxer[2]);
Boxer b = pq.top();
cout<<b.name;
//result is Rajiv
return 0;
}
回答by Taohidul Islam
Using
greateras comparison function you can use priority queue as min heap,#include <bits/stdc++.h> using namespace std; int main() { priority_queue<int,vector<int>,greater<int> >pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout << r << " "; } return 0; }Inserting value by changing their sign (using minus (-) for positive number and using plus (+) for negative number we can use priority queue in reversed order.
int main() { priority_queue<int>pq2; pq2.push(-1); //for +1 pq2.push(-2); //for +2 pq2.push(-3); //for +3 pq2.push(4); //for -4 while(!pq2.empty()) { int r = pq2.top(); pq2.pop(); cout << -r << " "; } return 0; }For custom data types or classes we need a to tell priority queue a way of knowing on which order it will sort our data.
struct compare { bool operator()(const int & a, const int & b) { return a>b; } }; int main() { priority_queue<int,vector<int>,compare> pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout << r << " "; } return 0; }For custom structure or class you can use
priority_queuein any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.struct people { int age,salary; }; struct compare { bool operator()(const people & a, const people & b) { if(a.salary==b.salary) { return a.age>b.age; } else { return a.salary>b.salary; } } }; int main() { priority_queue<people,vector<people>,compare> pq; people person1,person2,person3; person1.salary=100; person1.age = 50; person2.salary=80; person2.age = 40; person3.salary = 100; person3.age=40; pq.push(person1); pq.push(person2); pq.push(person3); while(!pq.empty()) { people r = pq.top(); pq.pop(); cout << r.salary << " " << r.age << endl; }Same result can be obtained by operator overloading :
struct people { int age,salary; bool operator< (const people & p) const { if(salary==p.salary) { return age>p.age; } else { return salary>p.salary; } } };
使用
greater作为比较函数，您可以使用优先队列作为最小堆，#include <bits/stdc++.h> using namespace std; int main() { priority_queue<int,vector<int>,greater<int> >pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout << r << " "; } return 0; }通过更改符号来插入值（使用减号 (-) 表示正数，使用加号 (+) 表示负数，我们可以以相反的顺序使用优先级队列。
int main() { priority_queue<int>pq2; pq2.push(-1); //for +1 pq2.push(-2); //for +2 pq2.push(-3); //for +3 pq2.push(4); //for -4 while(!pq2.empty()) { int r = pq2.top(); pq2.pop(); cout << -r << " "; } return 0; }对于自定义数据类型或类，我们需要一个告诉优先级队列的方式来了解它将对我们的数据进行排序的顺序。
struct compare { bool operator()(const int & a, const int & b) { return a>b; } }; int main() { priority_queue<int,vector<int>,compare> pq; pq.push(1); pq.push(2); pq.push(3); while(!pq.empty()) { int r = pq.top(); pq.pop(); cout << r << " "; } return 0; }对于自定义结构或类，您可以
priority_queue按任何顺序使用。假设，我们想根据工资降序对人进行排序，如果并列则根据他们的年龄排序。struct people { int age,salary; }; struct compare { bool operator()(const people & a, const people & b) { if(a.salary==b.salary) { return a.age>b.age; } else { return a.salary>b.salary; } } }; int main() { priority_queue<people,vector<people>,compare> pq; people person1,person2,person3; person1.salary=100; person1.age = 50; person2.salary=80; person2.age = 40; person3.salary = 100; person3.age=40; pq.push(person1); pq.push(person2); pq.push(person3); while(!pq.empty()) { people r = pq.top(); pq.pop(); cout << r.salary << " " << r.age << endl; }通过运算符重载可以获得相同的结果：
struct people { int age,salary; bool operator< (const people & p) const { if(salary==p.salary) { return age>p.age; } else { return salary>p.salary; } } };
In main function :
在主函数中：
priority_queue<people> pq;
people person1,person2,person3;
person1.salary=100;
person1.age = 50;
person2.salary=80;
person2.age = 40;
person3.salary = 100;
person3.age=40;
pq.push(person1);
pq.push(person2);
pq.push(person3);
while(!pq.empty())
{
people r = pq.top();
pq.pop();
cout << r.salary << " " << r.age << endl;
}
回答by R. Martinho Fernandes
You need to provide operator<for that struct. Something like:
您需要提供operator<该结构。就像是：
bool operator<(node const& x, node const& y) {
return x.count < y.count;
}
Now you can use a priority queue from the standard library.
现在您可以使用标准库中的优先级队列。
回答by rashedcs
We can define user defined comparator class:
我们可以定义用户定义的比较器类：
Code Snippet :
代码片段：
#include<bits/stdc++.h>
using namespace std;
struct man
{
string name;
int priority;
};
class comparator
{
public:
bool operator()(const man& a, const man& b)
{
return a.priority<b.priority;
}
};
int main()
{
man arr[5];
priority_queue<man, vector<man>, comparator> pq;
for(int i=0; i<3; i++)
{
cin>>arr[i].name>>arr[i].priority;
pq.push(arr[i]);
}
while (!pq.empty())
{
cout<<pq.top().name<<" "<<pq.top().priority;
pq.pop();
cout<<endl;
}
return 0;
}
回答by yukinarit
Since C++11, you can write
从 C++11 开始，你可以写
auto comparer = [](const auto& a, const auto& b) {
return a.priority < b.priority;
};
std::priority_queue<Item, std::vector<Item>, decltype(comparer)> queue(comparer);
