Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

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 form Description

input iterator

Read only, forward moving

output iterator

Write only, forward moving

forward iterator

Both read and write, forward moving

bidirectional iterator

Read and write, forward and backward moving

random access iterator

Read and write, random access

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 

Iterator form Produced by

input iterator

istream_iterator

output iterator

ostream_iterator

inserter()

front_inserter()

back_inserter()

bidirectional iterator

list

set and multiset

map and multimap

random access iterator

ordinary pointers

vector

deque

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

2.2.1 Input Iterators

Input iterators are the simplest form of iterator. To understand their capabilities, consider an example algorithm:

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:

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.

2.2.1.1 Kinds of Input Iterators

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:

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:

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:

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.

2.2.2 Output Iterators

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:

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:

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.

2.2.3 Forward Iterators

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:

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:

2.2.4 Bidirectional Iterators

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:

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:

2.2.5 Random Access Iterators

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.


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:

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.

2.2.6 Reverse Iterators

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.



Previous fileTop of DocumentContentsIndex pageNext file