Introduction
If you ask most programmers to write a loop that writes the values 0, 1, 2, and so on through n-1, on the standard output, you will probably see something like this:
// Example 1
for (int i = 0; i < n; ++i)
std::cout << i << std::endl;
where ++i might appear, equivalently, as i++. If you ask for a loop
that writes the same values in the opposite sequence, you will probably see something
like this:
// Example 2
for (int i = n-1; i >= 0; --i)
std::cout << i << std::endl;
These loops are nicely related and solve their respective problems in obvious,
straightforward ways.
Nevertheless, in recent years, we have been changing our style so that we can write loops in a form that works not only for integers such as i and n in these two examples, but also for unsigned integers and iterators. As one example of this stylistic change, in Accelerated C++, we made a point of using != instead of < to terminate loops, which means that we would solve our first problem this way:
// Example 3
for (int i = 0; i != n; ++i)
std::cout << i << std::endl;
even though we expect many readers to find that usage unfamiliar.
We use this style even though it courts disaster if we try to count downward:
// Can you find the error before you
// read on?
for (int i = n-1; i != 0; --i)
std::cout << i << std::endl;
The problem here, of course, is that if n is zero before the loop starts,
the first value of i will be -1, so the program will never terminate.
We avoid such disasters by counting downward in a completely different style:
// Example 4a
int i = n;
while (i != 0) {
--i;
std::cout << i << std::endl;
}
or, alternatively:
// Example 4b
for (int i = n; i != 0; ) {
--i;
std::cout << i << std::endl;
}
One reason to use the same form of loop for different types is to avoid having
to remember which kind of loop to use for which type. Unsigned integers, of course,
are never negative, which means that we must be especially careful when we use
them in loops that count down to zero. Iterators always support == and
!= comparisons, but they do not always support <, >,
<=, or >=, which means that if we wish to cater to iterators,
we must restrict ourselves to equality and inequality comparisons.
The rest of this article will explain in greater detail the consequences of our desire for generality, by examining various ways of writing values on the standard output stream. We will leave it to our readers to generalize the bodies of our loops to encompass other computations.
Unsigned Values
It is easy to forget that C++ has both signed and unsigned integers, because many programs do not use unsigned integers explicitly. Nevertheless, unsigned integers are important for expressing sizes. One reason is that by foregoing the possibility of negative values, unsigned integers can express a larger range of positive values than can plain integers. Accordingly, on some C++ implementations, it is possible to create an object that is so large that its size will not fit in a plain integer, but will nevertheless fit in an unsigned integer. For this reason, both the C and C++ standards say that the sizeof operator returns an unsigned type, and C++ programs often use unsigned quantities to express sizes.
Our first generalization, then, will be to allow for the possibility that i and n might be unsigned. In that case, we can see that Example 2 stops working:
// Example 2 with unsigned values
// This code no longer works
for (unsigned i = n-1; i >= 0; --i)
std::cout << i << std::endl;
The problem, of course, is that i >= 0 is always true if i is
unsigned, so the loop will never terminate. Moreover, if n is zero, the
value of n - 1 will underflow, which again is hardly what we want.
Of course, it is obvious in this example that i is unsigned, so it is almost as obvious that the comparison i >= 0 is a mistake. In practice, unsigned values sometimes appear in subtler contexts. For example, suppose that v has type std::vector<int>, and we want to write the elements of v on the standard output stream in reverse order. We might be tempted to do so this way:
// This code doesn't work either.
// Do you see why?
for (std::vector<int>::size_type i =
v.size()-1; i >= 0; --v)
std::cout << v[i] << std::endl;
Like the previous example, this loop will fail because i is unsigned. This
time, however, the fact that i is unsigned is not evident from the code
-- in order to see the problem, you have to know that the standard containers'
size_type members represent unsigned types.
The lesson here is that if we might be using unsigned integers, we must avoid any computation that might create or require a negative value. Therefore, we must always verify that i is strictly positive before we decrement it, and we must not compute n - 1 unless we know that n is not zero.
How can we rewrite our loop under these constraints? We know that the loop must do three things:
We must begin by initializing i, because otherwise i doesn't have a meaningful value. Moreover, because n might be zero, we cannot yet compute n - 1, so we have little choice but to have verified that i is not zero.
The resulting loop looks like our Example 4, except that i is unsigned:
// This version works
unsigned i = n;
while (i != 0) {
--i;
std::cout << i << std::endl;
}
In other words, if we wish to write a loop that counts downward, and we want
it to work with unsigned values, we should write a loop that looks like Example
4a or the equivalent 4b, rather than one like Example 2.
Of course, most loops count upward, not downward, and for such loops, even with unsigned integers, we don't have a reason yet to prefer != to <. In particular, Example 1 works just fine with unsigned values even though it uses < instead of !=. To see why we prefer Example 3 to Example 1, we have to generalize our loop to deal with iterators rather than with integers.
Iterators
Let's change our original problem: instead of writing a sequence of consecutive integers on the standard output stream, we wish to write each element of an object named x, which has type std::list<int>. If we try to adapt our Example 1 to solve this problem, we run into trouble:
// This code doesn't work
for (std::list<int>::iterator i =
x.begin(); i < x.end(); ++i)
std::cout << *i << std::endl;
The difficulty is that the std::list class does not offer random-access
iterators. Rather, it offers only bidirectional iterators, which support ==
and != but not <, >, <=, or >=.
Accordingly, we must write i != x.end() rather than i < x.end(),
giving us a loop that looks like this:
// This version works
for (std::list<int>::iterator i =
x.begin(); i != x.end(); ++i)
std::cout << *i << std::endl;
Note that this loop has the same form as our original Example 3:
// Example 3, repeated for convenience
for (int i = 0; i != n; ++i)
std::cout << i << std::endl;
We can see the resemblance by changing i's type from int to std::list<int>::iterator,
the initial value 0 to x.begin(), the upper bound n to
x.end(), and by writing *i instead of i. These substitutions
change only types and values; they do not change the overall form of the loop.
Let us now turn our attention to counting backward. If we wish to generalize backward-counting loops to encompass iterators, not only must we avoid order comparisons such as <, but we must also not try to compute iterator values that refer to a point before the beginning of a container.
For any standard-library container, it is possible to form an iterator that refers to any element of the container. It is also possible to form an iterator that refers to a position immediately after the last element of the container -- in fact, the end member yields just such an iterator. However, there is no guarantee of being able to form an iterator that refers to a position immediately before the first element. For example:
// Create an object of type std::list with one element // x starts out empty std::list<int> x; x.push_back(42); // x now has one element // Create two iterators that refer to // that element // p refers to x's element std::list<int>::iterator p = x.begin(); // So does q std::list<int>::iterator q = p; // Increment one iterator; decrement the other // p now refers to a position just past // the end of x ++p; // This assertion will succeed. assert(p == x.end()); --q; // Undefined behavior!We made both iterators, p and q, refer to the only element of x. If we now increment p, it refers to a position just past the end of x. If we decrement q, the resulting behavior is undefined, because the C++ library defines only an off-the-end iterator, not an off-the-beginning iterator.
This situation is similar to what saw with unsigned integers: if we want to deal with the range from 0 up to and not including n, we can compute the value that is just after the end of the range (namely n), but we cannot compute the value that is just before the beginning of the range (namely -1).
We infer that to write a loop that uses iterators to count backward, we should use the same technique that we used for unsigned integers, namely Examples 4a and 4b:
// Example 4a with iterator values
std::list<int>::iterator i = x.end();
while (i != x.begin()) {
--i;
std::cout << *i << std::endl;
}
// Example 4b with iterator values
for (std::list<int>::iterator i = x.end();
i != x.begin(); ) {
--i;
std::cout << *i << std::endl;
}
We can use either of these forms to count backward through signed or unsigned
integers and also through random-access or bidirectional iterators.
Conclusion
One of the most common everyday programming tasks is doing something to every element in a range, typically a range of integers or container elements. The most common way of iterating through a range of integers:
for (int i = 0; i < n; ++i)
std::cout << i << std::endl;
does not generalize to elements of containers that support only forward or bidirectional
iterators. However, by changing < to !=, we obtain a single
form that supports both integers and iterators.
The situation is more problematic for backward iteration. Here, the common form:
for (int i = n-1; i >= 0; --i)
std::cout << i << std::endl;
does not even support unsigned integers, let alone iterators. However, by writing
this loop as:
int i = n;
while (i != 0) {
--i;
std::cout << i << std::endl;
}
or, alternatively:
for (int i = n; i != 0; ) {
--i;
std::cout << i << std::endl;
}
we obtain a form that works not only for signed and unsigned integers, but also
for bidirectional or random-access iterators [1].
When there are several ways of writing a particular computation, we believe it is useful to keep an eye out for forms that work with multiple types and to get into the habit of using them instead of forms that work only with specific types.
Note
[1] Note that we said bidirectional iterators, not forward iterators. We can't use forward iterators to iterate backward, so we won't try.
About the Authors
Andrew Koenig is a member of the Communication Software Research Department at AT&T's Shannon Laboratory, and the Project Editor of the C++ standards committee. A programmer for more than 30 years, 15 of them in C++, he has published more than 150 articles about C++ and speaks on the topic worldwide. He is the author of C Traps and Pitfalls and co-author of Ruminations on C++ and Accelerated C++.
Barbara E. Moo is an independent consultant with 20 years' experience in the software field. During her nearly 15 years at AT&T, she worked on one of the first commercial projects ever written in C++, managed the company's first C++ compiler project, and directed the development of AT&T's award-winning WorldNet Internet service business. She is co-author of Ruminations on C++ and Accelerated C++ and lectures worldwide.
