# A Strategy for Defining Order Relations

February 01, 2013

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>