Columns

Standard C/C++

P. J. Plauger

The Header <iterator>, Part 2

As you progress in C++, you'll naturally want to use iterators, and even create your own. The header <iterator> provides excellent models for you to imitate and elaborate upon.

Introduction

Last month, I introduced the header <iterator>. It supplies considerable machinery for manipulating iterators within the Standard Template Library (or STL). So far, I have shown the template functions:


iterator_category
value_type
distance_type
advance
distance

along with the classes that they work with. The algorithms in STL make extensive use of these template functions to gloss over differences among the five categories of iterators. By suitably overloading on each of these template functions, STL can generate the best tailored C++ code for the actual iterators you use in your code.

I continue this month with the remainder of the header <iterator>. What's left are a number of iterators, in the form of template classes, and a handful of template functions that go with them.

Reverse Iterators

A reverse iterator, as its name implies, steps backward through a sequence when you step the iterator forward. Equally, it steps forward through a sequence when you step the iterator backward. It is a handy tool when you find it useful to sometimes operate on a sequence in reverse order — no need to actually reverse the sequence, then reverse it again later, just to perform the backward operation.

Listing 1 shows the chunk of header <iterator> that defines the template class reverse_iterator and its related template operators. It is a random-access iterator. The template class has a whole slew of type parameters:

So you might define:


typedef random_iterator<char *,
    char, char&, char*, ptrdiff_t>
Revptr;

to define an iterator type Revptr that walks backward through an array of char.

I discussed the relationship between RanIt, T, and Dist last month. The template function value_type helps you determine T for an iterator, while the template function distance_type helps you determine Dist. Sadly, the tricks that these template functions use don't quite meet the needs of default values for template type parameters. You have to spell them out when you specialize the template class reverse_iterator.

Less obvious are the template parameters Ref and Ptr. You'd think that Ref should always be T& and Ptr should always be T *. That's almost true, but not exactly. STL permits remarkable latitude in how you store the elements of a sequence. I'll get into that topic in more detail next month, when I present the header <memory>. For now, just know that the default parameter values shown usually do the job, unless you're being very tricky in how you implement RanIt.

The template class stores just one object, the underlying iterator of class RanIt. Anyone can obtain the value of this object by calling the member function base(). A class derived from reverse_iterator can access it as the protected object current. None of the remaining code is particularly tricky once you understand the essential design principle behind reverse iterators. It is captured in the member function operator*():


Ref operator*() const
    {return (*(current - 1)); }


Put simply, a reverse iterator returns the element just before the one designated by current. The reason why is simple, once you think about it. You typically designate a sequence by the range of iterators [first, last). The half-open interval notation means that first is part of a non-empty sequence but last is just past the end.

You designate a range of reverse iterators by the range of current values [last, first). For last to work as the value stored in current, it has to designate the element at current - 1 in a non-empty sequence. Once you make this shift, all the other properties of iterators follow pretty naturally.

The template class reverse_iterator is an excellent prototype for any random-access iterator class you choose to develop. It supplies all the needed member functions. It is also accompanied, in Listing 1, by all the template operators you need to define as well. You will see more of this particular iterator when we discuss the container template classes vector and deque.

Of course, you can also run a bidirectional iterator backward. Listing 2 shows the chunk of header <iterator> that defines the template class reverse_bidirectional_iterator and its related template operator. It is a bidirectional iterator, naturally enough. That's why its first parameter is called BidIt, as an aide memoire. Its parameters are otherwise the same as for template class reverse_iterator.

Once again, the template class reverse_bidirectional_iterator is an excellent prototype for any bidirectional iterator class you choose to develop. You will see it again when we discuss the container template classes list, map, multimap, set, and multiset.

Insertion Iterators

You often have occasion to generate a sequence of elements in one pass from beginning to end. An output iterator is the ideal agent for disposing of the generated elements. It has the weakest semantic requirements of any of the iterator categories that let you write a sequence. Those weak requirements permit considerable latitude in writing output iterators.

Say, for example, you want to insert the generated sequence in some container object C of type Cont. The container template classes defined in STL have a number of uniform properties you can exploit. In particular:

Of course, nothing prevents you from defining your own containers that follow these rules. On the contrary STL encourages you to follow its models so that your additions integrate well with the rest of STL.

Listing 3 shows the chunk of <iterator> that defines several template classes:

Each of these template classes stores a reference to the container object, with the protected name container. The last one also stores the insertion point in an object with the protected name iter.

On the face of it, the member operator definitions in each of these template classes are outrageous. They do not supply the semantics normally associated with their operators. Remember, however, that an output iterator next is meant to be used in just one or two stylized ways:


