Standard C++ Library Reference ISO/IEC (VERSION3)

hence are often passed and returned by value, not by reference. Note also that none of the
operations described above can throw an exception, at least when performed on a valid iterator.
The hierarchy of iterator categories can be summarize by showing three sequences. For
write-only access to a sequence, you can use any of:
output iterator
-> forward iterator
-> bidirectional iterator
-> random-access iterator
The right arrow means ``can be replaced by.'' So any algorithm that calls for an output iterator
should work nicely with a forward iterator, for example, but not the other way around.
For read-only access to a sequence, you can use any of:
input iterator
-> forward iterator
-> bidirectional iterator
-> random-access iterator
An input iterator is the weakest of all categories, in this case.
Finally, for read/write access to a sequence, you can use any of:
forward iterator
-> bidirectional iterator
-> random-access iterator
Remember that an object pointer can always serve as a random-access iterator. Hence, it can
serve as any category of iterator, so long as it supports the proper read/write access to the
sequence it designates.
An iterator It other than an object pointer must also define the member types required by the
specialization iterator_traits<It>. Note that these requirements can be met by deriving
It from the public base class iterator.
This ``algebra'' of iterators is fundamental to practically everything else in the Standard
Template Library. It is important to understand the promises, and limitations, of each iterator
category to see how iterators are used by containers and algorithms in STL.
Algorithm Conventions
The descriptions of the algorithm template functions employ several shorthand phrases:
The phrase ``in the range [A, B)'' means the sequence of zero or more discrete values
beginning with A up to but not including B. A range is valid only if B is reachable from
A -- you can store A in an object N (N = A), increment the object zero or more times
●