Like the containers, iterators define a common set of operations. Some operations are provided by all iterators; other operations are supported by only specific kinds of iterators. For example, ostream_iterator
s have only increment, dereference, and assignment. Iterators on vector
, string
s, and deque
s support these operations and the decrement, relational, and arithmetic operators.
Iterators are categorized by the operations they provide and the categories form a sort of hierarchy. With the exception of output iterators, an iterator of a higher category provides all the operations of the iterators of a lower categories.
The standard specifies the minimum category for each iterator parameter of the generic and numeric algorithms. For example, find
—which implements a one-pass, read-only traversal over a sequence—minimally requires an input iterator. The replace
function requires a pair of iterators that are at least forward iterators. Similarly, replace_copy
requires forward iterators for its first two iterators. Its third iterator, which represents a destination, must be at least an output iterator, and so on. For each parameter, the iterator must be at least as powerful as the stipulated minimum. Passing an iterator of a lesser power is an error.
Many compilers will not complain when we pass the wrong category of iterator to an algorithm.
Input iterators: can read elements in a sequence. An input iterator must provide
• Equality and inequality operators (==
, !=
) to compare two iterators
• Prefix and postfix increment (++
) to advance the iterator
• Dereference operator (*
) to read an element; dereference may appear only on the right-hand side of an assignment
• The arrow operator (->
) as a synonym for (* it).member
—that is, dereference the iterator and fetch a member from the underlying object
Input iterators may be used only sequentially. We are guaranteed that *it++
is valid, but incrementing an input iterator may invalidate all other iterators into the stream. As a result, there is no guarantee that we can save the state of an input iterator and examine an element through that saved iterator. Input iterators, therefore, may be used only for single-pass algorithms. The find
and accumulate
algorithms require input iterators; istream_iterator
s are input iterators.
Output iterators: can be thought of as having complementary functionality to input iterators; they write rather than read elements. Output iterators must provide
• Prefix and postfix increment (++
) to advance the iterator
• Dereference (*
), which may appear only as the left-hand side of an assignment (Assigning to a dereferenced output iterator writes to the underlying element.)
We may assign to a given value of an output iterator only once. Like input iterators, output iterators may be used only for single-pass algorithms. Iterators used as a destination are typically output iterators. For example, the third parameter to copy
is an output iterator. The ostream_iterator
type is an output iterator.
Forward iterators: can read and write a given sequence. They move in only one direction through the sequence. Forward iterators support all the operations of both input iterators and output iterators. Moreover, they can read or write the same element multiple times. Therefore, we can use the saved state of a forward iterator. Hence, algorithms that use forward iterators may make multiple passes through the sequence. The replace
algorithm requires a forward iterator; iterators on forward_list
are forward iterators.
Bidirectional iterators: can read and write a sequence forward or backward. In addition to supporting all the operations of a forward iterator, a bidirectional iterator also supports the prefix and postfix decrement (--
) operators. The reverse
algorithm requires bidirectional iterators, and aside from forward_list
, the library containers supply iterators that meet the requirements for a bidirectional iterator.
Random-access iterators: provide constant-time access to any position in the sequence. These iterators support all the functionality of bidirectional iterators. In addition, random-access iterators support the operations from Table 3.7 (p. 111):
• The relational operators (<
, <=
, >
, and >=
) to compare the relative positions of two iterators.
• Addition and subtraction operators (+
, +=
, -
, and -=
) on an iterator and an integral value. The result is the iterator advanced (or retreated) the integral number of elements within the sequence.
• The subtraction operator (-
) when applied to two iterators, which yields the distance between two iterators.
• The subscript operator (iter[n]
) as a synonym for * (iter + n)
.
The sort
algorithms require random-access iterators. Iterators for array, deque, string
, and vector
are random-access iterators, as are pointers when used to access elements of a built-in array.