如何使用对象的优先级队列STL？
class Person { public: int age; }; 我想将Person类的对象存储在优先级队列中。
priority_queue< Person, vector<Person>, ??? >
我觉得我需要为比较而定义一个类，但是我不确定。
另外，当我们写，
priority_queue< int, vector<int>, greater<int> >
如何做更大的工作？
您需要为存储在队列中的typesPerson提供有效的严格的弱sorting比较。 默认是使用std::less<T> ，它parsing为相当于operator<东西。 这依赖于它自己的存储types。 所以如果你要实施
bool operator<(const Person& lhs, const Person& rhs);
它应该没有任何进一步的变化。 实施可能是
bool operator<(const Person& lhs, const Person& rhs) { return lhs.age < rhs.age; }
如果types没有自然的“小于”比较，那么提供自己的谓词而不是默认的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>的等效operator>并产生一个优先级反转WRT的队列，这是默认情况。 这将需要在两个Person实例上运行的operator>的存在。
你会写一个比较类，例如：
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>
使用greater给予相反的顺序，默认less ，这意味着队列会给你最低的价值，而不是最高的。
优先级队列是一种抽象数据types，它捕获一个容器的元素具有“优先级”的属性。 优先级最高的元素总是出现在队列的前面。 如果删除该元素，则下一个最高优先级元素前进。
C ++标准库定义了一个类模板priority_queue，包含以下操作：
push ：将一个元素插入优先队列。
top ：从优先级队列中返回（不删除它）最高优先级的元素。
pop ：从优先级队列中删除最高优先级的元素。
size ：返回优先级队列中的元素个数。
empty ：根据优先级队列是否为空，返回true或false。
以下代码片段显示了如何构build两个优先级队列，一个可以包含整数，另一个可以包含string：
#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.front() << endl; // Print highest priority string pq.pop(); // Remmove highest priority string } return 0; }
这个程序的输出是：
the quick the lazy dog jumped over fox
由于队列遵循优先级规则，string从最高优先级打印到最低优先级。
有时需要创build一个优先级队列来包含用户定义的对象。 在这种情况下，优先级队列需要知道用于确定哪些对象具有最高优先级的比较标准。 这是通过函数对象beloging到一个重载operator（）的类来完成的。 重载的（）作为确定优先级的目的。 例如，假设我们要创build一个优先级队列来存储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; } };
这段代码可能有帮助..
#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..
我们可以定义用户定义的比较器：下面的代码可以帮助你。
代码片段：
#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：
蝙蝠侠2
悟空9
马里奥4
产量
悟空9
马里奥4
蝙蝠侠2
