0

I'm trying to understand how comparator works for priority queue, I did several tests:

Test 1: Create comparator class, and use priority_queue<T, vector<T>, cmp>

It always works fine

Test 2:

struct test {
    int a = 0;
};

bool operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

int main() 
{
    priority_queue<test> pq;
}

This works as expected.

Test 3: Put test 2 inside a class

class T{
    struct test {
        int a = 0;
    };

    bool operator<(const test& lhs, const test& rhs) {
        return lhs.a < rhs.a;
    }
};

Compiling Error:

'bool T::operator<(const T::test&, const T::test&)' must take exactly one argument

It seems that the compiler thought that I was overloading the operator < for class T. Is there any other ways to accomplish this if I really need the classes to be nested?

Test 4: Overload operator<

struct test {
    int a = 0;
    bool operator<(const test& rhs) {
        return a < rhs.a;
    }
};

int main() 
{
    vector<test> v;
    sort(v.begin(), v.end());   // No error
    set<test> s;                // No error
    priority_queue<test> pq;    // Compiling error
}

Only priority_queue throws an error:

'passing 'const test*' as 'this' argument discards qualifiers'

I don't know why this works for sort and set but not for priority queue.

Improve this question
3
  • 1
    You made the operator< a method of T. Either declare it inside T::test as a friend, or declare it outside T entirely. Commented Apr 29, 2018 at 22:56
  • 4: stackoverflow.com/questions/550428/… , a comparison should not change the object being compared. Commented Apr 29, 2018 at 22:59
  • And the answer to your second question is that the operator should be const-qualified if it isn't going to change the lhs (which it isn't). Stick a const before the {. And Please ask one question per question. Commented Apr 29, 2018 at 22:59

2 Answers 2

Reset to default
2

The operator< must take two arguments while when you make it a member of class T, it implicitly gets this as the third argument, thus the error in Test 3:

class T {
  bool operator<(const test& lhs, const test& rhs) { // error
    return lhs.a < rhs.a;
  }
};

To fix this, define operator< in the nested test class:

class T {
public:
  struct test {
    int a = 0;
    friend bool operator<(const test& lhs, const test& rhs) {
      return lhs.a < rhs.a;
    }
  };
};

or at the namespace scope.

And in Test 4 operator< should be const:

struct test {
  int a = 0;
  bool operator<(const test& rhs) const {
    return a < rhs.a;
  }
};
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you very much! I'm still a little confused about test 4. Why sort and set don't require the const signature? It doesn't look very consistent to me.
@Seraph I think that technically priority_queue doesn't have to require const, but operator< defined in such way will be inconsistent and test won't satisfy LessThanComparable concept: en.cppreference.com/w/cpp/concept/LessThanComparable
1

A comparator for a priority_queue works as for any other comparator. It should be able to participate in the expression 

if (compare(element1, element2))

The default implementation reduces to

if (element1 < element 2) ....

What you did in 3 resulted in

if ( tObject.operator<(anotherTObject, yetAnotherTObject))

So your

bool T::operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

should really be comparing to the object itself like

bool T::operator<(const test& rhs) const {
    auto lhs = *this;
    return lhs.a < rhs.a;
}

The last const acts like the const on the first argument in vitauts reasonable answer.

Improve this answer

4 Comments

Thank you very much! I'm still a little confused about test 4. Why sort and set don't require the const signature? It doesn't look very consistent to me.
@Seraph In a priority queue you cant change the keys inside the structure, or the queue would be invalid. This would also be true for a set.
Thanks again. I did some further test, there is no error when declaring the set, but if I tried to insert an object, it would throw the same error.
@Seraph Good testing!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.