STL Conventions
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.
Iterator Conventions
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 iteratorX
can only have a valueV
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 iteratorX
can represent a singular value that indicates end-of-sequence. If an input iterator does not compare equal to its end-of-sequence value, it can have a valueV
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 iteratorX
can take the place of an output iterator (for writing) or an input iterator (for reading). You can, however, read (viaV = *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 iteratorX
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 iteratorX
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. ForN
an integer object, you can writex[N]
,x + N
,x - N
, andN + 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.
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 withA
up to but not includingB
. A range is valid only ifB
is reachable fromA
-- you can storeA
in an objectN
(N = A
), increment the object zero or more times (++N
), and have the object compare equal toB
after a finite number of increments (N == B
). - The phrase ``each
N
in the range[A, B)
'' means thatN
begins with the valueA
and is incremented zero or more times until it equals the valueB
. The caseN == B
is not in the range. - The phrase ``the lowest value of
N
in the range[A, B)
such that X'' means that the condition X is determined for eachN
in the range[A, B)
until the condition X is met. - The phrase ``the highest value of
N
in the range[A, B)
such that X'' usually means that X is determined for eachN
in the range[A, B)
. The function stores inK
a copy ofN
each time the condition X is met. If any such store occurs, the function replaces the final value ofN
(which equalsB
) with the value ofK
. For a bidirectional or random-access iterator, however, it can also mean thatN
begins with the highest value in the range and is decremented over the range until the condition X is met. - Expressions such as
X - Y
, whereX
andY
can be iterators other than random-access iterators, are intended in the mathematical sense. The function does not necessarily evaluateoperator-
if it must determine such a value. The same is also true for expressions such asX + N
andX - N
, whereN
is an integer type.
Several algorithms make use of a predicate that performs a
pairwise comparison,
such as with operator==
, to yield a bool
result.
The predicate function operator==
, or any
replacement for it, must not alter either of its operands.
It must yield the same bool
result every time it is evaluated,
and it must yield the same result if a copy of either operand is substituted
for the operand.
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 false (X can't be ordered before itself)X
andY
have an equivalent ordering if!pr(X, Y) && !pr(Y, X)
(X == Y
need not be defined)pr(X, Y) && pr(Y, Z)
impliespr(X, Z)
(ordering is transitive)
Some of these algorithms implicitly use the predicate
X < Y
, and some use a predicate pr(X, Y)
passed as a function object. Predicates that
satisfy the ``strict weak ordering'' requirement are
X < Y
and X > Y
for the
arithmetic types and for string objects.
Note, however, that predicates such as X <= Y
and
X >= Y
for these same types
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.
It must yield the same bool
result every time it is evaluated,
and it must yield the same result if a copy of either operand is substituted
for the operand.
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.) - It is possible to insert (
push_heap
) a new element or remove (pop_heap
) the largest element in logarithmic time and preserve the heap discipline in the resulting sequence.
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.
It must yield the same bool
result every time it is evaluated,
and it must yield the same result if a copy of either operand is substituted
for the operand.
See also the Table of Contents and the Index.
Copyright © 1992-2006 by P.J. Plauger. All rights reserved.