C++ 如何对对象使用优先队列 STL？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19535644/
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
How to use the priority queue STL for objects?
提问by user2441151
class Person
{
public:
int age;
};
I want to store objects of the class Person in a priority queue.
我想将 Person 类的对象存储在优先级队列中。
priority_queue< Person, vector<Person>, ??? >
I think I need to define a class for the comparison thing, but I am not sure about it.
我想我需要为比较事物定义一个类，但我不确定。
Also, when we write,
此外，当我们写作时，
priority_queue< int, vector<int>, greater<int> >
How does the greater work?
更大的工作如何？
回答by juanchopanza
You need to provide a valid strict weak ordering comparison for the type stored in the queue, Personin this case. The default is to use std::less<T>, which resolves to something equivalent to operator<. This relies on it's own stored type having one. So if you were to implement
Person在这种情况下，您需要为存储在队列中的类型提供有效的严格弱排序比较。默认为 use std::less<T>，它解析为等效于operator<. 这依赖于它自己的存储类型。所以如果你要实施
bool operator<(const Person& lhs, const Person& rhs);
it should work without any further changes. The implementation could be
它应该无需任何进一步更改即可工作。实施可能是
bool operator<(const Person& lhs, const Person& rhs)
{
return lhs.age < rhs.age;
}
If the the type does not have a natural "less than" comparison, it would make more sense to provide your own predicate, instead of the default std::less<Person>. For example,
如果该类型没有自然的“小于”比较，则提供您自己的谓词而不是默认值会更有意义std::less<Person>。例如，
struct LessThanByAge
{
bool operator()(const Person& lhs, const Person& rhs) const
{
return lhs.age < rhs.age;
}
};
then instantiate the queue like this:
然后像这样实例化队列：
std::priority_queue<Person, std::vector<Person>, LessThanByAge> pq;
Concerning the use of std::greater<Person>as comparator, this would use the equivalent of operator>and have the effect of creating a queue with the priority inverted WRT the default case. It would require the presence of an operator>that can operate on two Personinstances.
关于std::greater<Person>作为比较器的使用，这将使用等效于operator>并具有创建优先级反转 WRT 默认情况下的队列的效果。它需要存在operator>可以在两个Person实例上运行的 。
回答by Mike Seymour
You would write a comparator class, for example:
您将编写一个比较器类，例如：
struct CompareAge {
bool operator()(Person const & p1, Person const & p2) {
// return "true" if "p1" is ordered before "p2", for example:
return p1.age < p2.age;
}
};
and use that as the comparator argument:
并将其用作比较器参数：
priority_queue<Person, vector<Person>, CompareAge>
Using greatergives the opposite ordering to the default less, meaning that the queue will give you the lowest value rather than the highest.
Usinggreater给出与 default 相反的顺序less，这意味着队列将为您提供最低值而不是最高值。
回答by Siddharth Kumar
A priority queue is an abstract data type that captures the idea of a container whose elements have "priorities" attached to them. An element of highest priority always appears at the front of the queue. If that element is removed, the next highest priority element advances to the front.
优先级队列是一种抽象数据类型，它捕捉容器的概念，其元素具有附加到它们的“优先级”。最高优先级的元素总是出现在队列的前面。如果该元素被移除，则下一个优先级最高的元素会前进到最前面。
The C++ standard library defines a class template priority_queue, with the following operations:
C++标准库定义了一个类模板priority_queue，操作如下：
push: Insert an element into the prioity queue.
push：将一个元素插入优先队列。
top: Return (without removing it) a highest priority element from the priority queue.
top：从优先级队列中返回（不删除）最高优先级的元素。
pop: Remove a highest priority element from the priority queue.
pop：从优先级队列中删除最高优先级的元素。
size: Return the number of elements in the priority queue.
size：返回优先级队列中元素的数量。
empty: Return true or false according to whether the priority queue is empty or not.
empty: 根据优先级队列是否为空，返回真或假。
The following code snippet shows how to construct two priority queues, one that can contain integers and another one that can contain character strings:
以下代码片段显示了如何构造两个优先级队列，一个可以包含整数，另一个可以包含字符串：
#include <queue>
priority_queue<int> q1;
priority_queue<string> q2;
The following is an example of priority queue usage:
以下是优先级队列使用的示例：
#include <string>
#include <queue>
#include <iostream>
using namespace std; // This is to make available the names of things defined in the standard library.
int main()
{
piority_queue<string> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.
pq.push("the quick");
pq.push("fox");
pq.push("jumped over");
pq.push("the lazy dog");
// The strings are ordered inside the priority queue in lexicographic (dictionary) order:
// "fox", "jumped over", "the lazy dog", "the quick"
// The lowest priority string is "fox", and the highest priority string is "the quick"
while (!pq.empty()) {
cout << pq.top() << endl; // Print highest priority string
pq.pop(); // Remmove highest priority string
}
return 0;
}
The output of this program is:
这个程序的输出是：
the quick
the lazy dog
jumped over
fox
Since a queue follows a priority discipline, the strings are printed from highest to lowest priority.
由于队列遵循优先级规则，因此字符串从最高优先级到最低优先级打印。
Sometimes one needs to create a priority queue to contain user defined objects. In this case, the priority queue needs to know the comparison criterion used to determine which objects have the highest priority. This is done by means of a function object belonging to a class that overloads the operator (). The overloaded () acts as < for the purpose of determining priorities. For example, suppose we want to create a priority queue to store Time objects. A Time object has three fields: hours, minutes, seconds:
有时需要创建一个优先级队列来包含用户定义的对象。在这种情况下，优先级队列需要知道用于确定哪些对象具有最高优先级的比较标准。这是通过属于重载运算符 () 的类的函数对象来完成的。重载的 () 充当 < 用于确定优先级。例如，假设我们要创建一个优先级队列来存储 Time 对象。Time 对象具有三个字段：小时、分钟、秒：
struct Time {
int h;
int m;
int s;
};
class CompareTime {
public:
bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
{
if (t1.h < t2.h) return true;
if (t1.h == t2.h && t1.m < t2.m) return true;
if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
return false;
}
}
A priority queue to store times according the the above comparison criterion would be defined as follows:
根据上述比较标准存储时间的优先队列将定义如下：
priority_queue<Time, vector<Time>, CompareTime> pq;
Here is a complete program:
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
struct Time {
int h; // >= 0
int m; // 0-59
int s; // 0-59
};
class CompareTime {
public:
bool operator()(Time& t1, Time& t2)
{
if (t1.h < t2.h) return true;
if (t1.h == t2.h && t1.m < t2.m) return true;
if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
return false;
}
};
int main()
{
priority_queue<Time, vector<Time>, CompareTime> pq;
// Array of 4 time objects:
Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};
for (int i = 0; i < 4; ++i)
pq.push(t[i]);
while (! pq.empty()) {
Time t2 = pq.top();
cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
setw(3) << t2.s << endl;
pq.pop();
}
return 0;
}
The program prints the times from latest to earliest:
该程序从最晚到最早打印时间：
5 16 13
5 14 20
3 2 40
3 2 26
If we wanted earliest times to have the highest priority, we would redefine CompareTime like this:
如果我们希望最早的时间具有最高优先级，我们可以像这样重新定义 CompareTime：
class CompareTime {
public:
bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
{
if (t2.h < t1.h) return true;
if (t2.h == t1.h && t2.m < t1.m) return true;
if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
return false;
}
};
回答by bitbyter
This piece of code may help..
这段代码可能会有所帮助..
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int age;
string name;
node(int a, string b){
age = a;
name = b;
}
};
bool operator<(const node& a, const node& b) {
node temp1=a,temp2=b;
if(a.age != b.age)
return a.age > b.age;
else{
return temp1.name.append(temp2.name) > temp2.name.append(temp1.name);
}
}
int main(){
priority_queue<node> pq;
node b(23,"prashantandsoon..");
node a(22,"prashant");
node c(22,"prashantonly");
pq.push(b);
pq.push(a);
pq.push(c);
int size = pq.size();
for (int i = 0; i < size; ++i)
{
cout<<pq.top().age<<" "<<pq.top().name<<"\n";
pq.pop();
}
}
Output:
输出：
22 prashantonly
22 prashant
23 prashantandsoon..
回答by rashedcs
We can define user defined comparator: .The code below can be helpful for you.
我们可以定义用户定义的比较器： .下面的代码可以对您有所帮助。
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;
}
input :
输入 ：
batman 2
goku 9
mario 4
蝙蝠侠 2
悟空 9
马里奥 4
Output
输出
goku 9
mario 4
batman 2
悟空 9
马里奥 4
蝙蝠侠 2
