Are these two comparison expressions identical?

Question

There seems to be some disagreement in another question about whether these two functions have identical logic:

bool operator<(const screenPoint& left, const screenPoint& right){

  if (left.x < right.x) return true;

  else return left.y < right.y;

}



bool operator<(const screenPoint& left, const screenPoint& right){

  return left.x < right.x || left.y < right.y;

}

I have stared at these for quite a while and I cannot see how they would behave differently. In both, if

left.x < right.x

, they both return

true

. If not, then they both return the result of

left.y < right.y

. Right?

If not, can someone please elaborate.

Also, it was suggested that the first of these is identical to the implementation of lexographical ordering in

std::tie

, is that true?

Answer 1

The two are identical to each other (if you fix the missing parenthesis in the first if), but they do not implement a strict weak ordering, so you probably don't want to use them (it would be invalid to use them in standard ordered containers and algorithms).

Proof: Consider the original relation for a=(1,3) b=(2,2). Then a < b and b < a. (asymmetric property violated)

A correct lexicographical ordering would look like this:

bool operator<(const screenPoint& left, const screenPoint& right){
    if (left.x < right.x) 
        return true;
    if (left.x > right.x)
        return false;
    return left.y < right.y;
}

If your members have only a < operator and not a > operator, replace left.x > right.x by !(right.x < left.x). This is how lexicographical comparison is implemented by std::pair and std::tuple (which is returned by std::tie).

Are these two comparison expressions identical?

Sign up