Introduction
I continue my overview of the Standard Template Library (or STL for short), a major component of the draft Standard C++ library. (See "Standard C/C++: The Standard Template Library," CUJ December 1995, and "Standard C/C++: STL Headers — An Overview," CUJ January 1996.) This month, I focus on the first of three major topics, iterators. The other two major topics are algorithms and containers, as I described last month.
Iterators are the glue that ties together all of STL. Essentially all of the algorithms supplied by the draft Standard C++ library are templates that you instantiate for particular iterators that you specify. You are encouraged to write your own algorithm templates in the same style. Similarly, all the containers in the library supply iterators that let you access the sequences they control. You are encouraged to supply suitable iterators for any containers you define. Since a common, garden variety object pointer can serve as practically any category of iterator, this is hardly an onerous constraint.
I count three headers as glue, in this sense: <utility>, <iterator>, and <memory>. Of these, the first is arguably more glue than iterator technology. But all three supply machinery used throughout STL. I outlined all the headers last month, so I won't summarize them again.
Instead, I focus on those properties shared by all iterators — how to categorize them and how each category behaves. If you want an introduction aimed at programmers less sophisticated in C and C++, I wrote a two-part overview recently in our sister publication, Embedded Systems Programming. (See "State of the Art: From Indexes to Iterators," ESP July 1995, and "State of the Art: A Taxonomy of Iterators," ESP August 1995.)
Output Iterators
To begin at the beginning, an iterator in C++ is a generalization of an object pointer in C. Pointers themselves make perfectly fine iterators, of course. The generalization comes from the ability to declare new classes in C++, and to overload many of the operators with new meanings for these classes.
You use an iterator to access the elements of an ordered sequence. "Access" is a general term that can mean either storing into an object or obtaining the stored value from an object. If all you want to do is create a new sequence by generating its values in order, you can write a loop like:
for (; <not done>; ++next)
*next = <whatever>;
Here, next is an object of some iterator type X, <not done> is the predicate that determines when the loop terminates, and <whatever> is an expression of the element type T.
An iterator of type X that can be used this way is called an output iterator. From the above, it is easy to see that an output iterator must define at least the following operations:
- *next = <whatever> assigns <whatever> to the next element to generate in the sequence.
- ++next alters next to designate the next element in the sequence.
A popular variant of this idiom in C uses slightly different notation:
while (<not done>)
*next++ = <whatever>;
To support this idiom, the expression *next++ = <whatever> must combine the two operations described immediately above, just as for pointers in C.
An output iterator promises little more than these properties. Rounding out the set of operations is a copy constructor, a destructor, and an assignment operator, all with the usual sensible properties. In trade for these weak properties, an output iterator permits a wide variation of implementations. You can even write output to a file in the guise of storing output records one at a time on a suitable output iterator.
Table 1 shows the semimathematical notation conventionally used to describe the properties of output iterators. Similar tables appear later for the other categories of iterators. I find this notation helpful as a supplement to the example code and commentary above, but I don't think it provides a complete replacement. The table doesn't make clear, for example, several important constraints on output iterators:
- You really must increment an output iterator after each store.
- You really shouldn't increment an output iterator more than once between stores.
If the output iterator is actually a pointer, these constraints aren't so obvious. But once you see the kind of clever tricks that STL plays with special-purpose output iterators, you will understand their need. You may also better appreciate some of the more esoteric entries in Table 1 (such as the return type of r++). For now, just remember that an output iterator is intended to be used only in one of the stylized loops I showed above.
Input Iterators
Output iterators are for generating new sequences. To access stored values in order from an existing sequence, you need a slightly different idiom:
for (p = first; p != last; ++p)
<process>(*p);
Here, p, first, and last are objects of some iterator type X, and <process> is a function that accepts an argument of the element type T. The sequence consist of the elements denoted by iterators in the half-open interval [first, last].
Note that last does not denote an element of the sequence. Rather, it is the first element beyond the end of the sequence. An empty sequence is one for which first == last. The C Standard blessed this idiom for walking arrays in C — you can store the address of the first element beyond an array in a pointer, but you can't dereference it. Iterators generalize this concept to a fare thee well.
An iterator of type X that can be used this way is called an input iterator. From the above, it is easy to see that an input iterator must define at least the following operations:
- p != q is true if the iterators p and q of type X do not denote the same element. (For convenience, p == q is also always defined, as the logical inverse of p != q.)
- *p is an rvalue of type T. The expression is not defined for p == last.
- ++p alters p to designate the next element in a sequence after the one it originally designated. The expression is not defined for p == last.
A popular variant of this idiom in C uses slightly different notation:
while (first != last)
<process>(*first++);
To support this idiom, the expression *first++ must combine the two operations described immediately above, just as for pointers in C.
From these properties, it is safe to conclude that [first, last) is a finite sequence only if last is reachable from first. Put another way, incrementing first a finite number of times must eventually yield a value that compares equal to last.
Like its cousin the output iterator, an input iterator promises little more than these properties. Again rounding out the set of operations is a copy constructor, a destructor, and an assignment operator, again with the usual sensible properties. The only other addition is the "points at" operator p->m, which is defined only when type T is a structured type. As you might guess, an input iterator also permits a wide variation of implementations. You can even read input from a file in the guise of accessing input records one at a time using a suitable input iterator.
Table 2 shows the semimathematical notation conventionally used to describe the properties of input iterators. Once again, the table doesn't make completely clear all the important constraints on input iterators. In fact, the C++ standards committees have recently indulged in rather heated debate over what properties an input iterator should properly have. I won't even try to reproduce the rather esoteric arguments. Rather, I encourage you to treat input iterators with the same caution I advised for output iterators. Use them only in one of the stylized loops I showed above.
Forward Iterators
Output and input iterators are particularly tricky, for the reasons I cited in passing. They can serve as interfaces to files of arbitrary length. A more conventional use of iterators, however, is to access sequences that are truly stored completely in memory. In such cases, you can use iterators that have rather less surprising properties.
Say, for example, that you are still content to access the elements of a sequence strictly from beginning to end. But you might want to both read and write the elements of the sequence. Or you might want to keep an occasional "bookmark" at some point you've visited earlier in the sequence. In such cases, you still use much the same control loops as I showed earlier for output and input iterators. You simply ask for iterators that behave a bit more like conventional pointers.
A forward iterator meets these requirements. As with input iterators, you can compare two forward iterators for equality or inequality. The two iterator values must, of course, inhabit the same domain of values, as before. And a forward iterator can also have a "singular value" that behaves for all the world like the address of an array element just "off the end." But a forward iterator can support either read-only or read/write access to the sequence. And you can have multiple active copies of a forward iterator pointing various places within the sequence.
You might think of a forward iterator as a pointer to an element of a singly linked list. You can tell when you're pointing off the end of a list. If not, you can access the list element, or advance the pointer to the next element in the sequence. But you can't back up, and you can't access an arbitrary element of the list. (Well, you can do so with some finagling, but you can't perform these operations in constant time, regardless of the length of the list.)
Table 3 shows the semimathematical notation conventionally used to describe the properties of forward iterators.
Bidirectional Iterators
The next useful generalization of iterators, beyond forward iterators, is to permit both incrementing and decrementing. Quite a number of algorithms are much more efficiently implemented with just this extra bit of latitude. So STL defined a bidirectional iterator as a forward iterator that you can also run backwards through a sequence.
You might think of a bidirectional iterator as a pointer to an element of a doubly linked list. You can tell when you're pointing off the end of a list. If not, you can access the list element, or advance the pointer to the next element in the sequence, or back up the pointer to the previous element in the sequence. But you can't access an arbitrary element of the list, at least not with a constant-time operation.
Table 4 shows the semimathematical notation conventionally used to describe the additional properties of bidirectional iterators. All the properties of forward iterators apply as well.
Random-Access Iterators
The final step in generalizing iterators takes us to the full power of object pointers in C. A random-access iterator supports the addition and subtraction of integer values, pointer subtraction, and subscripting — as well as all the operations permitted for bidirectional iterators, of course. Some algorithms simply require this degree of flexibility to perform at all well. (Sorting and fast searching by binary chop are two obvious examples.)
Remember, however, that a random-access iterator is still not necessarily a C-style pointer. The difference of two such iterators, for example, is some type Dist, which may or may not be one of the basic integer types. You should be able to perform integer arithmetic with Dist objects, of course, but nothing prevents these creatures from being classes in their own right.
Table 5 shows the semimathematical notation conventionally used to describe the additional properties of random-access iterators. All the properties of bidirectional iterators apply as well.
Iterator Categories
By now, the hierarchy of iterator categories should be fairly apparent. Nevertheless, I'll summarize by showing three sequences. For write-only access to a sequence, you can use any of:
output iterator ->
forward iterator ->
bidirectional iterator ->
random-access iterator</pre
>
<P>
The right arrow means "can be
replaced by." So any algorithm that calls for an output
iterator should work nicely with a forward iterator, for
example (but not the other way around).</P>
<P>
For read-only access to a sequence,
you can use any of:</P>
<pre>input iterator ->
forward iterator ->
bidirectional iterator ->
random-access iterator
An input iterator is the weakest of all categories, in this case.
Finally, for read/write access to a sequence, you can use any of:
forward iterator -> bidirectional iterator -> random-access iterator
Remember that an object pointer can always serve as a random-access iterator. Hence, it can serve as any category of iterator, so long as it supports the proper read/write access to the sequence it designates.
This "algebra" of iterators is fundamental to practically everything else in the Standard Template Library. It is important to understand the promises, and limitations, of each iterator category to see how iterators are used by containers and algorithms in STL. o
P.J. Plauger is senior editor of C/C++ Users Journal. He is convener of the ISO C standards committee, WG14, and active on the C++ committee, WG21. His latest books are The Draft Standard C++ Library, and Programming on Purpose (three volumes), all published by Prentice-Hall.You can reach him at [email protected].
