Iwaskid's blog

Help with priority_queue custom comparator C++
By Iwaskid, history, 7 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This is wrong.

if (A.second.second > B.second.second) {
    return false;
}
→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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>>>.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    priority_queue<pair<long long, pair<long long, long long>>,vector<pair<long long,pair<long long,long long>>>,greater<pair<long long,pair<long long, long long>>>> q;
	q.push(make_pair(0, make_pair(1, 1)));//first
	q.push(make_pair(9, make_pair(1, 1)));//second
	q.push(make_pair(0, make_pair(1, 2)));//third

    Is there something else I'm doing wrong? Thanks!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The code is right. Either you didn't save the code or you're checking the order of the queue wrong.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        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!

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Using the <tuple> template instead of nested pairs as follows may be more convenient for your program.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef tuple< ll, ll, ll > tuple_t;

int main()
{
    priority_queue< tuple_t > q;

    q.push( tuple_t( 0, 1, 1 ) ),
	q.push( tuple_t( 9, 1, 1 ) ),
	q.push( tuple_t( 0, 1, 2 ) );

	while( !q.empty() )
    {
        tuple_t t = q.top();

        cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " " << endl;

        q.pop();
    }

}

Best wishes

→ Reply