Varieties of Iterators

There are five basic forms of iterators used in the standard library:

Iterator categories are hierarchical. Forward iterators can be used wherever input or output iterators are required, bidirectional iterators can be used in place of forward iterators, and random access iterators can be used in situations requiring bidirectionality.

A second characteristic of iterators is whether or not they can be used to modify the values held by their associated container. A constant iterator is one that can be used for access only, and cannot be used for modification. Output iterators are never constant, and input iterators always are. Other iterators may or may not be constant, depending upon how they are created. There are both constant and non-constant bidirectional iterators, both constant and non-constant random access iterators, and so on.

The following table summarizes specific ways that various categories of iterators are generated by the containers in the standard library.

In the following sections we will describe the capabilities and construction of each form of iterator.

Input iterators are the simplest form of iterator. To understand their capabilities, consider an example program. The find() generic algorithm (to be described in more detail in Chapter 13: Find an Element Satisfying a Condition), performs a simple linear search, looking for a specific value being held within a container. The contents of the container are described using two iterators, here called first and last. While first is not equal to last the element denoted by first is compared to the test value. If equal, the iterator, which now denotes the located element, is returned. If not equal, the first iterator is incremented, and the loop cycles once more. If the entire region of memory is examined without finding the desired value, then the algorithm returns the end-of-range iterator.

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

This algorithm illustrates three requirements for an input iterator:

• An iterator can be compared for equality to another iterator. They are equal when they point to the same position, and are otherwise not equal.
• An iterator can be dereferenced using the * operator, to obtain the value being denoted by the iterator.
• An iterator can be incremented, so that it refers to the next element in sequence, using the operator ++.

Notice that these characteristics can all be provided with new meanings in a C++ program, since the behavior of the given functions can all be modified by overloading the appropriate operators. Because of this overloading, iterators are possible. There are three main varieties of input iterators:

Ordinary pointers. Ordinary pointers can be used as input iterators. In fact, since we can subscript and add to ordinary pointers, they are random access values, and thus can be used either as input or output iterators. The end-of-range pointer describes the end of a contiguous region of memory, and the deference and increment operators have their conventional meanings. For example, the following searches for the value 7 in an array of integers:

Ordinary Pointers as Iterators

int data[100];
    ...
 int * where = find(data, data+100, 7);
 

Note that constant pointers, pointers which do not permit the underlying array to be modified, can be created by simply placing the keyword const in a declaration.

const int * first = data;
 const int * last = data + 100;
    // can't modify location returned by the following
 const int * where = find(first, last, 7);
 

Container iterators. All of the iterators constructed for the various containers provided by the standard library are at least as general as input iterators. The iterator for the first element in a collection is always constructed by the member function begin(), while the iterator that denotes the "past-the-end" location is generated by the member function end(). For example, the following searches for the value 7 in a list of integers:

list<int>::iterator where = find(aList.begin(), aList.end(), 7);
 

Each container that supports iterators provides a type within the class declaration with the name iterator. Using this, iterators can uniformly be declared in the fashion shown. If the container being accessed is constant, or if the description const_iterator is used, then the iterator is a constant iterator.

Input stream iterators. The standard library provides a mechanism to operate on an input stream using an input iterator. This ability is provided by the class istream_iterator, and will be described in more detail in Input Stream Iterators.

An output iterator has the opposite function from an input iterator. Output iterators can be used to assign values in a sequence, but cannot be used to access values. For example, we can use an output iterator in a generic algorithm that copies values from one sequence into another:

template <class InputIterator, class OutputIterator>
 OutputIterator copy
    (InputIterator first, InputIterator last, OutputIterator result) 
 {
     while (first != last) 
       *result++ = *first++;
     return result;
 }
 

Parallel Sequences

Two ranges are being manipulated here; the range of source values specified by a pair of input iterators, and the destination range. The latter, however, is specified by only a single argument. It is assumed that the destination is large enough to include all values, and errors will ensue if this is not the case.

As illustrated by this algorithm, an output iterator can modify the element to which it points, by being used as the target for an assignment. Output iterators can use the dereference operator only in this fashion, and cannot be used to return or access the elements they denote.

As we noted earlier, ordinary pointers, as well as all the iterators constructed by containers in the standard library, can be used as examples of output iterators. (Ordinary pointers are random access iterators, which are a superset of output iterators.) So, for example, the following code fragment copies elements from an ordinary C-style array into a standard library vector:

int data[100];
 vector<int> newdata(100);
    ...
 copy (data, data+100, newdata.begin());
 

