Iterators are a generalization of
that allow a C++ program to work with different data structures (for example,
and
(since C++20)) in a uniform manner. The iterator library provides definitions for iterators, as well as iterator traits, adaptors, and utility functions.
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
that takes iterators works as well with regular pointers.
Iterator categories
There are five(until C++17)six(since C++17) kinds of iterators:
,
,
,
,
, and
(since C++17). (See also
for the most basic kind of iterator.)
Instead of being defined by specific types, each category of iterator is defined by the operations that can be performed on it. This definition means that any type that supports the necessary operations can be used as an iterator -- for example, a pointer supports all of the operations required by
, so a pointer can be used anywhere a
is expected.
All of the iterator categories (except
) can be organized into a hierarchy, where more powerful iterator categories (e.g.
) support the operations of less powerful categories (e.g.
). If an iterator falls into one of these categories and also satisfies the requirements of
, then it is called a mutable iterator and supports both input and output. Non-mutable iterators are called constant iterators.
Iterators are called constexpr iterators if all operations provided to meet iterator category requirements are
.
(since C++20)Iterator category Operations and storage requirement write read increment decrement random
access contiguous
storage without
multiple
passes with
multiple
passes
Required
Required Required
(mutable if supports write operation)Required Required
(also satisfies
)Required Required Required
(also satisfies
)Required Required Required Required
(also satisfies
)Required Required Required Required Required
(also satisfies
)Required Required Required Required Required Required
category was only formally specified in C++17, but the iterators of
,
,
, and
, as well as pointers into C arrays are often treated as a separate category in pre-C++17 code.
Note: A type supporting the required operations in a row of the table above does not necessarily fall into the corresponding category, see the category page for the complete list of requirements.
Definitions
Types and writability
An input iterator i supports the expression *i, resulting in a value of some
T, called the value type of the iterator.
An output iterator i has a non-empty set of types that are writable(until C++20)
(since C++20) to the iterator; for each such type T, the expression *i=o is valid where o is a value of type T.
For every iterator type Xfor which equality is defined(until C++20), there is a corresponding signed
(until C++20)
(since C++20) type called the difference type of the iterator.
Dereferenceability and validity
Just as a regular pointer to an
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. Such a value is called a past-the-end value.
Values of an iterator i for which the expression *i is defined are called dereferenceable. The
never assumes that past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with any sequence. Results of most expressions are undefined for singular values; the only exceptions are
the assignment of a non-singular value to an iterator that holds a singular value,
destroying an iterator that holds a singular value, and,
for iterators that meet the
requirements, using a
iterator as the source of a copy or move(since C++11) operation.
In these cases the singular value is overwritten the same way as any other value. Dereferenceable values are always non-singular.
An invalid iterator is an iterator that may be singular.
Ranges
Most of the standard library’s algorithmic templates that operate on data structures have interfaces that use ranges.
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.
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.
(until C++20)A range can be denoted by either
[i, s), with an iterator i and a sentinels that designate the beginning and end of the computation (i and s can have different types), or
i + [0, n), with an iterator i and a count n that designate the beginning and the number of elements to which the computation is to be applied.
Iterator-sentinel rangeAn iterator and a sentinel denoting a range are comparable. [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, if any, 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 valid range.
Counted rangeA counted rangei + [0, n) is empty if n==0; otherwise, i + [0, 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, if any, pointed to by the result of n applications of ++i.
A counted range i + [0, n) is valid if and only if
n==0; or
all of the following conditions are satisfied: n is positive,
i is dereferenceable, and
++i + [0, --n) is valid.
(since C++20)The result of the application of functions in the standard library to invalid ranges is undefined.
Iterator concepts (since C++20)
A new system of iterators based on
that are different from C++17 iterators. While the basic taxonomy remains similar, the requirements for individual iterator categories are somewhat different.
Defined in namespace std
(C++20)
specifies that a type is indirectly readable by applying operator *
(concept)
(C++20)
specifies that a value can be written to an iterator's referenced object
(concept)
(C++20)
specifies that a
type can be incremented with pre- and post-increment operators
(concept)
(C++20)
specifies that the increment operation on a
type is
and that the type is
(concept)
is-integer-likeis-signed-integer-like
(C++20)(C++20)
specifies that a type behaves as a (signed) integer type
(exposition-only concept*)
(C++20)
specifies that objects of a type can be incremented and dereferenced
(concept)
(C++20)
specifies a type is a sentinel for an
type
(concept)
(C++20)
specifies that the - operator can be applied to an iterator and a sentinel to calculate their difference in constant time
(concept)
(C++20)
specifies that a type is an input iterator, that is, its referenced values can be read and it can be both pre- and post-incremented
(concept)
(C++20)
specifies that a type is an output iterator for a given value type, that is, values of that type can be written to it and it can be both pre- and post-incremented
(concept)
(C++20)
specifies that an
is a forward iterator, supporting equality comparison and multi-pass
(concept)
(C++20)
specifies that a
is a bidirectional iterator, supporting movement backwards
(concept)
(C++20)
specifies that a
is a random-access iterator, supporting advancement in constant time and subscripting
(concept)
(C++20)
specifies that a
is a contiguous iterator, referring to elements that are contiguous in memory
(concept)
Iterator associated types (since C++20)
Iterator primitives
Iterator customization points (since C++20)
Defined in namespace std::ranges
(C++20)
casts the result of dereferencing an object to its associated rvalue reference type
(customization point object)
(C++20)
swaps the values referenced by two dereferenceable objects
(customization point object)
Algorithm concepts and utilities (since C++20)
A set of concepts and related utility templates designed to ease constraining common algorithm operations.
Defined in header
Defined in namespace std
Indirect callable concepts
indirectly_unary_invocableindirectly_regular_unary_invocable
(C++20)(C++20)
specifies that a callable type can be invoked with the result of dereferencing an
type
(concept)
(C++20)
specifies that a callable type, when invoked with the result of dereferencing an
type, satisfies
(concept)
(C++20)
specifies that a callable type, when invoked with the result of dereferencing two
types, satisfies
(concept)
(C++20)
specifies that a callable type, when invoked with the result of dereferencing two
types, satisfies
(concept)
(C++20)
specifies that a callable type, when invoked with the result of dereferencing two
types, satisfies
(concept)
Common algorithm requirements
(C++20)
specifies that values may be moved from an
type to an
type
(concept)
(C++20)
specifies that values may be moved from an
type to an
type and that the move may be performed via an intermediate object
(concept)
(C++20)
specifies that values may be copied from an
type to an
type
(concept)
(C++20)
specifies that values may be copied from an
type to an
type and that the copy may be performed via an intermediate object
(concept)
(C++20)
specifies that the values referenced by two
types can be swapped
(concept)
(C++20)
specifies that the values referenced by two
types can be compared
(concept)
(C++20)
specifies the common requirements of algorithms that reorder elements in place
(concept)
(C++20)
specifies the requirements of algorithms that merge sorted sequences into an output sequence by copying elements
(concept)
(C++20)
specifies the common requirements of algorithms that permute sequences into ordered sequences
(concept)
Utilities
(C++20)
computes the result of invoking a callable object on the result of dereferencing some set of
types
(alias template)
(C++20)
helper template for specifying the constraints on algorithms that accept projections
(class template)
(C++26)
computes the value type of an
type by projection
(alias template)
Iterator adaptors
iterator adaptor for reverse-order traversal
(class template)
(C++14)
creates a
of type inferred from the argument
(function template)
iterator adaptor for insertion at the end of a container
(class template)
creates a
of type inferred from the argument
(function template)
iterator adaptor for insertion at the front of a container
(class template)
creates a
of type inferred from the argument
(function template)
iterator adaptor for insertion into a container
(class template)
creates a
of type inferred from the argument
(function template)
(C++23)
iterator adaptor that converts an iterator into a constant iterator
(class template)
(C++23)
computes a constant iterator type for a given type
(alias template)
(C++23)
computes a sentinel type to be used with constant iterators
(alias template)
(C++23)
creates a std::const_iterator of type inferred from the argument
(function template)
(C++23)
creates a std::const_sentinel of type inferred from the argument
(function template)
(C++11)
iterator adaptor which dereferences to an rvalue
(class template)
(C++20)
sentinel adaptor for
(class template)
(C++11)
creates a
of type inferred from the argument
(function template)
(C++20)
adapts an iterator type and its sentinel into a common iterator type
(class template)
(C++20)
default sentinel for use with iterators that know the bound of their range
(class)
(C++20)
iterator adaptor that tracks the distance to the end of the range
(class template)
(C++20)
sentinel that always compares unequal to any
type
(class)
Stream iterators
Iterator operations
Defined in header
advances an iterator by given distance
(function template)
returns the distance between two iterators
(function template)
(C++11)
increment an iterator
(function template)
(C++11)
decrement an iterator
(function template)
(C++20)
advances an iterator by given distance or to a given bound
(algorithm function object)
(C++20)
returns the distance between an iterator and a sentinel, or between the beginning and end of a range
(algorithm function object)
(C++20)
increment an iterator by a given distance or to a bound
(algorithm function object)
(C++20)
decrement an iterator by a given distance or to a bound
(algorithm function object)
Range access (since C++11)
These non-member function templates provide a generic interface for containers, plain arrays, and
.
Defined in header
Defined in header
Defined in header
(since C++23)
Defined in header
(since C++23)
Defined in header
Defined in header
(since C++26)
Defined in header
(since C++26)
Defined in header
Defined in header
Defined in header
Defined in header
(since C++26)
Defined in header
Defined in header
Defined in header
(since C++20)
Defined in header
(since C++23)
Defined in header
Defined in header
(since C++17)
Defined in header
Defined in header
Defined in header
Defined in header
Defined in namespace std
(C++11)(C++14)
returns an iterator to the beginning of a container or array
(function template)
(C++11)(C++14)
returns an iterator to the end of a container or array
(function template)
(C++14)
returns a reverse iterator to the beginning of a container or array
(function template)
(C++14)
returns a reverse end iterator for a container or array
(function template)
(C++17)(C++20)
returns the size of a container or array
(function template)
(C++17)
checks whether the container is empty
(function template)
(C++17)
obtains the pointer to the underlying array
(function template)
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
C++98 array types could not be value types they can
C++98 past-the-end iterators were always non-singular they can be singular
C++98 the validity of an iterator was not defined defined to be always non-singular
C++98 output iterators had value types output iterators have writable types instead
C++98 singular iterators could not be destroyed allowed
(
) C++98 singular iterators could not be copied allowed if they are value-initialized
(
) C++98
,
and
always satisfy
they might not satisfy
(
) C++98 the definition of iterator singularity and
reachability depended on containers depend on sequences instead
C++17
did not provide the
range access function templates provides these templates
C++23
and
did not
provide the range access function templates provides these templates