Geek Answers Handbook

Preferred '<' implementation for multi-variable structures

At first, this may seem overly abstract or philosophical, but I'm really interested to find out if anyone has a convincing argument in favor of one implementation over another.

Given operator< for std::pair<T1, T2> , this would be a 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;

I understand that two implementations give equivalent results. Is the latter preferable because it is defined exclusively in terms of operator< ? Or is it legitimate to assume that a type that is less than comparable should also be comparable equality? Does anyone else see another point that will affect you between one or the other?

Naturally, any answer should be both general and extensible. So which one would you use and why? Is there any other implementation that is even better than the above?

+6
source share
3 answers

It cannot be assumed that for any type, if it is less than comparable, it is equal, since you can overload operator< , but not overload operator== .

Thus, if you expect that you will have to handle user-defined types, a second approach is preferable. However, you must add some parentheses to clarify the order of operations:

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

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

Then:! !(T1b < T1a) will mean that "t1b is not an ancestor of t1a", therefore either:

  • t1a is the ancestor of t1b (excluded by the first test)
  • t1a is the same node as t1b
  • t1a and t1b are not comparable (i.e. are brothers and sisters)

This third case is really important. In this case, you probably need the <operator to return false a couple, but it may not be.

(Weak ordering on multiple elements means that a <= b and b <= a can be false.)

Personally, I do not like operator overloading, especially when used with generics. Programmers tend to assume good "arithmetic" properties that are not always preserved.

+4
source

I would use the second because it indicates the standard!

Two definitions, as others have noted, are equivalent if < defines the general order for both types, and == matches < . But when this is either wrong, the difference is observable, and if you used the first definition that you would not correspond.

EDIT: The standard definition is better than your first definition in one sense: if < defines strict weak ordering on both T1 and T2, then the standard definition gives strict weak ordering on pair<T1, T2> . Your first definition does not, and this can cause real problems. Suppose, for example, that x and y are such that neither x < y nor y < x . Then we consider an array of pairs a[3] = {P(x, 2), P(y, 1), P(x, 1)} . It is clear that we must say that this array is not sorted in ascending order because a[2] < a[0] . But if we use your first definition, std::is_sorted will conclude that the array is sorted, because no two consecutive elements are comparable. The fact that the first definition is not a strict weak order violates the algorithm. In the standard definition, P(y, 1) < P(x, 2) , and therefore the algorithm detects that the array is not sorted as desired.

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

+2
source

More articles:


All Articles