2.2 Varieties of Iterators

As shown in Table 3, there are five basic forms of iterators used in the C++ Standard Library:

Table 3: Iterator forms in the C++ 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.

Table 4 summarizes specific ways that various categories of iterators are generated by the containers in the C++ Standard Library.

Table 4: Iterators generated in the C++ Standard Library 

In the following sections we 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 algorithm:

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

This algorithm, which is similar to the std::find() generic algorithm (Section 13.3.1), 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, first and last. While first is not equal to last, the element denoted by first is compared to the test value. If this element is equal to the test value, the iterator, which now denotes the located element, is returned. If it is 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.

This algorithm illustrates three features of an input iterator:

• An input iterator can be compared for equality to another iterator. They are equal when they point to the same position, and not equal otherwise.

• An input iterator can be dereferenced, using operator*() to obtain the value being denoted by the iterator.

• An input iterator can be incremented, so that it refers to the next element in sequence, using operator++().

Notice that these features 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 kinds of input iterators: ordinary pointers, container iterators, and input streams 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 dereference and increment operators have their conventional meanings. For example, the following code searches for the value 7 in an array of integers:

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

Note that constant 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 = std::find(first, last, 7);

Because ordinary pointers have the same functionality as random access iterators, most of the generic algorithms in the C++ Standard Library can be used with conventional C++ arrays, as well as with the containers provided by the C++ Standard Library.

Container iterators. All of the iterators constructed for the various containers provided by the C++ 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 iterator searches for the value 7 in a list of integers:

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

Each container that supports iterators provides a type with the name iterator within the class declaration. Using this type, 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 C++ Standard Library provides a mechanism to operate on an input stream using an input iterator. This ability is provided by the class istream_iterator, described in more detail in Section 2.3.1.

An output iterator has the opposite function of 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;
}

A number of the generic algorithms manipulate two parallel sequences. Frequently the second sequence is described using only a beginning iterator, rather than an iterator pair. It is assumed, but not checked, that the second sequence has at least as many elements as the first.

In the algorithm shown here, two ranges are being manipulated: 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; they cannot be used to return or to access the elements they denote.

As we noted earlier, ordinary pointers, like all iterators constructed by containers in the C++ Standard Library, can be used as output iterators. (Ordinary pointers are random access iterators, which are a superset of output iterators.) For example, in this code fragment elements from an ordinary C-style array are copied into a C++ Standard Library vector:

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

Just as the istream_iterator provides a way to operate on an input stream using the input iterator mechanism, the C++ Standard Library provides a datatype, ostream_iterator, that permits values to be written to an output stream in an iterator-like fashion (Section 2.3.2).

Yet another form of output iterator is an insert iterator (Section 2.4). 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.

A forward iterator combines the features of an input iterator and an output iterator. It permits values to be both 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 could be 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, like all iterators produced by containers in the C++ Standard Library, can be used as forward iterators. For example, in the following code instances of the value 7 are replaced with the value 11 in a vector of integers:

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

Bidirectional iterators are similar to forward iterators, 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 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:

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

Some algorithms require more functionality than simply accessing 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.

With 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 different the physical addresses being described.

Algorithms that use random access iterators include generic operations like 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 std::random_shuffle() provided by the C++ Standard Library.

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

---

NOTE -- The function randomInteger described here appears in a number of the example programs presented in later sections.

---

The program will cycle as long as first denotes 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 std::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 imposed by increasing index values; for a set, by 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 yields values in exactly the reverse order of values given by the standard iterators. For a vector or a list, a reverse iterator generates the last element first, and the first element last. For a set it generates the largest element first, and the smallest element last. Strictly speaking, reverse iterators do not constitute a new category of iterator, but an adaptation of another iterator type. Consequently, we have reverse bidirectional iterators and reverse random access iterators. Any bidirectional or random access iterator can be adapted by the reverse_iterator template.

The list, set, and map datatypes 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 datatypes 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.