Just as the istream_iterator provided a way to operate on an input stream using the input iterator mechanism, the standard library provides a data type, ostream_iterator, that permits values to be written to an output stream in an iterator-like fashion. These will be described in Output Stream Iterators.

Yet another form of output iterator is an insert iterator. An insert iterator changes the output iterator operations of dereferencing/assignment and increment into insertions into a container. This permits operations such as copy() to be used with variable length containers, such as lists and sets. Insert iterators will be described in more detail in Insert Iterators.

A forward iterator combines the features of an input iterator and an output iterator. It permits values to both be accessed and modified. One function that uses forward iterators is the replace() generic algorithm, which replaces occurrences of specific values with other values. This algorithm is written as follows:

template <class ForwardIterator, class T>
 void 
    replace (ForwardIterator first, ForwardIterator last, 
             const T& old_value, const T& new_value)
 {
     while (first != last) 
     {
     if (*first == old_value) 
         *first = new_value;
         ++first;
     }
 }
 

Ordinary pointers, as well as any of the iterators produced by containers in the standard library, can be used as forward iterators. The following, for example, replaces instances of the value 7 with the value 11 in a vector of integers.

    replace (aVec.begin(), aVec.end(), 7, 11);

A bidirectional iterator is similar to a forward iterator, except that bidirectional iterators support the decrement operator (operator --), permitting movement in either a forward or a backward direction through the elements of a container. For example, we can use bidirectional iterators in a function that reverses the values of a container, placing the results into a new container.

template <class BidirectionalIterator, class OutputIterator>
 OutputIterator 
    reverse_copy (BidirectionalIterator first,
                  BidirectionalIterator last,
                  OutputIterator result) 
 {
     while (first != last) 
     *result++ = *--last;
     return result;
 }
 

As always, the value initially denoted by the last argument is not considered to be part of the collection.

The reverse_copy() function could be used, for example, to reverse the values of a linked list, and place the result into a vector:

   list<int> aList;
     ....
    vector<int> aVec (aList.size());
    reverse_copy (aList.begin(), aList.end(), aVec.begin() );
 

Some algorithms require more functionality than the ability to access values in either a forward or backward direction. Random access iterators permit values to be accessed by subscript, subtracted one from another (to yield the number of elements between their respective values) or modified by arithmetic operations, all in a manner similar to conventional pointers.

When using conventional pointers, arithmetic operations can be related to the underlying memory; that is, x+10 is the memory ten elements after the beginning of x. With iterators the logical meaning is preserved (x+10 is the tenth element after x), however the physical addresses being described may be different.

Algorithms that use random access iterators include generic operations such as sorting and binary search. For example, the following algorithm randomly shuffles the elements of a container. This is similar to, although simpler than, the function random_shuffle() provided by the standard library.

template <class RandomAccessIterator>
 void
    mixup (RandomAccessIterator first, RandomAccessIterator last)
 {
    while (first < last) 
    {
       iter_swap(first, first + randomInteger(last - first));
       ++first;
    }
 }
 

randomInteger()

The program will cycle as long as first is denoting a position that occurs earlier in the sequence than the one denoted by last. Only random access iterators can be compared using relational operators; all other iterators can be compared only for equality or inequality. On each cycle through the loop, the expression last - first yields the number of elements between the two limits. The function randomInteger() is assumed to generate a random number between 0 and the argument. Using the standard random number generator, this function could be written as follows:

unsigned int randomInteger (unsigned int n)
    // return random integer greater than
    // or equal to 0 and less than n
 {
    return rand() % n;

}

This random value is added to the iterator first, resulting in an iterator to a randomly selected value in the container. This value is then swapped with the element denoted by the iterator first.

An iterator naturally imposes an order on an underlying container of values. For a vector or a map the order is given by increasing index values. For a set it is the increasing order of the elements held in the container. For a list the order is explicitly derived from the way values are inserted.

A reverse iterator will yield values in exactly the reverse order of those given by the standard iterators. That is, for a vector or a list, a reverse iterator will generate the last element first, and the first element last. For a set it will generate the largest element first, and the smallest element last. Strictly speaking, reverse iterators are not themselves a new category of iterator. Rather, there are reverse bidirectional iterators, reverse random access iterators, and so on.

The list, set and map data types provide a pair of member functions that produce reverse bidirectional iterators. The functions rbegin() and rend() generate iterators that cycle through the underlying container in reverse order. Increments to such iterators move backward, and decrements move forward through the sequence.

Similarly, the vector and deque data types provide functions (also named rbegin() and rend()) that produce reverse random access iterators. Subscript and addition operators, as well as increments to such iterators move backward within the sequence.