Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

A Simple Invariant

October 24, 2012

Last week, I said that I would discuss how to use class invariants and data-structure audits to make software more reliable. I'll start with invariants.

An invariant is a claim about a program that we expect to be true at specific points during the program's execution. With each invariant comes the benefit that code can assume that the invariant is true, and the responsibility that code must never cause the invariant to become false at any point at which it is expected to be true.

Programmers often use invariants without realizing it. For example, consider this comment

// At this point, the vector v is sorted.

If the comment is correct, it is describing an invariant: Every time control passes through the comment, the elements of v are in sequence. Accordingly, the invariant's benefit is that, for example, it is safe to use a binary search on v. The invariant's responsibility is that code that changes the value of v's elements must then put those elements back in sequence before the next time the program reaches this comment.

For example, if we execute a statement such as


we have probably broken the invariant (unless n happens to have a value that keeps v in order). Accordingly, we have the responsibility of putting v back into order before the next point in the program at which the invariant is expected to be true.

One way of fulfilling this responsibility is to sort v after we've inserted n:

               sort(v.begin(), v.end());

Once we have done so, v's is once again in order, so the invariant is valid. Of course, sorting can take a while, but this approach might sense if we were putting many new elements into v instead of just one. The first call to push_back makes the invariant false, but once we're done appending elements to v, calling sort makes the invariant true again.

Another way to fulfill our responsibility is not to append n to v, but rather to insert n into v at a point that maintains v's ordering. When we do this insertion, we can take advantage of the invariant. For example, we might write code such as

               v.insert(upper_bound(v.begin(), v.end(), n), n);

The call to upper_bound does a binary search in v (i.e., in the range starting at v.begin() and ending just before v.end()). It returns an iterator that refers to the first element that is strictly greater than n, or an off-the-end iterator if no such element exists. The call to insert places a copy of n immediately before the position to which the result of upper_bound refers. In effect, the call to insert inserts a copy of n at the last position in v at which it is possible to do so while preserving v's sequence. We note in passing that if we had called lower_bound instead of upper_bound, v's sequence would still be preserved, and the copy of n would have been inserted at the first position at which it was possible to do so. These two positions are usually identical, but not if v contains multiple elements with values equal to n.

These examples are typical of how programmers can use invariants to help think about their programs. The main idea is to ensure that the invariant is true whenever it is supposed to be true, and we can do that either by causing it to be true (by calling sort) or by arranging that it never becomes false (by using upper_bound and insert). Next week, I'll talk about how we can use invariants such as this one to make our programs more reliable.

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.