Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) 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.
For every iterator type
X
there is a corresponding signed integer type called the
*difference type*
of the iterator.

Since iterators are an abstraction of pointers, their semantics are
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 document 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 8 — Relations among iterator categories

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

→ Output |

The five categories of iterators correspond to the iterator concepts
InputIterator,
OutputIterator,
ForwardIterator,
BidirectionalIterator, and
RandomAccessIterator, respectively. The generic term *iterator* refers to
any type that satisfies Iterator.

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

Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges. A range is an iterator and a *sentinel* that designate
the beginning and end of the computation, or an iterator and a count that designate
the beginning and the number of elements to which the computation is to be applied.

An iterator and a sentinel denoting a range are comparable. The types of a sentinel and an iterator that denote a range must satisfy Sentinel ([iterators.sentinel]). A range [i,s) is empty if i == s; otherwise, [i,s) 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 the first iterator j such that j == s.

A sentinel
s
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 == s.
If
s
is reachable from
i,
[i,s) denotes a range.

A counted range [i,n) is empty if n == 0; otherwise, [i,n) refers to the n elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by the result of incrementing i n times.

A range [i,s) is valid if and only if s is reachable from i. A counted range [i,n) is valid if and only if n == 0; or n is positive, i is dereferenceable, and [++i,--n) is valid. 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).

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

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

The name iter_move denotes a *customization point
object* ([customization.point.object]). The expression
ranges::iter_move(E) for some subexpression E is expression-equivalent to the
following:

static_cast<decltype(iter_move(E))>(iter_move(E)), if that expression is well-formed when evaluated in a context that does not include ranges::iter_move but does include the lookup set produced by argument-dependent lookup ( ISO/IEC 14882:2014 §[basic.lookup.argdep]).

Otherwise, if the expression *E is well-formed:

if *E is an lvalue, std::move(*E);

otherwise, static_cast<decltype(*E)>(*E).

Otherwise, ranges::iter_move(E) is ill-formed.

If ranges::iter_move(E) does not equal *E, the program is ill-formed with no diagnostic required.

The name iter_swap denotes a *customization point
object* ([customization.point.object]). The expression
ranges::iter_swap(E1, E2) for some subexpressions E1 and E2
is expression-equivalent to the following:

(void)iter_swap(E1, E2), if that expression is well-formed when evaluated in a context that does not include ranges::iter_swap but does include the lookup set produced by argument-dependent lookup ( ISO/IEC 14882:2014 §[basic.lookup.argdep]) and the following declaration:

void iter_swap(auto, auto) = delete;

Otherwise, if the types of E1 and E2 both satisfy Readable, and if the reference type of E1 is swappable with ([concepts.lib.corelang.swappable]) the reference type of E2, then ranges::swap(*E1, *E2)

Otherwise, if the types T1 and T2 of E1 and E2 satisfy IndirectlyMovableStorable<T1, T2> && IndirectlyMovableStorable<T2, T1>, (void)(*E1 = iter_exchange_move(E2, E1)), except that E1 is evaluated only once.

Otherwise, ranges::iter_swap(E1, E2) is ill-formed.

If ranges::iter_swap(E1, E2) does not swap the values denoted by the expressions E1 and E2, the program is ill-formed with no diagnostic required.

iter_exchange_move is an exposition-only function specified as:
```
template <class X, class Y>
constexpr value_type_t<remove_reference_t<X>> iter_exchange_move(X&& x, Y&& y)
noexcept(
```

*see below*);

*Effects:* Equivalent to:

value_type_t<remove_reference_t<X>> old_value(iter_move(x)); *x = iter_move(y); return old_value;

*Remarks:* The expression in the noexcept is equivalent to:

NE(remove_reference_t<X>, remove_reference_t<Y>) && NE(remove_reference_t<Y>, remove_reference_t<X>)

Where NE(T1, T2) is the expression:

