Algorithm
Conventions
Iterator
Conventions
The Standard Template Library, or STL, establishes uniform standards for the application of iterators to STL containers or other sequences that you define, by STL algorithms or other functions that you define. This document summarizes many of the conventions used widely throughout the Standard Template Library.
The STL facilities make widespread use of iterators, to mediate between the various algorithms and the sequences upon which they act. For brevity in the remainder of this document, the name of an iterator type (or its prefix) indicates the category of iterators required for that type. In order of increasing power, the categories are summarized here as:
OutIt -- An output
iterator X can only have a value V
stored indirect on it, after which it must be
incremented before the next store, as in (*X++ = V),
(*X = V, ++X), or (*X = V, X++).InIt -- An input
iterator X can represent a singular
value that indicates end-of-sequence. If such an iterator
does not compare equal to its end-of-sequence value, it
can have a value V accessed indirect on it
any number of times, as in (V = *X). To
progress to the next value, or end-of-sequence, you
increment it, as in ++X, X++,
or (V = *X++). Once you increment any
copy of an input iterator, none of the other copies can
safely be compared, dereferenced, or incremented
thereafter.FwdIt -- A forward
iterator X can take the place of an
output iterator (for writing) or an input iterator (for
reading). You can, however, read (via V = *X)
what you just wrote (via *X = V) through a
forward iterator. And you can make multiple copies of a
forward iterator, each of which can be dereferenced and
incremented independently.BidIt -- A bidirectional
iterator X can take the place of a
forward iterator. You can, however, also decrement a
bidirectional iterator, as in --X, X--,
or (V = *X--).RanIt -- A random-access
iterator X can take the place of a
bidirectional iterator. You can also perform much the
same integer arithmetic on a random-access iterator that
you can on an object pointer. For N an
integer object, you can write x[N], x
+ N, x - N, and N + X.Note that an object pointer can take the place of a random-access iterator, or any other for that matter. All iterators can be assigned or copied. They are assumed to be lightweight objects and 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.
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.
The descriptions of the algorithm template functions employ several shorthand phrases:
[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 (++N), and have
the object compare equal to B after a finite
number of increments (N == B).N in the range [A,
B)'' means that N begins with the
value A and is incremented zero or more
times until it equals the value B. The case N
== B is not in the range.N in the
range [A, B) such that X'' means that
the condition X is determined for each N in
the range [A, B) until the condition X is
met.N in
the range [A, B) such that X'' usually
means that X is determined for each N in the
range [A, B). The function stores in K
a copy of N each time the condition X is
met. If any such store occurs, the function replaces the
final value of N (which equals B)
with the value of K. For a bidirectional or
random-access iterator, however, it can also mean that N
begins with the highest value in the range and is
decremented over the range until the condition X is met.X - Y, where X
and Y can be iterators other than
random-access iterators, are intended in the mathematical
sense. The function does not necessarily evaluate operator-
if it must determine such a value. The same is also true
for expressions such as X + N and X
- N, where N is an integer type.Several algorithms make use of a predicate, using operator==,
that must impose an equivalence
relationship on pairs of elements from a sequence. For
all elements X, Y, and Z:
X == X is true.X == Y is true, then Y == X
is true.X == Y && Y == Z is true, then X
== Z is true.Several algorithms make use of a predicate that must impose a strict weak ordering on pairs
of elements from a sequence. For the predicate pr(X, Y):
pr(X, X) is falseX and Y
have an equivalent
ordering if !pr(X, Y) && !pr(Y, X)
(X == Y need not be defined)pr(X, Y) && pr(Y,
Z) implies pr(X, Z)Some of these algorithms implicitly use the predicate X
< Y. Other predicates that typically satisfy the
``strict weak ordering'' requirement are X > Y, less(X, Y), and greater(X, Y).
Note, however, that predicates such as X <= Y and
X >= Y do not satisfy this requirement.
A sequence of elements designated by iterators in the range [first,
last) is ``a sequence
ordered by operator<'' if, for each N
in the range [0, last - first) and for each M
in the range (N, last - first) the predicate !(*(first
+ M) < *(first + N)) is true. (Note that the elements
are sorted in ascending order.) The predicate function operator<,
or any replacement for it, must not alter either of its operands.
Moreover, it must impose a strict weak ordering
on the operands it compares.
A sequence of elements designated by iterators in the range [first,
last) is ``a heap ordered
by operator<'' if, for each N in
the range [1, last - first) the predicate !(*first
< *(first + N)) is true. (The first element is the
largest.) Its internal structure is otherwise known only to the
template functions make_heap,
pop_heap,
and push_heap.
As with an ordered sequence,
the predicate function operator<, or any
replacement for it, must not alter either of its operands, and it
must impose a strict weak ordering
on the operands it compares.
See also the Table of Contents.
Copyright © 1992-1996 by P.J. Plauger. All rights reserved.