Last week , I proposed a comparison function for pairs of integers and asked whether it met the requirements for C++ order relations:

 
struct Thing { int a, b; };


bool compare(const Thing& t1, const Thing& t2)
{
return t1.a < t2.a && t1.b < t2.b;
}

As one reader was kind enough to point out, it doesn't work because it's not transitive:

For example, with three objects, t1(a1, b1), t2(a2, b2), and t3(a3,b3), a1 < a2, b1 > b2; a1 < a3, b1 > b3; a2 < a3, b2 < b3. Then, t1 and t2 are unordered, t1 and t3 are unordered, but t2 < t3.

This reader proposed an interesting alternative:

 
bool compare(const Thing& t1, const Thing& t2)
{
     return (t1.a * t1.a + t1.b * t1.b) <
            (t2.a * t2.a + t2.b * t2.b);
}

In effect, this comparison function is a generalization of the one I proposed two weeks ago :

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

Both of these functions implement a notion of magnitude, which we can think of as the distance between a given value and a zero point. In two dimensions, the distance between a point with coordinates (x, y) and zero is the square root of x2 + y2. The two-dimensional version of the comparison function compares the sums of the squares directly instead of comparing their square roots.

Both of these functions are flawed because their computations might overflow. Aside from those flaws, however, these functions implement a generally useful strategy for defining order relations: If you want to compare two complicated objects, the strategy is to define a function that computes a single number from each object and then compares those numbers.

As long as equal objects yield equal numbers, this strategy clearly results in a valid order relation, because it is defined in terms of comparing numbers. However, there is no guarantee that the resulting order relation will be useful or even comprehensible. For example, the mapping from objects to numbers might be a cryptographic hash. In that case, the ordering would be somewhere between very difficult and impossible to understand. It would still be a valid ordering, but understanding it would be as hard as cracking the hash code.

For an order relation based on a mapping to numbers to be intuitively useful, then, the number that comes from each object needs to be related to the object in a useful way. For that matter, we don't even need to use numbers; what we need is a strategy for finding a useful mapping.

One such strategy might be to take each element of an object that is being compared, convert it somehow to a string, and concatenate all those strings to obtain a single string that describes the entire object. Comparing objects then turns into comparing strings.

This observation suggests that there is a natural connection between comparing objects with multiple components and comparing strings. That connection leads us to the notion of dictionary order, which we will describe next week.