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.

Answer 3

I would use the second, because that's what the Standard specifies!

The two definitions are, as others have mentioned, equivalent as long as < defines a total ordering on both types and == is consistent with <. But when either is not true, the difference is observable and if you used the first definition you wouldn't be conforming.

EDIT: The Standard definition is better than your first definition in one sense: if < defines a strict weak ordering on both T1 and T2, then the Standard definition gives a strict weak ordering on pair<T1, T2>. Your first definition doesn't, and this can cause real problems. For example, suppose we have x and y such that neither x < y nor y < x. Then consider the array of pairs a[3] = {P(x, 2), P(y, 1), P(x, 1)}. Clearly we should say this array is not sorted in ascending order, because a[2] < a[0]. But if we use your first definition, std::is_sorted would conclude that the array is sorted, because no two consecutive elements are comparable. The fact that the first definition is not a strict weak ordering breaks the algorithm. Under the Standard definition, P(y, 1) < P(x, 2), and so the algorithm detects that the array is not sorted as desired.

(This answer previously had a totally incorrect analysis of this situation -- sorry!)

Answer 4

I use this notation:

return (x1 == x2) ? (x2 < y2) : (x1 < x2);