Why does operator< need to be overloaded when implementing class-based priority queues in c++?

Question

note, I am not asking for answers. I simply am curious regarding why things work

I need to implement a priority queue for a printer simulator for a class assignment. After looking at examples on the internet, I noticed that operator< was being overloaded in order to arrange the priority queue correctly.

code in question: java2s priority queue example

Why does operator< need to be overloaded? Where is '<' even used to make the comparison? Does implementing the operator overload change the way the queue STL works?

This implementation doesn't seem intuitive to me at all: why isn't operator> being overloaded instead? How is one supposed to learn that operator< needs to be overloaded in order for the priority_queue to work correctly?

Answer 1

STL containers use operator< by default to order the contents, for those containers that order the contents.

You can override this by passing in a comparison functor to the constructor of the container, which allows you to decouple the sorting/ordering from the container object.

Operator> could have been chosen, but one had to be picked and that was operator<, and is then used everywhere for consistency.

Answer 2

Okay, the basic reason is that a priority queue is a structure in which inserted items are returned in the order of some order function. You need an ordering and the obvious way to handle it is by overloading operator<. You could have a function by name, but being able to say if( a < b) is arguably more readable than if(isLessThan(a,b)) or something like that.

You don't overload operator> because it isn't needed; the only operation you need in a priority queue is less-than. That doesn't mean you couldn't have one, but since you have an ==, you can implement it trivially -- or just reverse the operands.

Answer 3

Why does operator< need to be overloaded?

The Compare function object in priority_queue<T, Sequence, Compare>:

Compare induces a strict weak ordering, as defined in the LessThan Comparable requirements, on its argument type.

LessThanComparable documentation:

Notes

[1] Only operator< is fundamental; the other inequality operators are essentially syntactic sugar.

[2] Antisymmetry is a theorem, not an axiom: it follows from irreflexivity and transitivity.

[3] Because of irreflexivity and transitivity, operator< always satisfies the definition of a partial ordering. The definition of a strict weak ordering is stricter, and the definition of a total ordering is stricter still.

Where is '<' even used to make the comparison?

void push(const value_type& x) which inserts a value in the queue.

Does implementing the operator overload change the way the queue STL works?

Yes, of course. If you swap the order of elements in the comparison, your sort goes the other way.

Answer 4

FYI: std::priority_queue could accept Compare predicate.
operator< used just as default behaviour. It is minimal requirement.

why isn't operator> being overloaded instead

I think by historical reaqsons. In mathematic all examples usualy described for < operation, and one operator is enought for define all other operation ( >, <=, >=, ==, !=).

This implementation doesn't seem intuitive to me at all

For me this interface was expected. I think it as habbit.

Does implementing the operator overload change the way the queue STL works?

No, no. Not STL queue, only your queue - for your type, if your own comparator was not defined.

Answer 5

priority_queue<T> uses std::less<T>, which in turn requires T() < T() to be a valid expression. Could be a member, could be a non-member, but the expression has to be valid.

However, std::less<T> may be specialized, so your statement that operator< needs to be overloaded is a bit misleading.