[Previous] [Contents] [Next]

Caution: This version of this document is no longer maintained. For the latest documentation, see http://www.qnx.com/developers/docs.

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:

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:

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 boolresult 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):

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 boolresult 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:

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 boolresult 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-2002 by P.J. Plauger. All rights reserved.

[Previous] [Contents] [Next]