Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(containers) in a uniform manner.
To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators.
All input iterators
i
support the expression
*i,
resulting in a value of some object type
T,
called the
*value type*
of the iterator.
All output iterators support the expression
*i = o
where
o
is a value of some type that is in the set of types that are
*writable*
to the particular iterator type of
i.
All iterators
i
for which the expression
(*i).m
is well-defined, support the expression
i->m
with the same semantics as
(*i).m.
For every iterator type
X
for which
equality is defined, there is a corresponding signed integer type called the
*difference type*
of the iterator.

Since iterators are an abstraction of pointers, their semantics is
a generalization of most of the semantics of pointers in C++.
This ensures that every
function template
that takes iterators
works as well with regular pointers.
This International Standard defines
five categories of iterators, according to the operations
defined on them:
*input iterators*,
*output iterators*,
*forward iterators*,
*bidirectional iterators*
and
*random access iterators*,
as shown in Table [tab:iterators.relations].

Table 105 — Relations among iterator categories

Random Access | → Bidirectional |
→ Forward | → Input |

→ Output |

Forward iterators satisfy all the requirements of input iterators and can be used whenever an input iterator is specified; Bidirectional iterators also satisfy all the requirements of forward iterators and can be used whenever a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.

Iterators that further satisfy the requirements of output iterators are
called *mutable iterator*s. Nonmutable iterators are referred to
as *constant iterator*s.

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence.
These values are called
*past-the-end*
values.
Values of an iterator
i
for which the expression
*i
is defined are called
*dereferenceable*.
The library never assumes that past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with any
sequence.
[ *Example:*
After the declaration of an uninitialized pointer
x
(as with
int* x;),
x
must always be assumed to have a singular value of a pointer.
* — end example* ]
Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that satisfy the
DefaultConstructible requirements, using a value-initialized iterator
as the source of a copy or move operation. [ *Note:* This guarantee is not
offered for default initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers.
* — end note* ]
In these cases the singular
value is overwritten the same way as any other value.
Dereferenceable
values are always non-singular.

An iterator
j
is called
*reachable*
from an iterator
i
if and only if there is a finite sequence of applications of
the expression
++i
that makes
i == j.
If
j
is reachable from
i,
they refer to elements of the same sequence.

Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges.
A
*range*
is a pair of iterators that designate the beginning and end of the computation.
A range [i,i)
is an empty range;
in general, a range [i,j)
refers to the elements in the data structure starting with the element
pointed to by
i
and up to but not including the element pointed to by
j.
Range [i,j)
is valid if and only if
j
is reachable from
i.
The result of the application of functions in the library to invalid ranges is
undefined.

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.

Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

In the following sections,
a
and
b
denote values of type
X or const X,
difference_type and reference refer to the
types iterator_traits<X>::difference_type and
iterator_traits<X>::reference, respectively,
n
denotes a value of
difference_type,
u,
tmp,
and
m
denote identifiers,
r
denotes a value of
X&,
t
denotes a value of value type
T,
o
denotes a value of some type that is writable to the output iterator.
[ *Note:* For an iterator type X there must be an instantiation
of iterator_traits<X> ([iterator.traits]). * — end note* ]

This definition applies to pointers, since pointers are iterators. The effect of dereferencing an iterator that has been invalidated is undefined.

The Iterator requirements form the basis of the iterator concept taxonomy; every iterator satisfies the Iterator requirements. This set of requirements specifies operations for dereferencing and incrementing an iterator. Most algorithms will require additional operations to read ([input.iterators]) or write ([output.iterators]) values, or to provide a richer set of iterator movements ([forward.iterators], [bidirectional.iterators], [random.access.iterators]).)

A type X satisfies the Iterator requirements if:

X satisfies the CopyConstructible, CopyAssignable, and Destructible requirements ([utility.arg.requirements]) and lvalues of type X are swappable ([swappable.requirements]), and

the expressions in Table [tab:iterator.requirements] are valid and have the indicated semantics.

Table 106 — Iterator requirements

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

*r | reference | pre: r is dereferenceable. | |

++r | X& |

A class or pointer type X satisfies the requirements of an input iterator for the value type T if X satisfies the Iterator ([iterator.iterators]) and EqualityComparable (Table [equalitycomparable]) requirements and the expressions in Table [tab:iterator.input.requirements] are valid and have the indicated semantics.

In Table [tab:iterator.input.requirements], the term
*the domain of ==*
is used in the ordinary mathematical sense to denote
the set of values over which
== is (required to be) defined.
This set can change over time.
Each algorithm places additional requirements on the domain of
== for the iterator values it uses.
These requirements can be inferred from the uses that algorithm
makes of == and !=.
[ *Example:*
the call find(a,b,x)
is defined only if the value of a
has the property *p*
defined as follows:
b has property *p*
and a value i
has property *p*
if
(*i==x)
or if
(*i!=x
and
++i
has property
p).
* — end example* ]

