# STL Conventions

<head><title>STL Conventions</title></head>

# STL Conventions

* * *

**[Algorithm Conventions](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#Algorithm%20Conventions)· [Iterator Conventions](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#Iterator%20Conventions)**

The [Standard
Template Library](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#Standard%20Template%20Library), or
[STL](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#STL), establishes uniform standards
for the application of
[iterators](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#Iterator%20Conventions) to STL
[containers](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_cont.html#Containers) or other sequences
that you define, by STL
[algorithms](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#Algorithm%20Conventions) 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 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 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.
- **`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 iteratorCopy to clipboard

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 iteratorCopy to clipboard

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 iteratorCopy to clipboard

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](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#Standard%20Template%20Library). 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 (`++N`),
and have the object compare equal to `B`
after a finite number of increments (`N == B`).
- 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.
- 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.
- 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.
- 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 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 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` 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)`
(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](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#strict%20weak%20ordering) 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](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering),
the predicate function `operator<`, or any
replacement for it, must not alter either of its operands,
and it must impose a
[strict weak ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#strict%20weak%20ordering) 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](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#Table%20of%20Contents)** and the
**[Index](https://docs.qualcomm.com/doc/80-N3040-23/topic/_cpp_index.html)**.

*[Copyright](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_crit_pjp.html) © 1992-2006by P.J. Plauger. All rights reserved.*

<!--V5.01:1566-->

Last Published: Oct 06, 2026

[Previous Topic
Locale Definitions](https://docs.qualcomm.com/bundle/publicresource/80-N3040-23/topics/cpp_localedefs.md) [Next Topic
STL Container](https://docs.qualcomm.com/bundle/publicresource/80-N3040-23/topics/cpp_lib_cont.md)