Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Introducing C++ Order Relations

January 18, 2013

The C++ library facilities for sorting, binary searching, and ordered containers work only on types with appropriate order relations defined on them. For example, if v has type vector<T>, and we wish to call sort(v.begin(), v.end()), the call will work properly only if T has an appropriately defined operator<. If there is an appropriate operation with a different name, such as compare, we could call sort(v.begin(), v.end(), compare) instead. Either way, the operation has to be appropriately defined.

Because the built-in numeric types, along with the standard string and container types, define appropriate operations, C++ programmers can go a long time without having to know just what it takes to define such an operation. Over the next few weeks, I intend to discuss some of the subtleties involved in doing so.

Perhaps the most important aspect to remember about C++ order relations is that the parts of the library that expect them expect only a single relation. In other words, when you call sort, sort needs to know only how to look at two values a and b and answer the yes-or-no question: Should a precede b according to the given ordering? Asking this question is analogous to asking whether a<b, except that the operation need not be spelled as <. So, for example, when we call sort(v.begin(), v.end(), compare), we are saying that the function named compare will be used to say whether a precedes b.

Because sort's caller need supply only a single operation, the code inside sort itself never compares two elements directly for equality or inequality. Instead, any equality test comes about only as a consequence of calling <, or compare, or whatever its name might be.

At this point, I could continue by explaining the rules surrounding order relations. Instead of doing that, however, I'd like to take a step back and think about what properties an order relation needs to have in order to be useful for sorting.

The most important such property is that after a sequence has been sorted, the order of its elements must conform to the definition of <. In particular, if a precedes b in the sequence, then b<a must be false. By implication, a<a must be false for all values of a. Otherwise, it would be impossible to sort a two-element sequence both of whose elements had value a. We can describe this requirement by saying that < must be irreflexive.

For similar reasons, a<b and b< a must never both be true. Otherwise, it would be impossible to sort a two-element sequence with a and b as its two values. By implication, for any two values a and b, either a<b is true, b<a is true, or a<b and b<a are both false. We can describe this requirement by saying that < must be antisymmetric.

Whenever a<b is true, a will precede b in any ordering — that's the meaning of a<b. As a result, if a<b and b<c are both true, then a must precede b and b must precede c. As a result, a must precede c, from which we can infer that a<c ought to be true as well. Indeed, the C++ library requires this property: Whenever a<b and b<c are both true, a<c must be true as well. We can describe this requirement by saying that < must be transitive.

Let's abbreviate the state of affairs in which a<b and b<a are both false by writing a?b, which we might describe by saying that a and b are unordered. Note that for any a and b, exactly one of a<b, b<a, and a?b is true. We've already seen that a?a must be true for any value of a, and that whenever a?b is true, b?a is also true. In other words, unlike <, ? is both reflexive and symmetric. However, like <, ? must be transitive: If we don't care whether a precedes b, and we don't care whether b precedes c, it makes no sense to care whether a precedes c.

We can summarize these rules as follows:

  • < must be irreflexive, antisymmetric, and transitive.
  • If a<b and b<a are both false, we say that a and b are unordered.
  • The unordered relation must be reflexive, symmetric, and transitive.

Any relation that is reflexive, symmetric, and transitive is called an equivalence relation. Elements that are related by an equivalence relation are not necessary equal, but they share some of the properties of equality.

Exercise:

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

Does this function meet all of the requirements of an order relation? Why or why not?

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.
 


Dr. Dobb's TV