A Simple Invariant
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
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
sort makes the invariant true again.
Another way to fulfill our responsibility is not to append
v, but rather to insert
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
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
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
insert). Next week, I'll talk about how we can use invariants such as this one to make our programs more reliable.