I am having problem writing a custom comparator for priority queue in C++. The elements' type in the queue is pair<long long,pair<long long, long long>> I want the queue to rank the elements with the smallestfirst element first, and if there is a tie, rank the elements with the smallest second.first element first. If there's a tie again, rank the element with the smallest second.second element first. So I have the following comparator and declaration:
class cmp {
public:
bool operator()(pair<long long, pair<long long, long long>> A, pair<long long, pair<long long, long long>> B) {
if (A.first > B.first) {
return true;
}
if (A.first < B.first) {
return false;
}
if (A.first == B.first) {
if (A.second.first > B.second.first) {
return true;
}
if (A.second.first < B.second.first) {
return false;
}
if (A.second.second > B.second.second) {
return false;
}
return true;
}
}
};
int main()
{
priority_queue<pair<long long, pair<long long, long long>>,vector<pair<long long,pair<long long,long long>>>,cmp> q;
q.push(make_pair(0, make_pair(1, 1)));//first element
q.push(make_pair(9, make_pair(1, 1)));//second element
q.push(make_pair(0, make_pair(1, 2)));//third element
}
However, when I push the three elements shown in the code, the queue does not give me the correct ranking of first, third, and second. I am sure I made some mistake but I couldn't find it. Please help me. Thank you!
This is wrong.
As Benq said, the last if statement is wrong, it should return true. You don't need a custom comparison function though, you could just use greater<>, that is, replace cmp with greater<pair<long long,pair<long long,long long>>>.
Hi, Unfortunately even after I used greater it still was in the wrong order. It organized the elements as first, second and third instead of first, third, and second. Here is the code:
Is there something else I'm doing wrong? Thanks!
The code is right. Either you didn't save the code or you're checking the order of the queue wrong.
you're right. I used Visual Studio to debug and instead of printing out the elements I was just looking at the queue from the watch list. I just learned that priority_queue is not sorted at all times. Thanks!
Using the
<tuple>template instead of nested pairs as follows may be more convenient for your program.Best wishes