is_nothrow_constructible<value_type_t<T1>, rvalue_reference_t<T1>>::value && is_nothrow_assignable<value_type_t<T1>&, rvalue_reference_t<T1>>::value && is_nothrow_assignable<reference_t<T1>, rvalue_reference_t<T2>>::value && is_nothrow_assignable<reference_t<T1>, value_type_t<T2>>::value> && is_nothrow_move_constructible<value_type_t<T1>>::value && noexcept(ranges::iter_move(declval<T1&>()))

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type. Accordingly, it is required that if WI is the name of a type that satisfies the WeaklyIncrementable concept ([iterators.weaklyincrementable]), R is the name of a type that satisfies the Readable concept ([iterators.readable]), and II is the name of a type that satisfies the InputIterator concept ([iterators.input]) concept, the types

difference_type_t<WI> value_type_t<R> iterator_category_t<II>

be defined as the iterator's difference type, value type and iterator category, respectively.

difference_type_t<T> is implemented as if:

template <class> struct difference_type { }; template <class T> struct difference_type<T*> : enable_if<is_object<T>::value, ptrdiff_t> { }; template <class I> struct difference_type<const I> : difference_type<decay_t<I>> { }; template <class T> requires requires { typename T::difference_type; } struct difference_type<T> { using type = typename T::difference_type; }; template <class T> requires !requires { typename T::difference_type; } && requires(const T& a, const T& b) { { a - b } -> Integral; } struct difference_type<T> : make_signed< decltype(declval<T>() - declval<T>()) > { }; template <class T> using difference_type_t = typename difference_type<T>::type;

Users may specialize difference_type on user-defined types.

A Readable type has an associated value type that can be accessed with the value_type_t alias template.

template <class> struct value_type { }; template <class T> struct value_type<T*> : enable_if<is_object<T>::value, remove_cv_t<T>> { }; template <class I> requires is_array<I>::value struct value_type<I> : value_type<decay_t<I>> { }; template <class I> struct value_type<const I> : value_type<decay_t<I>> { }; template <class T> requires requires { typename T::value_type; } struct value_type<T> : enable_if<is_object<typename T::value_type>::value, typename T::value_type> { }; template <class T> requires requires { typename T::element_type; } struct value_type<T> : enable_if< is_object<typename T::element_type>::value, remove_cv_t<typename T::element_type>> { }; template <class T> using value_type_t = typename value_type<T>::type;

If a type I has an associated value type, then value_type<I>::type shall name the value type. Otherwise, there shall be no nested type type.

The value_type class template may be specialized on user-defined types.

When instantiated with a type I
such that I::value_type is valid and denotes a type,
value_type<I>::type names that type, unless it is not an object type ( ISO/IEC 14882:2014 §[basic.types]) in which case
value_type<I> shall have no nested type type. [ *Note:* Some legacy output
iterators define a nested type named value_type that is an alias for void. These
types are not Readable and have no associated value types.* — end note* ]

When instantiated with a type I
such that I::element_type is valid and denotes a type,
value_type<I>::type names the type remove_cv_t<I::element_type>, unless it is
not an object type ( ISO/IEC 14882:2014 §[basic.types]) in which case
value_type<I> shall have no nested type type. [ *Note:* Smart pointers like
shared_ptr<int> are Readable and have an associated value type. But a smart pointer
like shared_ptr<void> is not Readable and has no associated value type.* — end note* ]

iterator_category_t<T> is implemented as if:

template <class> struct iterator_category { }; template <class T> struct iterator_category<T*> : enable_if<is_object<T>::value, random_access_iterator_tag> { }; template <class T> struct iterator_category<T const> : iterator_category<T> { }; template <class T> requires requires { typename T::iterator_category; } struct iterator_category<T> { using type =see below; }; template <class T> using iterator_category_t = typename iterator_category<T>::type;

Users may specialize iterator_category on user-defined types.

If T::iterator_category is valid and denotes a type, then the type iterator_category<T>::type is computed as follows:

