Last week, I noted that if you have an object with two components, each of which you know how to order independently, it requires at least a little thought to figure out how to do so. Moreover, there is a commonly used strategy, often called lexicographical order or dictionary order, for taking the ordering strategies for individual components and combining them.

The C++ library is considerate enough to implement dictionary ordering for its users in (at least) three places. The first is the std::pair template, which defines the six comparison operators in terms of the corresponding operators of the pair's components. Specifically,

 
pair(x1, y1) < pair(x2, y2) is defined as x1<x2 || (!(x2 < x1) && y2 < y1)

Note that this definition is careful to use only < on components, not > or ==. Part of its technique for doing so rests on the fact that the comparison x2 < x1 can take place only when it has already been established that x1<x2 is false, so that !(x2 < x1) is really a clever way of saying x2 == x1 without using == or !=.

Analogously,

 
pair(x1, y1) == pair(x2, y2) is defined as x1 == x2 && y1 == y2

This definition is careful to use only == to define == on pairs.

You might think that the other four comparison operators would be defined in terms of the corresponding operators on the component, but you would be wrong. Instead,

 
pair(x1, y1) > pair(x2, y2) is defined as pair(x2, y2) < pair(x1, y1)
pair(x1, y1) !=  pair(x2, y2) is defined as !(pair(x1, y1) == pair(x2, y2))
pair(x1, y1) <= pair(x2, y2) is defined as !(pair(x1, y1) > pair(x2, y2))
pair(x1, y1) >= pair(x2, y2) is defined as !(pair(x1, y1)< pair(x2, y2))

The underlying principles are easy to understand once explained:

• The pair template never depends on more than the == and < operations on the components.
• Order relations are defined entirely in terms of other order relations.
• Equality relations are defined entirely in terms of other equality relations.
• If the element types have relations defined that meet the library requirements, then the resulting relations on pairs will also meet the library requirements.

As a generalization of pair, the library tuple template also implements the six comparison operators in terms of < and == on the tuple's elements. Like pair, tuple does not reply on the other four comparison operators on elements.

The third place where the library implements dictionary order is in the lexicographical_compare algorithm. This algorithm accepts two pairs of iterators, each of which defines a range of elements, and uses an extended version of this comparison procedure to compare the sequences:

• If both sequences have the same length and every element is equal to the corresponding element of the other sequence, the two sequences are considered equal. This case holds even if both sequences are empty.
• If one sequence is a prefix of the other, the shorter sequence is considered less than the other.
• Otherwise, the result of the comparison is the result of comparing the elements that make up the first discrepancy between the sequences.

This function offers an easy way to define sequence comparison in terms of element comparison when all the elements have the same type.

Unless there is a good reason to do otherwise, one's first thought about how to define comparison between two data structures should probably be to compare the data structure's elements along the lines that we've been discussing. The main mistake that beginners make is to believe that it is possible to define pair(x1, y1) < pair(x2, y2) as something such as x1 < x2 && y1 < y2, which doesn't work.

There is another pitfall in defining comparison relations: Sometimes the obvious way of comparing individual elements doesn't always work. We'll look at some examples of that pitfall next week.