Блог пользователя Iwaskid

Автор Iwaskid, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

This is wrong.

if (A.second.second > B.second.second) {
    return false;
}
»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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!

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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