Preferred implementation of '<' for multi-variable structures

Question

Initially this may seem overly abstract or philosophical, but I am genuinely interested to see if someone has a convincing argument in favor of one implementation over the other.

Given operator< for std::pair<T1, T2>, which would be the better implementation:

return x.first < y.first ||
       x.first == y.first && x.second < y.second;

or:

return x.first < y.first ||
       !(y.first < x.first) && x.second < y.second;

My understanding is that the two implementations yield equivalent results. Is the latter preferred because it is defined solely in terms of operator<? Or is it legitimate to assume that a type that is less-than comparible should also be equality comparable? Does anyone else see another point that would sway you between one or the other?

Naturally any answer should be both generic and extensible. So which one would you use and why? Is there a different implementation that's even better than the above?

Answer 1

It is not legitimate to assume that for any type, if it is less-than comparable, it is also equality comparable, since one can overload operator< but not overload operator==.

Thus, if you anticipate having to handle user-defined types, the second approach is preferable. However, you should add some parentheses to clarify the order of operations:

return x.first < y.first ||
       (!(y.first < x.first) && x.second < y.second);

Answer 2

The implementation are not equivalent if operator< represents a weak ordering. For example, imagine that objects of T1 are nodes in a digraph and T1a < T1d means "T1a is an ancestor of T1b in the graph" (this is not such an uncommon notation).

Then: !(T1b < T1a) would mean "t1b is not an ancestor of t1a" so either:

1. t1a is an ancestor of t1b (ruled out by the first test)
2. t1a is the same node as t1b
3. t1a and t1b are not comparable (i.e. they are siblings)

This third case is really important. In that case, you probably want operator< to return false on the pair, but it might not.

(A weak ordering on a set of elements means that a <= b and b <= a can both be false.)

Personally, I'm not fond of operator overloading, especially when used with generics. Programmers tend to assume nice "arithmetic" properties that do not always hold.