for (; <not done>; ++next)
    *next = <whatever>;

or:


while (<not done>)
    *next++ = <whatever>;


Walk through these template class definitions for the two stylized loops above. You will see that they supply the absolute minimum functionality needed to behave like output iterators. Thus, they serve as good models for any output iterators you might choose to write.

Listing 3 also defines three template functions:

These provide a handy way to concoct insertion iterators on the fly.

Stream Iterators

If you can deliver a generated sequence to a container, using some clever form of output iterator, you should certainly be able to insert it into an output stream, using some other clever form. Equally, you should be able to obtain a sequence of elements from an input stream, using some clever form of input iterator. Indeed, that is the case.

Say you have elements of type T for which are defined a stream extractor:


istream& operator>>(istream&, T&);


That's all you need to read characters from an input stream such as cin, convert them to a value of type T, and store the value in an object X, just by writing:


cin >> X;


The template class istream_iterator<T, Dist> does this for you, in the guise of obtaining an element from a sequence using an input iterator. If you write:


typedef istream_iterator<int, ptrdiff_t>
    Int_init;
Int_init int_in(cin);

then the expression *int_in++ extracts an int from cin and delivers it as the value of the expression.

You should, of course, first test that such a value is available in the input stream. The proper way to do so is to compare int_it for equality with the singular value that signals end of file. (See "Standard C/C++: Iterators," CUJ, February 1996.) The default constructor always yields an object with this singular value. Thus, you can write:


Int_init first(cin), last;

and proceed to extract elements from a stream until you reach end of file, by writing either the stylized loop:


for (p= first; p != last; ++p)
    <process>(*p);

or its variant:


while (first != last)
    <process>(*first++);


Listing 4 shows the chunk of <iterator> that defines the template class istream_iterator and its equality operator. You should once again study how its bizarre member operators work in the stylized loops above to deliver proper behavior for an input iterator. Note that such an iterator object has to squirrel away a "lookahead" value, of type T, to meet all its semantic requirements.

Listing 4 also defines the template class ostream_iterator<T>. It defines an output iterator for inserting elements into an output stream. Say you have elements of type T for which are defined a stream inserter:

ostream&operator<<(ostream&,T);


That's all you need to convert a value of type T to a character sequence and write the sequence to an output stream such as cout, just by writing:

cout << X;


The template class ostream_iterator<T> does this for you, in the guise of storing a generated element into a sequence using an output iterator. If you write:


typedef ostream_iterator<int>
    Int_outit;
Int_outit int_out(cout);

then the expression *int_out++ = X inserts the int value X into cout. Even better, the declaration:


Int_outit int_out(cout, " ");

appends a space to each inserted value, so they don't all run together.

Stream Buffer Iterators

A late addition to STL is a pair of iterators for inserting and extracting elements of type E (typically of type char) directly to and from a stream buffer. The template class basic_streambuf<E, T> defines the stream-buffer objects that mediate transfers between an actual stream, such as a file, and computer memory. It is a templatized version of the older iostreams class streambuf, which performs a function analogous to the Standard C library type FILE. Here, T stands for a "traits" class, which supplies assorted information about the element type E.

I won't delve into all the intricacies of iostreams as it has been standardized. Suffice it to say that the template class istreambuf_iterator<E, T> plays a crucial role in this new machinery. Every character read from an input stream is obtained through the intermediary of an input iterator of this type. Similarly, every character written to an output stream is delivered through the intermediary of an output iterator of type ostreambuf_iterator<E, T>.

Listing 5 shows the last chunk of the header <iterator>. It defines these two template classes and an accompanying template operator. Compare these definitions closely with those in Listing 4 — they are highly parallel. The major difference is that istreambuf_iterator endeavors to perform "lazy input." It defers actually obtaining an element from the input stream until it is actually needed. Otherwise, the two sets of classes are more alike than different.

Conclusion

The machinery defined in the header <iterator> is used throughout STL. You should cultivate enough familiarity with it to use it comfortably. It is hard to write good algorithms without leaning heavily on iterator_category and the other utilitarian template functions I covered last month. It is amazing how often the insertion iterators come in handy when you muck about with containers. And if you perform truly serious work with iostreams, you can't avoid working with the stream-buffer iterators at the very least.

But this header has an equally important use, as I emphasize one last time. Of the five categories of iterators, only forward iterators have no prototype defined within this header. All the others have excellent models for you to imitate and elaborate upon. Use them.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. He developed Lib Suite ++, the Plum-Hall validation suite for the Standard C++ library. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at pjp@plauger.com.