13.2 ITERATORS REVISITED

In Chapter 5, we provided a usage perspective on the primary container classes of the C++ Standard Library. The goal of this section is to provide further insights into the iterators used for STL containers. Iterators are supported by all the sequence and associative container classes.

As was mentioned earlier, iterators are a generalization of pointers. An iterator is to a container class what a pointer is to an array. However, there is one important respect in which an iterator is different from a pointer: An iterator cannot be given null initialization. In other words, an iterator cannot be set to, say, 0 in order to point to nothing. All container classes that support iterators also support special functions begin(),end(),rbegin(), and rend() that can be invoked for initializing an iterator and for testing its value against the beginning or the end of a sequence.

As the reader already knows from Chapter 5, one of the useful features of the Standard Template Library is the availability of the generic algorithms for all kinds of processing associated with the container elements. These algorithms are generic in the sense that they can be invoked in a container-independent manner. The algorithms take iterator arguments and they don't care what specific container an iterator is defined for.

13.2.1 Iterator Categories for Generic Algorithms

Again as mentioned already in Chapter 5, the different algorithms of the generic library run the gamut from performing simple tasks like searching for a specific element in a container to more complex tasks like sorting, merging, and so on. It obviously makes sense that if the algorithms are defined solely in terms of operations on iterators (and the data pointed to by iterators), then each algorithm should be specific about the minimum iterator functionality that it needs. For example, an algorithm that searches for a specific element—such as the generic algorithm find()—only needs an iterator that can step through the elements, one at a time, and make a comparison. Here is a possible implementation of find() that shows how a generic algorithm can make explicit the minimum-functionality iterator it needs:

    template <class InputIterator, class T>    InputIterator find(InputIterator first,                        InputIterator last, const T& value)    {         for (; first != last; ++first)             if (value == *first)                return first;         return last;    }

What this says is that find() needs just the minimum functionality encased in an InputIterator. But, of course, it would be just as happy with other iterator types if they can do what a InputIterator does.

There is then obviously a need to create a categorization of the different iterator capabilities. For this purpose, the designers of the generic library have defined five different categories of iterators:

      InputIterator          OutputIterator      ForwardIterator      BidirectionalIterator      RandomAccessIterator

An InputIterator is a forward incrementing iterator that can be used to read the elements of a container. It supports both the prefix and the postfix versions of the increment operator ++. The algorithm find() is an example of the generic library algorithms requiring just this level of support. An OutputIterator—also a forward incrementing iterator—can be used to write into the elements of a container. The algorithm copy(), whose prototype is shown below, is an example of a generic algorithm that takes an OutputIterator as the third argument to mark the position where writing should begin.

     template <class InputIterator, class OutputIterator>     OutputIterator copy(InputIterator first,                         InputIterator last,                         OutputIterator destination);

Starting with the position first and ending with the position one before last, this algorithm copies all the elements over to the positions starting with destination. The algorithm can copy elements from one container to another, or from one section of a container to another non-overlapping section of the same container. The function returns the iterator position that points to one past the last value written out.^[4]

As its name implies, a ForwardIterator is also a forward incrementing iterator. It can be used to both read from and write into the elements of a container. In that sense, it combines the functionalities of the InputIterator and the OutputIterator. The generic algorithms adjacent_find(), replace(), and so on, need just this level of functionality.

A BidirectionalIterator can step through a container in both directions and read from and write into the elements. A BidirectionalIterator can always be substituted where a ForwardIterator is needed. An example of a generic library algorithm that needs just this level of support is reverse().

Finally, a RandomAccessIterator, in addition to supporting all the functionality of a BidirectionalIterator, provides an array-like constant-time access to any element of a container. Let's say p is the current value of a random-access iterator. Obviously, *p yields the container element to which p points. Now suppose we invoke the dereferencing operation *(p + i) for some value of an integer i that will not take us outside the container. Since p was assumed to be a random-access iterator, *(p + i) will retrieve directly in constant time the sequence element pointed to by (p + i). To get to this position, an iterator that is only bidirectional could wend its way through by repeated invocations of the ‘++’ operator, but that would obviously be inefficient. The algorithms sort and sort_heap() are examples of the generic algorithms that need the level of iterator support provided by a random-access iterator.

It should be evident from the above discussion that only those containers can support random-access iterators that store the elements in consecutive memory segments, in the same manner in which arrays are stored. This is indeed the case with the container classes vector and deque. On the other hand, since container classes such as list, map, and so on, do not store their elements in consecutive memory blocks, but in forms resembling linked lists, they can only support bidirectional iterators.

13.2.2 How to Declare an Iterator

An identifier is declared to be an iterator by the following declaration:

     container< type >::iterator iter;

where ‘container’ is one of the sequence or associative containers; ‘type’ the data type of elements in the container; ‘iter’ the identifier being declared as an iterator; and ‘iterator’ one of the following names:

      iterator      reverse_iterator      const_iterator         // cannot modify elements      const_reverse_iterator // cannot modify elements

As one would expect from the iterator names that have "reverse" in them, the increment operator ‘++’ and the decrement operator ‘−’ have opposite meanings for reverse_iterator and for const_reverse_iterator. What that means is that if p is a reverse iterator, then ++p points to the preceding element, as opposed to the next element. As with const pointers, const_iterator and const_reverse_iterator do not permit any modifications to the element they point to.

Here are some examples of iterator declarations, some taken from our examples in the earlier chapters of this book:

      vector<Shape*>::iterator p;      list<string>::iterator iter;      list<int>::reverse_iterator r;      list<string>::const_iterator iter;      map<string, int>::iterator mit;

While all sequenced and associative container classes support iterator, reverse_iterator, const_iterator, and const_reverse_iterator, the nature of these iterators is different for different container classes and that affects the computational efficiency of the various operations we may wish to carry out with the help of the iterators. For example, all four of these iterators for the vector container class are of type RandomAccessIterator, whereas all four of these iterators for the list container class are of type BidirectionalIterator. The iterators will be of random access variety for a container class only if it can store the elements of a data sequence in continuous segments of memory. If elements have to be stored in disjoint segments, as in a linked list, then the container class is more likely to support a bidirectional iterator.

^[4]copy naturally assumes that the destination container has (last - first) number of positions available for writing into. However, if the OutputIterator supplied as the third argument in a call to copy also happens to be an inserter, the destination container will be expanded to accommodate any additional elements. An inserter is an iterator adapter. Iterator adapters are meant to give specialized behaviors to iterators. There are two other iterator adapters, one that allows an algorithm to operate on a container in reverse and one for working with streams.