Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

How Not To Compare Aggregates

June 22, 2011

Last week and the week before, I showed a common example of an incorrect comparison function for pairs:

struct Point { int x, y; };
bool compare(const Point& p, const Point& q)
{
   return p.x < q.x && p.y < q.y;
}

and said that I would explain what is wrong with it. I also said that I would explain why the notion of approximate equality causes problems with sorting.

Both of these examples cause trouble for the same two fundamental reasons:

  1. When you define an ordering relation for sorting purposes, that relation implicitly defines a notion of "unordered" that covers the case where compare(a, b) and compare(b, a) are both false.
  2. This notion of "unordered" has to be an equivalence relation in order for sorting to work correctly.

With these reasons in mind, let's look first at approximate equality. Tempting though the notion might be, as soon as you decide to consider "equal" any two values that are closer than a given threshold, you get into trouble. The trouble occurs when a and b are close enough together to be considered equal, but just barely so, and b and c are also close enough to be considered equal, but also just barely so. In that case, it should be easy to imagine that even though a is "equal" to b and b is "equal" to c, a and c are not equal.

Such circumstances cause sorting to fail, and as a result, even if you decide to use approximate equality under other circumstances, you must not do so for sorting purposes.

Now let's look at our compare function. On the surface, it makes sense to say that a point is "less than" another point if both of its corresponding coordinates are less than those in the other point. However, consider what that rule does to the notion of "unordered:" It says that two points are unordered whenever their coordinates compare in opposite directions.

In other words, if p.x ≤ q.x and p.y ≥ q.y, or if p.x ≥ q.x and p.y ≤ q.y, the two points are "unordered." With this definition, it is not hard to find three points p, q, and r such that p and q are unordered, q and r are unordered, but p and r are ordered. For example, (0, 0) is unordered with both (0, n) and (n, 0) for any value of n ≥ 0, but it is "less than" (m, n) whenever both m > 0 and n > 0. Therefore, (0, 0) is unordered with both (0, 1), which is unordered with (1, 1), but (0, 0) is "less than" (1, 1).

One way of avoiding trouble when you try to define an order relation for sorting is to start by asking what "unordered" means as a concept, in the context of the data structure that you are trying to sort. It can be useful to think of this notion as a funny way of spelling "equal." For example, when we are sorting character strings, we often think of strings that differ only by whether letters are upper- or lower-case as "equal." Similarly, when we set out to sort pairs of numbers, we should start by thinking about what notion of "equality" we want to use when we are sorting.

One reader suggested an interesting possibility: We could sort numbers based on how far they are from a given point, such as (0, 0). This idea would lead to the following comparison function:

bool compare(const Point& p, const Point& q)
{
   return (p.x*p.x + p.y*p.y) < (q.x*q.x + q.y*q.y);
}

This comparison function treats all points the same distance from (0, 0) as being "equal." In effect, it does not distinguish at all between the points on any circle centered on (0, 0), and sorts all points based on the size of the circle that includes each point.

Many readers will consider this notion of sorting points to be rather weird, but at least it meets the requirements — something that the version we presented at the beginning of this not does not do. Another common solution to this problem is to compare points in "dictionary order:"

bool compare(const Point& p, const Point& q)
{
   return p.x < q.x || (p.x == q.x && p.y < q.y);
}

We can rewrite this function so that it does not need to use == at all:

bool compare(const Point& p, const Point& q)
{
   return p.x < q.x || (!(q.x < p.x) && p.y < q.y);
}

This rewrite relies on the fact that one of p.x < q.x, p.x == q.x, or q.x < p.x will always be true, so that if p.x < q.x and q.x < p.x are both ruled out, only p.x == q.x remains.

Written in this form, this function lets us generalize from < on a single pair of elements to < on multiple pairs of elements, and does so in a way that does not require us to define > or =.

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