Table 107 — Input iterator requirements (in addition to Iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

a != b | contextually convertible to bool | !(a == b) | pre: (a,b) is in the domain of ==. |

*a | convertible to T |
pre: a is dereferenceable. The expression (void)*a, *a is equivalent to *a. If a == b and (a,b) is in the domain of == then *a is equivalent to *b. | |

a->m | (*a).m | pre: a is dereferenceable. | |

++r | X& |
pre: r is dereferenceable. post: r is dereferenceable or r is past-the-end. post: any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==. | |

(void)r++ | equivalent to (void)++r | ||

*r++ | convertible to T |
{ T tmp = *r; ++r; return tmp; } |

[ *Note:*
For input iterators,
a == b
does not imply
++a == ++b.
(Equality does not guarantee the substitution property or referential transparency.)
Algorithms on input iterators should never attempt to pass through the same iterator twice.
They should be
*single pass*
algorithms.
Value type T is not required to be a CopyAssignable type (Table [copyassignable]).
These algorithms can be used with istreams as the source of the input data through the
istream_iterator
class template.
* — end note* ]

A class or pointer type X satisfies the requirements of an output iterator if X satisfies the Iterator requirements ([iterator.iterators]) and the expressions in Table [tab:iterator.output.requirements] are valid and have the indicated semantics.

Table 108 — Output iterator requirements (in addition to Iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

*r = o | result is not used |
Remark: After this operation r is not required to be dereferenceable.post: r is incrementable. | |

++r | X& |
&r == &++r.Remark: After this operation r is not required to be dereferenceable.post: r is incrementable. | |

r++ | convertible to const X& |
{ X tmp = r; ++r; return tmp; } |
Remark: After this operation r is not required to be dereferenceable.post: r is incrementable. |

*r++ = o | result is not used |
Remark: After this operation r is not required to be dereferenceable.post: r is incrementable. |

[ *Note:*
The only valid use of an
operator*
is on the left side of the assignment statement.
*Assignment through the same value of the iterator happens only once.*
Algorithms on output iterators should never attempt to pass through the same iterator twice.
They should be
*single pass*
algorithms.
Equality and inequality might not be defined.
Algorithms that take output iterators can be used with ostreams as the destination
for placing data through the
ostream_iterator
class as well as with insert iterators and insert pointers.
* — end note* ]

A class or pointer type X satisfies the requirements of a forward iterator if

X satisfies the requirements of an input iterator ([input.iterators]),

X satisfies the DefaultConstructible requirements ([utility.arg.requirements]),

if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,

the expressions in Table [tab:iterator.forward.requirements] are valid and have the indicated semantics, and

objects of type X offer the multi-pass guarantee, described below.

The domain of == for forward iterators is that of iterators over the same
underlying sequence. However, value-initialized iterators may be compared and
shall compare equal to other value-initialized iterators of the same type.
[ *Note:* value initialized iterators behave as if they refer past the end of
the same empty sequence * — end note* ]

Two dereferenceable iterators a and b of type X offer the
*multi-pass guarantee* if:

a == b implies ++a == ++b and

X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.

[ *Note:*
The requirement that
a == b
implies
++a == ++b
(which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through
a mutable iterator
(which applies to output iterators)
allows the use of multi-pass one-directional algorithms with forward iterators.
* — end note* ]

Table 109 — Forward iterator requirements (in addition to input iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

r++ | convertible to const X& |
{ X tmp = r; ++r; return tmp; } | |

*r++ | reference |

If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.

If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

A class or pointer type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the requirements for forward iterators, the following expressions are valid as shown in Table [tab:iterator.bidirectional.requirements].

Table 110 — Bidirectional iterator requirements (in addition to forward iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

-- r | X& |
pre: there exists s such that r == ++s. post: r is dereferenceable. --(++r) == r. -- r == -- s implies r == s. &r == &-- r. | |

r-- | convertible to const X& |
{ X tmp = r; -- r; return tmp; } | |

*r-- | reference |

[ *Note:*
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
* — end note* ]

A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, the following expressions are valid as shown in Table [tab:iterator.random.access.requirements].

Table 111 — Random access iterator requirements (in addition to bidirectional iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

r += n | X& |
{ difference_type m = n; if (m >= 0) while (m--) ++r; else while (m++) -- r; return r; } | |

a + n n + a | X |
{ X tmp = a; return tmp += n; } | a + n == n + a. |

r -= n | X& | return r += -n; | |

a - n | X |
{ X tmp = a; return tmp -= n; } | |

b - a | difference_type | return n |
pre: there exists a value n of type difference_type such that a + n == b. b == a + (b - a). |

a[n] | convertible to reference | *(a + n) | |

a < b | contextually convertible to bool | b - a > 0 | < is a total ordering relation |

a > b | contextually convertible to bool | b < a | > is a total ordering relation opposite to <. |

a >= b | contextually convertible to bool | !(a < b) | |

a <= b | contextually convertible to bool. | !(a > b) |