c++ - Why must std::sort compare function return false when arguments are equal?

Question

In std::sort you can supply a third argument which is the basis for how it sorts a list. If you want the first argument to come first, then you return true. If you want the second argument to come first you return false. I have come across the problem that my predicate function supposedly is an "invalid comparator", and I have narrowed it down to the fact that it does not fulfil the following requirement:

if arg1 == arg2, compare function MUST return false.

There have been some terms I have seen such as that std::sort requires "strict weak ordering". Apart from 2 places, all the other pages I get about these topics seem to be technical papers, and I can't understand it. What I can understand of it is that:

In weak ordering some elements "may be tied" with each other.

But to me this is also the meaning of a "partially ordered set", which is:

"there may be pairs of elements for which neither element precedes the other"

Furthermore, I can't understand what the "strict" implies in either of them.

Leaving aside my confusion about order theory terminology, my question is if in the compare function argument 1 and argument 2 are equal, and in which case I don't care which comes before the other (either one coming before would make me happy), why can't I return true to have argument 1 come first?

I was also going to ask how my program actually knows it's an invalid comparator but then I thought it probably just checks to see if arg1 and arg2 are equal when the compare function returns true.

Answer 1

The compare function simply models a "less than" operator. Consider how the < operator works for primitive types like int:

int a = 1, b = 2;     a < b == true      a is less than b
int a = 2, b = 1;     a < b == false     a is not less than b, because a is greater than b
int a = 1, b = 1;     a < b == false     a is not less than b, because a equals b

Returning true means you want a to be ordered before b. So return false if that is not the case, either because you want b to be ordered before a, or because their order doesn't matter.

If you return true when the arguments are equal, then you are saying that you want a to come before b and you want b to come before a, which is a contradiction.