The C++ library facilities for sorting, binary searching, and ordered containers work only on types with appropriate order relations defined on them. For example, if v has type vector<T>, and we wish to call sort(v.begin(), v.end()), the call will work properly only if T has an appropriately defined operator<. If there is an appropriate operation with a different name, such as compare, we could call sort(v.begin(), v.end(), compare) instead. Either way, the operation has to be appropriately defined.

Because the built-in numeric types, along with the standard string and container types, define appropriate operations, C++ programmers can go a long time without having to know just what it takes to define such an operation. Over the next few weeks, I intend to discuss some of the subtleties involved in doing so.

Perhaps the most important aspect to remember about C++ order relations is that the parts of the library that expect them expect only a single relation. In other words, when you call sort, sort needs to know only how to look at two values a and b and answer the yes-or-no question: Should a precede b according to the given ordering? Asking this question is analogous to asking whether a<b, except that the operation need not be spelled as <. So, for example, when we call sort(v.begin(), v.end(), compare), we are saying that the function named compare will be used to say whether a precedes b.

Because sort's caller need supply only a single operation, the code inside sort itself never compares two elements directly for equality or inequality. Instead, any equality test comes about only as a consequence of calling <, or compare, or whatever its name might be.

At this point, I could continue by explaining the rules surrounding order relations. Instead of doing that, however, I'd like to take a step back and think about what properties an order relation needs to have in order to be useful for sorting.

The most important such property is that after a sequence has been sorted, the order of its elements must conform to the definition of <. In particular, if a precedes b in the sequence, then b<a must be false. By implication, a<a must be false for all values of a. Otherwise, it would be impossible to sort a two-element sequence both of whose elements had value a. We can describe this requirement by saying that < must be irreflexive.

For similar reasons, a<b and b< a must never both be true. Otherwise, it would be impossible to sort a two-element sequence with a and b as its two values. By implication, for any two values a and b, either a<b is true, b<a is true, or a<b and b<a are both false. We can describe this requirement by saying that < must be antisymmetric.

Whenever a<b is true, a will precede b in any ordering — that's the meaning of a<b. As a result, if a<b and b<c are both true, then a must precede b and b must precede c. As a result, a must precede c, from which we can infer that a<c ought to be true as well. Indeed, the C++ library requires this property: Whenever a<b and b<c are both true, a<c must be true as well. We can describe this requirement by saying that < must be transitive.

Let's abbreviate the state of affairs in which a<b and b<a are both false by writing a?b, which we might describe by saying that a and b are unordered. Note that for any a and b, exactly one of a<b, b<a, and a?b is true. We've already seen that a?a must be true for any value of a, and that whenever a?b is true, b?a is also true. In other words, unlike <, ? is both reflexive and symmetric. However, like <, ? must be transitive: If we don't care whether a precedes b, and we don't care whether b precedes c, it makes no sense to care whether a precedes c.

We can summarize these rules as follows:

• < must be irreflexive, antisymmetric, and transitive.
• If a<b and b<a are both false, we say that a and b are unordered.
• The unordered relation must be reflexive, symmetric, and transitive.

Any relation that is reflexive, symmetric, and transitive is called an equivalence relation. Elements that are related by an equivalence relation are not necessary equal, but they share some of the properties of equality.

Exercise:

     bool compare(int m, int n)
     {
           return abs(m) < abs(n);
     }
 

Does this function meet all of the requirements of an order relation? Why or why not?