STL Conventions:Iterator Conventions, Algorithm Conventions

<< Formatted Output:Print Formats, Print Functions, Print Conversion Specifiers

Containers:Cont::const_reference, difference_type, reverse_iterator >>

Chapter 9. STL Conventions

The Standard Template Library (page 1), or STL (page 1), establishes uniform

standards for the application of iterators (page 37) to STL containers (page 41) or

other sequences that you define, by STL algorithms (page 38) 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:

v 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++).

v InIt -- An input iterator X 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 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.

v 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.

v 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--).

v 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.

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 (page 1). 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:

v 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 (++N), and have the object compare equal to B after a finite

number of increments (N == B).

v The phrase ``each 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.

v The phrase ``the lowest value of 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.

v The phrase ``the highest value of 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.

v Expressions such as X - Y, where X and Y can be iterators other than

random-access iterators, are intended in the mathematical sense. The function

Standard C++ Library

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:

v X == X is true.

v If X == Y is true, then Y == X is true.

v If 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):

v ``strict'' means that pr(X, X) is false

v ``weak'' means that X and Y have an equivalent ordering if !pr(X, Y) && !pr(Y,

X) (X == Y need not be defined)

v ``ordering'' means that 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 (page 39) 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

(page 259), pop_heap (page 263), and push_heap (page 264). As with an ordered

sequence (page 39), the predicate function operator<, or any replacement for it,

must not alter either of its operands, and it must impose a strict weak ordering

(page 39) on the operands it compares.

Chapter 9. STL Conventions

Standard C++ Library

Table of Contents: