# Introducing C++ Order Relations

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?