Global inequality comparisons for pair<> in C++ standard

Question

As according to cppreference:

In inequality comparisons (<, >), the first elements are compared first, and only if the inequality comparison is not true for them, the second elements are compared.

which translates to something like this:

return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second)));

My quesion is, why is it so unintuitive? What is the reasoning behind it? And are there examples where this reasoning leads to the correct answers?

I thought the implementation will simply be:

return a.first < b.first && a.second < b.second

Answer 1

This sort of comparison is called a lexicographical ordering and is one of the more natural ways to combine two different orderings into one.

The orderings that are requested in C++ are called strict weak orderings. This means that the following should be true:

• Irreflexivity: x < x is always false.
• Transitivity: If x < y and y < z, then x < z.
• Antisymmetry: If x < y, then y < x is always false.
• Transitivity of Equivalence: If x and y are incomparable and y and z are incomparable, then x and z are incomparable.

These properties are what you need in order to guarantee that you can take a list of objects and put them into sorted ascending order. This means that you can use std::sort on them, or store them in a std::set.

You can prove with a bit of math that if you have two different strict weak orderings, then the lexicographical ordering you get by combining them as std::pair does is also a strict weak ordering. The lexicographical ordering is one of the few ways that you can combine strict weak orderings to make new strict weak orderings.

However, the ordering that you've suggested is not a strict weak ordering and will cause certain assumptions to break. In particular, consider the pairs (0, 5), (3, 3), and (1, 6). Then (0, 5) is incomparable with (3, 3) and (3, 3) is incomparable with (1, 6). However, we do indeed have that (0, 5) < (1, 6), which breaks the rule of transitivity of equivalence. As a result, many sorting algorithms that assume that equivalence is transitive (which includes most major sorting algorithms) will not work correctly on your range, meaning that std::sort might behave incorrectly. It also means that you also couldn't store these in a std::set, because the std::set interally stores everything in some kind of sorted order (usually a balanced binary search tree) and you might get completely wrong results.

Hope this helps!