If T::iterator_category is the same as or derives from std::random_access_iterator_tag, iterator_category<T>::type is ranges::random_access_iterator_tag.

Otherwise, if T::iterator_category is the same as or derives from std::bidirectional_iterator_tag, iterator_category<T>::type is ranges::bidirectional_iterator_tag.

Otherwise, if T::iterator_category is the same as or derives from std::forward_iterator_tag, iterator_category<T>::type is ranges::forward_iterator_tag.

Otherwise, if T::iterator_category is the same as or derives from std::input_iterator_tag, iterator_category<T>::type is ranges::input_iterator_tag.

Otherwise, if T::iterator_category is the same as or derives from std::output_iterator_tag, iterator_category<T> has no nested type.

Otherwise, iterator_category<T>::type is T::iterator_category

rvalue_reference_t<T> is implemented as if:

```
template <
```

*dereferenceable* T>
requires *see below* using rvalue_reference_t
= decltype(ranges::iter_move(declval<T&>()));

The expression in the requires clause is equivalent to:

requires(T& t) { { ranges::iter_move(t) } -> auto&&; }

The Readable concept is satisfied by types that are readable by applying operator* including pointers, smart pointers, and iterators.

template <class In> concept bool Readable = requires { typename value_type_t<In>; typename reference_t<In>; typename rvalue_reference_t<In>; } && CommonReference<reference_t<In>&&, value_type_t<In>&> && CommonReference<reference_t<In>&&, rvalue_reference_t<In>&&> && CommonReference<rvalue_reference_t<In>&&, const value_type_t<In>&>;

The Writable concept specifies the requirements for writing a value into an iterator's referenced object.

