Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video