class Person
{
public:
int age;
};
我想将 Person 类的对象存储在优先级队列中。
priority_queue< Person, vector<Person>, ??? >
我想我需要为比较的东西定义一个类，但我不确定。
此外，当我们写作时，
priority_queue< int, vector<int>, greater<int> >
更大的如何工作？
问问题
135061 次
5 回答
113
Person在这种情况下，您需要为存储在队列中的类型提供有效的严格弱排序比较。默认是使用std::less<T>，它解析为等价于operator<. 这依赖于它自己的存储类型有一个。所以如果你要实施
bool operator<(const Person& lhs, const Person& rhs);
它应该可以在没有任何进一步更改的情况下工作。实施可能是
bool operator<(const Person& lhs, const Person& rhs)
{
return lhs.age < rhs.age;
}
如果该类型没有自然的“小于”比较，则提供您自己的谓词而不是 default 会更有意义std::less<Person>。例如，
struct LessThanByAge
{
bool operator()(const Person& lhs, const Person& rhs) const
{
return lhs.age < rhs.age;
}
};
然后像这样实例化队列：
std::priority_queue<Person, std::vector<Person>, LessThanByAge> pq;
关于std::greater<Person>作为比较器的使用，这将使用相当于operator>并具有创建优先级反转 WRT 默认情况下的队列的效果。它需要一个operator>可以在两个Person实例上运行的存在。
于 2013-10-23T07:41:51.813 回答
52
您将编写一个比较器类，例如：
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;
}
};
并将其用作比较器参数：
priority_queue<Person, vector<Person>, CompareAge>
Usinggreater给出了与 default 相反的顺序less，这意味着队列将为您提供最低值而不是最高值。
于 2013-10-23T07:43:23.177 回答
20
优先级队列是一种抽象数据类型，它捕获了一个容器的概念，该容器的元素具有附加的“优先级”。最高优先级的元素总是出现在队列的前面。如果该元素被删除，则下一个最高优先级元素将前进到前面。
C++标准库定义了一个类模板priority_queue，操作如下：
push：将一个元素插入优先队列。
top：从优先级队列中返回（不删除）最高优先级元素。
pop：从优先级队列中删除最高优先级的元素。
size：返回优先级队列中的元素数。
empty：根据优先级队列是否为空返回 true 或 false。
下面的代码片段展示了如何构造两个优先级队列，一个可以包含整数，另一个可以包含字符串：
#include <queue>
priority_queue<int> q1;
priority_queue<string> q2;
以下是优先队列使用示例：
#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 quick
the lazy dog
jumped over
fox
由于队列遵循优先级规则，因此字符串从最高优先级到最低优先级打印。
有时需要创建一个优先级队列来包含用户定义的对象。在这种情况下，优先级队列需要知道用于确定哪些对象具有最高优先级的比较标准。这是通过属于重载运算符 () 的类的函数对象来完成的。重载的 () 充当 < 用于确定优先级。例如，假设我们要创建一个优先级队列来存储 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;
}
}
根据上述比较标准存储时间的优先级队列将定义如下：
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;
}
该程序从最晚到最早打印时间：
5 16 13
5 14 20
3 2 40
3 2 26
如果我们希望最早的时间具有最高优先级，我们将像这样重新定义 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;
}
};
于 2015-10-16T02:13:54.313 回答
4
这段代码可能会有所帮助..
#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();
}
}
输出：
22 prashantonly
22 prashant
23 prashantandsoon..
于 2015-10-02T08:36:33.063 回答
0
我们可以定义用户定义的比较器：。下面的代码可能对您有所帮助。
代码片段：
#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;
}
输入 ：
蝙蝠侠 2
悟空 9
马里奥 4
输出
悟空 9
马里奥 4
蝙蝠侠 2
于 2017-07-04T04:31:06.077 回答