template <class Out, class T> concept bool Writable = requires(Out&& o, T&& t) { *o = std::forward<T>(t); // not required to be equality preserving *std::forward<Out>(o) = std::forward<T>(t); // not required to be equality preserving const_cast<const reference_t<Out>&&>(*o) = std::forward<T>(t); // not required to be equality preserving const_cast<const reference_t<Out>&&>(*std::forward<Out>(o)) = std::forward<T>(t); // not required to be equality preserving };

Let E be an an expression such that decltype((E)) is T, and let o be a dereferenceable object of type Out. Writable<Out, T> is satisfied only if

If Readable<Out> && Same<value_type_t<Out>, decay_t<T>> is satisfied, then *o after any above assignment is equal to the value of E before the assignment.

After evaluating any above assignment expression, o is not required to be dereferenceable.

If E is an xvalue ( ISO/IEC 14882:2014 §[basic.lval]), the resulting state of the object it denotes is valid but unspecified ( ISO/IEC 14882:2014 §[lib.types.movedfrom]).

[ *Note:*
The only valid use of an operator* is on the left side of the assignment statement.
*Assignment through the same value of the writable type happens only once.*
* — end note* ]

The WeaklyIncrementable concept specifies the requirements on types that can be incremented with the pre- and post-increment operators. The increment operations are not required to be equality-preserving, nor is the type required to be EqualityComparable.

template <class I> concept bool WeaklyIncrementable = Semiregular<I> && requires(I i) { typename difference_type_t<I>; requires SignedIntegral<difference_type_t<I>>; { ++i } -> Same<I>&; // not required to be equality preserving i++; // not required to be equality preserving };

Let i be an object of type I. When i is in the domain of
both pre- and post-increment, i is said to be *incrementable*.
WeaklyIncrementable<I> is satisfied only if

The expressions ++i and i++ have the same domain.

If i is incrementable, then both ++i and i++ advance i to the next element.

If i is incrementable, then &++i is equal to &i.

[ *Note:* For WeaklyIncrementable types, a equals b does not imply that ++a
equals ++b. (Equality does not guarantee the substitution property or referential
transparency.) Algorithms on weakly incrementable types should never attempt to pass
through the same incrementable value twice. They should be single pass algorithms. These algorithms
can be used with istreams as the source of the input data through the istream_iterator class
template.* — end note* ]

The Incrementable concept specifies requirements on types that can be incremented with the pre-
and post-increment operators. The increment operations are required to be equality-preserving,
and the type is required to be EqualityComparable. [ *Note:* This requirement
supersedes the annotations on the increment expressions in the definition of
WeaklyIncrementable. * — end note* ]

template <class I> concept bool Incrementable = Regular<I> && WeaklyIncrementable<I> && requires(I i) { { i++ } -> Same<I>&&; };

Let a and b be incrementable objects of type I. Incrementable<I> is satisfied only if

If bool(a == b) then bool(a++ == b).

If bool(a == b) then bool((a++, a) == ++b).

[ *Note:* The requirement that a equals b implies ++a equals ++b
(which is not true for weakly incrementable types) allows the use of multi-pass one-directional
algorithms with types that satisfy Incrementable.* — end note* ]

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

```
template <class I>
concept bool Iterator =
requires(I i) {
{ *i } -> auto&&; // Requires: i is dereferenceable
} &&
WeaklyIncrementable<I>;
```

[ *Note:* The requirement that the result of dereferencing the iterator is deducible from
auto&& means that it cannot be void.* — end note* ]

The Sentinel concept specifies the relationship between an Iterator type and a Semiregular type whose values denote a range.

```
template <class S, class I>
concept bool Sentinel =
Semiregular<S> &&
Iterator<I> &&
WeaklyEqualityComparableWith<S, I>;
```

The domain of == can change over time. Given an iterator i and sentinel s such that [i,s) denotes a range and i != s, [i,s) is not required to continue to denote a range after incrementing any iterator equal to i. Consequently, i == s is no longer required to be well-defined.

The SizedSentinel concept specifies requirements on an Iterator and a Sentinel that allow the use of the - operator to compute the distance between them in constant time.

```
template <class S, class I>
concept bool SizedSentinel =
Sentinel<S, I> &&
!disable_sized_sentinel<remove_cv_t<S>, remove_cv_t<I>> &&
requires(const I& i, const S& s) {
{ s - i } -> Same<difference_type_t<I>>&&;
{ i - s } -> Same<difference_type_t<I>>&&;
};
```

Let i be an iterator of type I, and s a sentinel of type S such that [i,s) denotes a range. Let N be the smallest number of applications of ++i necessary to make bool(i == s) be true. SizedSentinel<S, I> is satisfied only if:

If N is representable by difference_type_t<I>, then s - i is well-defined and equals N.

If -N is representable by difference_type_t<I>, then i - s is well-defined and equals -N.

[ *Note:* disable_sized_sentinel provides a mechanism to
enable use of sentinels and iterators with the library that meet the
syntactic requirements but do not in fact satisfy SizedSentinel.
A program that instantiates a library template that requires
SizedSentinel with an iterator type I and sentinel type
S that meet the syntactic requirements of SizedSentinel<S, I>
but do not satisfy SizedSentinel is ill-formed with no diagnostic required
unless disable_sized_sentinel<S, I> evaluates to
true ([structure.requirements]). * — end note* ]

[ *Note:* The SizedSentinel
concept is satisfied by pairs of
RandomAccessIterators ([iterators.random.access]) and by
counted iterators and their sentinels ([counted.iterator]).* — end note* ]

The InputIterator concept is a refinement of
Iterator ([iterators.iterator]). It
defines requirements for a type whose referenced values can be read (from the requirement for
Readable ([iterators.readable])) and which can be both pre- and post-incremented.
[ *Note:* Unlike in ISO/IEC 14882, input iterators are not required to satisfy
EqualityComparable ([concepts.lib.compare.equalitycomparable]).* — end note* ]

template <class I> concept bool InputIterator = Iterator<I> && Readable<I> && requires { typename iterator_category_t<I>; } && DerivedFrom<iterator_category_t<I>, input_iterator_tag>;

The OutputIterator concept is a refinement of Iterator ([iterators.iterator]). It defines requirements for a type that can be used to write values (from the requirement for Writable ([iterators.writable])) and which can be both pre- and post-incremented. However, output iterators are not required to satisfy EqualityComparable.

```
template <class I, class T>
concept bool OutputIterator =
Iterator<I> &&
Writable<I, T> &&
requires(I i, T&& t) {
*i++ = std::forward<T>(t); // not required to be equality preserving
};
```

Let E be an expression such that decltype((E)) is T, and let i be a dereferenceable object of type I. OutputIterator<I, T> is satisfied only if *i++ = E; has effects equivalent to:

*i = E; ++i;

[ *Note:*
Algorithms on output iterators should never attempt to pass through the same iterator twice.
They should be
*single pass*
algorithms.
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* ]

The ForwardIterator concept refines InputIterator ([iterators.input]), adding equality comparison and the multi-pass guarantee, specified below.

template <class I> concept bool ForwardIterator = InputIterator<I> && DerivedFrom<iterator_category_t<I>, forward_iterator_tag> && Incrementable<I> && Sentinel<I, I>;

The domain of == for forward iterators is that of iterators over the same
underlying sequence. However, value-initialized iterators of the same type
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* ]

Pointers and references obtained from a forward iterator into a range [i,s) shall remain valid while [i,s) continues to denote a range.

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

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

The expression ([](X x){++x;}(a), *a) is equivalent to the expression *a.

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

The BidirectionalIterator concept refines ForwardIterator ([iterators.forward]), and adds the ability to move an iterator backward as well as forward.

template <class I> concept bool BidirectionalIterator = ForwardIterator<I> && DerivedFrom<iterator_category_t<I>, bidirectional_iterator_tag> && requires(I i) { { --i } -> Same<I>&; { i-- } -> Same<I>&&; };

A bidirectional iterator r is decrementable if and only if there exists some s such that ++s == r. Decrementable iterators r shall be in the domain of the expressions --r and r--.

Let a and b be decrementable objects of type I. BidirectionalIterator<I> is satisfied only if:

&--a == &a.

If bool(a == b), then bool(a-- == b).

If bool(a == b), then after evaluating both a-- and --b, bool(a == b) still holds.

If a is incrementable and bool(a == b), then bool(--(++a) == b).

If bool(a == b), then bool(++(--a) == b).

The RandomAccessIterator concept refines BidirectionalIterator ([iterators.bidirectional]) and adds support for constant-time advancement with +=, +, -=, and -, and the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

template <class I> concept bool RandomAccessIterator = BidirectionalIterator<I> && DerivedFrom<iterator_category_t<I>, random_access_iterator_tag> && StrictTotallyOrdered<I> && SizedSentinel<I, I> && requires(I i, const I j, const difference_type_t<I> n) { { i += n } -> Same<I>&; { j + n } -> Same<I>&&; { n + j } -> Same<I>&&; { i -= n } -> Same<I>&; { j - n } -> Same<I>&&; j[n]; requires Same<decltype(j[n]), reference_t<I>>; };

Let a and b be valid iterators of type I such that b is reachable from a. Let n be the smallest value of type difference_type_t<I> such that after n applications of ++a, then bool(a == b). RandomAccessIterator<I> is satisfied only if:

(a += n) is equal to b.

&(a += n) is equal to &a.

(a + n) is equal to (a += n).

For any two positive integers x and y, if a + (x + y) is valid, then a + (x + y) is equal to (a + x) + y.

a + 0 is equal to a.

If (a + (n - 1)) is valid, then a + n is equal to ++(a + (n - 1)).

(b += -n) is equal to a.

(b -= n) is equal to a.

&(b -= n) is equal to &b.

(b - n) is equal to (b -= n).

If b is dereferenceable, then a[n] is valid and is equal to *b.