Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Concrete Examples of Orderings

February 15, 2013

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.

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.
 

Comments:



Video