View source for cpp/iterator

{{title|Iterator library}}
{{cpp/iterator/navbar}}

Iterators are a generalization of [[cpp/language/pointer|pointers]] that allow a C++ program to work with different data structures (for example, [[cpp/container|containers]]{{rev inl|since=c++20| and [[cpp/ranges|ranges]]}}) 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 [[cpp/language/function template|function template]] that takes iterators works as well with regular pointers.

===Iterator categories===
There are {{rev inl|until=c++17|five}}{{rev inl|since=c++17|six}} kinds of iterators: {{named req|InputIterator}}, {{named req|OutputIterator}}, {{named req|ForwardIterator}}, {{named req|BidirectionalIterator}}, {{named req|RandomAccessIterator}}{{rev inl|since=c++17|, and {{named req|ContiguousIterator}}}}.

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 {{named req|RandomAccessIterator}}, so a pointer can be used anywhere a {{named req|RandomAccessIterator}} is expected.

All of the iterator categories (except {{named req|OutputIterator}}) can be organized into a hierarchy, where more powerful iterator categories (e.g. {{named req|RandomAccessIterator}}) support the operations of less powerful categories (e.g. {{named req|InputIterator}}). If an iterator falls into one of these categories and also satisfies the requirements of {{named req|OutputIterator}}, then it is called a ''mutable'' iterator and supports ''both'' input and output. Non-mutable iterators are called ''constant'' iterators.

{{rrev|since=c++20|
Iterators are called ''constexpr'' iterators if all operations provided to meet iterator category requirements are [[cpp/language/constexpr#constexpr function|constexpr functions]].
}}

{| class="wikitable"
!rowspan="3"|Iterator category
!colspan="7"|Operations and storage requirement
|- style="text-align:center;"
|rowspan="2"|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;write&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|rowspan="2"|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;read&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|colspan="2"|increment
|rowspan="2"|&nbsp;decrement&nbsp;
|rowspan="2"|&nbsp;&nbsp;&nbsp;random&nbsp;&nbsp;&nbsp;<br>access
|rowspan="2"|&nbsp;contiguous&nbsp;<br>storage
|- style="text-align:center;"
|without<br>&nbsp;&nbsp;&nbsp;multiple&nbsp;&nbsp;&nbsp;<br>passes
|with<br>&nbsp;&nbsp;&nbsp;multiple&nbsp;&nbsp;&nbsp;<br>passes
|- style="text-align:center;"
|{{named req|OutputIterator}}
|{{yes|Required}}
|
|{{yes|Required}}
|
|
|
|
|- style="text-align:center;"
|{{named req|InputIterator}}<br>{{small|(mutable if supports write operation)}}
|
|{{yes|Required}}
|{{yes|Required}}
|
|
|
|
|- style="text-align:center;"
|{{named req|ForwardIterator}}<br>{{small|(also satisfies {{named req|InputIterator}})}}
|
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|
|
|
|- style="text-align:center;"
|{{named req|BidirectionalIterator}}<br>{{small|(also satisfies {{named req|ForwardIterator}})}}
|
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|
|
|- style="text-align:center;"
|{{named req|RandomAccessIterator}}<br>{{small|(also satisfies {{named req|BidirectionalIterator}})}}
|
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|
|- style="text-align:center;"
|&nbsp;&nbsp;&nbsp;{{named req|ContiguousIterator}}<ref>{{named req|ContiguousIterator}} category was only formally specified in C++17, but the iterators of {{lc|std::vector}}, {{lc|std::basic_string}}, {{lc|std::array}}, and {{lc|std::valarray}}, as well as pointers into C arrays are often treated as a separate category in pre-C++17 code.</ref><br>{{small|(also satisfies {{named req|RandomAccessIterator}})}}
|
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|{{yes|Required}}
|}
<references/>
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 {{c|i}} supports the expression {{c|*i}}, resulting in a value of some [[cpp/language/type|object type]] {{tt|T}}, called the ''value type'' of the iterator.

An output iterator {{c|i}} has a non-empty set of types that are {{rev inl|until=c++20|''writable''}}{{rev inl|since=c++20|{{ltt|cpp/iterator/indirectly_writable}}}} to the iterator; for each such type {{tt|T}}, the expression {{c|1=*i = o}} is valid where {{c|o}} is a value of type {{tt|T}}.

For every iterator type {{tt|X}} {{rev inl|until=c++20|for which equality is defined}}, there is a corresponding signed {{rev inl|until=c++20|[[cpp/language/types#Signed and unsigned integer types|integer]]}}{{rev inl|since=c++20|[[cpp/iterator/weakly_incrementable#Integer-like types|integer-like]]}} type called the ''difference type'' of the iterator.

====Dereferenceability and validity====
Just as a regular pointer to an [[cpp/language/array|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<!-- LWG 1210 -->. Such a value is called a ''past-the-end'' value.

Values of an iterator {{c|i}} for which the expression {{c|*i}} is defined are called ''dereferenceable''. The [[cpp/standard library|standard library]] 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 {{named req|DefaultConstructible}} requirements, using a [[cpp/language/value initialization|value-initialized]] iterator as the source of a copy {{rev inl|since=c++11|or move}} 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.

{{rev begin}}
{{rev|until=c++20|
An iterator {{c|j}} is called ''reachable'' from an iterator {{c|i}} if and only if there is a finite sequence of applications of the expression {{c|++i}} that makes {{c|1=i == j}}. If {{c|j}} is reachable from {{c|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 {{range|i|i}} is an empty range; in general, a range {{range|i|j}} refers to the elements in the data structure starting with the element pointed to by {{c|i}} and up to but not including the element pointed to by {{c|j}}.

Range {{range|i|j}} is ''valid'' if and only if {{c|j}} is reachable from {{c|i}}. 
}}
{{rev|since=c++20|
A ''range'' is either
* a [[#Comparable range|comparable range]] {{range|i|s}}, an iterator {{c|i}} and a ''sentinel'' {{c|s}} that designate the beginning and end of the computation ({{c|i}} and {{c|s}} can have different types), or
* a [[#Counted range|counted range]] {{counted range|i|n}}, an iterator {{c|i}} and a count {{c|n}} that designate the beginning and the number of elements to which the computation is to be applied.

=====Comparable range=====
An iterator and a sentinel denoting a range are comparable. {{range|i|s}} is empty if {{c|1=i == s}}; otherwise, {{range|i|s}} refers to the elements in the data structure starting with the element pointed to by {{c|i}} and up to but not including the element, if any, pointed to by the first iterator {{c|j}} such that {{c|1=j == s}}.

A sentinel {{c|s}} is called ''reachable'' from an iterator {{c|i}} if and only if there is a finite sequence of applications of the expression {{c|++i}} that makes {{c|1=i == s}}.

If {{c|s}} is reachable from {{c|i}}, {{range|i|s}} denotes a ''valid'' range.

=====Counted range=====
A ''counted range'' {{counted range|i|n}} is empty if {{c|1=n == 0}}; otherwise, {{counted range|i|n}} refers to the {{c|n}} elements in the data structure starting with the element pointed to by {{c|i}} and up to but not including the element, if any, pointed to by the result of {{c|n}} applications of {{c|++i}}.

A counted range {{counted range|i|n}} is ''valid'' if and only if
* {{c|1=n == 0}}; or
* all of the following conditions are satisfied:
** {{c|n}} is positive,
** {{c|i}} is dereferenceable, and
** {{counted range|--i|--n}} is valid.
}}
{{rev end}}

The result of the application of functions in the standard library to invalid ranges is undefined.

===Iterator concepts===
C++20 introduces a new system of iterators based on [[cpp/language/constraints|concepts]] that are different from C++17 iterators. While the basic taxonomy remains similar, the requirements for individual iterator categories are somewhat different.

{{dsc begin}}
{{dsc namespace|std}}
{{dsc inc|cpp/iterator/dsc indirectly_readable}}
{{dsc inc|cpp/iterator/dsc indirectly_writable}}
{{dsc inc|cpp/iterator/dsc weakly_incrementable}}
{{dsc inc|cpp/iterator/dsc incrementable}}
{{dsc inc|cpp/iterator/dsc input_or_output_iterator}}
{{dsc inc|cpp/iterator/dsc sentinel_for}}
{{dsc inc|cpp/iterator/dsc sized_sentinel_for}}
{{dsc inc|cpp/iterator/dsc input_iterator}}
{{dsc inc|cpp/iterator/dsc output_iterator}}
{{dsc inc|cpp/iterator/dsc forward_iterator}}
{{dsc inc|cpp/iterator/dsc bidirectional_iterator}}
{{dsc inc|cpp/iterator/dsc random_access_iterator}}
{{dsc inc|cpp/iterator/dsc contiguous_iterator}}
{{dsc end}}

===Iterator associated types===
{{dsc begin}}
{{dsc namespace|std}}
{{dsc inc|cpp/iterator/dsc incrementable_traits}}
{{dsc inc|cpp/iterator/dsc indirectly_readable_traits}}
{{dsc inc|cpp/iterator/dsc iter_t}}
{{dsc end}}

===Iterator primitives===
{{dsc begin}}
{{dsc inc|cpp/iterator/dsc iterator_traits}}
{{dsc inc|cpp/iterator/dsc iterator_tags}}
{{dsc inc|cpp/iterator/dsc iterator}}
{{dsc end}}

===Iterator customization points===
{{dsc begin}}
{{dsc namespace|std::ranges}}
{{dsc inc|cpp/iterator/ranges/dsc iter_move}}
{{dsc inc|cpp/iterator/ranges/dsc iter_swap}}
{{dsc end}}

===Algorithm concepts and utilities===
C++20 also provides a set of concepts and related utility templates designed to ease constraining common algorithm operations.

{{dsc begin}}
{{dsc header|iterator}}
{{dsc namespace|std }}
{{dsc h2|Indirect callable concepts}}
{{dsc inc|cpp/iterator/dsc indirectly_unary_invocable}}
{{dsc inc|cpp/iterator/dsc indirect_unary_predicate}}
{{dsc inc|cpp/iterator/dsc indirect_binary_predicate}}
{{dsc inc|cpp/iterator/dsc indirect_equivalence_relation}}
{{dsc inc|cpp/iterator/dsc indirect_strict_weak_order}}
{{dsc h2|Common algorithm requirements}}
{{dsc inc|cpp/iterator/dsc indirectly_movable}}
{{dsc inc|cpp/iterator/dsc indirectly_movable_storable}}
{{dsc inc|cpp/iterator/dsc indirectly_copyable}}
{{dsc inc|cpp/iterator/dsc indirectly_copyable_storable}}
{{dsc inc|cpp/iterator/dsc indirectly_swappable}}
{{dsc inc|cpp/iterator/dsc indirectly_comparable}}
{{dsc inc|cpp/iterator/dsc permutable}}
{{dsc inc|cpp/iterator/dsc mergeable}}
{{dsc inc|cpp/iterator/dsc sortable}}
{{dsc h2|Utilities}}
{{dsc inc|cpp/iterator/dsc indirect_result_t}}
{{dsc inc|cpp/iterator/dsc projected}}
{{dsc end}}

===Iterator adaptors===
{{dsc begin}}
{{dsc inc|cpp/iterator/dsc reverse_iterator}}
{{dsc inc|cpp/iterator/dsc make_reverse_iterator}}
{{dsc inc|cpp/iterator/dsc move_iterator}}
{{dsc inc|cpp/iterator/dsc move_sentinel}}
{{dsc inc|cpp/iterator/dsc make_move_iterator}}
{{dsc inc|cpp/iterator/dsc basic_const_iterator}}
{{dsc inc|cpp/iterator/dsc const_iterator}}
{{dsc inc|cpp/iterator/dsc const_sentinel}}
{{dsc inc|cpp/iterator/dsc make_const_iterator}}
{{dsc inc|cpp/iterator/dsc make_const_sentinel}}
{{dsc inc|cpp/iterator/dsc common_iterator}}
{{dsc inc|cpp/iterator/dsc default_sentinel_t}}
{{dsc inc|cpp/iterator/dsc counted_iterator}}
{{dsc inc|cpp/iterator/dsc unreachable_sentinel_t}}
{{dsc inc|cpp/iterator/dsc back_insert_iterator}}
{{dsc inc|cpp/iterator/dsc back_inserter}}
{{dsc inc|cpp/iterator/dsc front_insert_iterator}}
{{dsc inc|cpp/iterator/dsc front_inserter}}
{{dsc inc|cpp/iterator/dsc insert_iterator}}
{{dsc inc|cpp/iterator/dsc inserter}}
{{dsc end}}

===Stream iterators===
{{dsc begin}}
{{dsc inc|cpp/iterator/dsc istream_iterator}}
{{dsc inc|cpp/iterator/dsc ostream_iterator}}
{{dsc inc|cpp/iterator/dsc istreambuf_iterator}}
{{dsc inc|cpp/iterator/dsc ostreambuf_iterator}}
{{dsc end}}

===Iterator operations===
{{dsc begin}}
{{dsc header|iterator}}
{{dsc inc|cpp/iterator/dsc advance}}
{{dsc inc|cpp/iterator/dsc distance}}
{{dsc inc|cpp/iterator/dsc next}}
{{dsc inc|cpp/iterator/dsc prev}}
{{dsc inc|cpp/iterator/ranges/dsc advance}}
{{dsc inc|cpp/iterator/ranges/dsc distance}}
{{dsc inc|cpp/iterator/ranges/dsc next}}
{{dsc inc|cpp/iterator/ranges/dsc prev}}
{{dsc end}}

===Range access===
These non-member functions provide a generic interface for containers, plain arrays, and {{lc|std::initializer_list}}.
{{dsc begin}}
{{dsc header|array}}
{{dsc header|deque}}
{{dsc header|forward_list}}
{{dsc header|iterator}}
{{dsc header|list}}
{{dsc header|map}}
{{dsc header|regex}}
{{dsc header|set}}
{{dsc header|span}}
{{dsc header|string}}
{{dsc header|string_view}}
{{dsc header|unordered_map}}
{{dsc header|unordered_set}}
{{dsc header|vector}}
{{dsc namespace|std}}
{{dsc inc|cpp/iterator/dsc begin}}
{{dsc inc|cpp/iterator/dsc end}}
{{dsc inc|cpp/iterator/dsc rbegin}}
{{dsc inc|cpp/iterator/dsc rend}}
{{dsc inc|cpp/iterator/dsc size}}
{{dsc inc|cpp/iterator/dsc empty}}
{{dsc inc|cpp/iterator/dsc data}}
{{dsc end}}

===Defect reports===
{{dr list begin}}
{{dr list item|wg=cwg|dr=1181|std=C++98|before=array types could not be value types|after=they can}}
{{dr list item|wg=lwg|dr=208|std=C++98|before=past-the-end iterators were always non-singular|after=they can be singular}}
{{dr list item|wg=lwg|dr=278|std=C++98|before=the validity of an iterator was not defined|after=defined to be always non-singular}}
{{dr list item|wg=lwg|dr=324|std=C++98|before=output iterators had value types|after=output iterators have writable types instead}}
{{dr list item|wg=lwg|dr=407|std=C++98|before=singular iterators could not be destroyed|after=allowed}}
{{dr list item|wg=lwg|dr=408|paper=N3066|std=C++98|before=singular iterators could not be copied|after=allowed if they are value-initialized}}
{{dr list item|wg=lwg|dr=1158|paper=N3066|std=C++98|before={{named req|ForwardIterator}}, {{named req|BidirectionalIterator}}<br>and {{named req|RandomAccessIterator}}<br>always satisfy {{named req|OutputIterator}}|after=they might not satisfy {{named req|OutputIterator}}}}
{{dr list end}}

{{langlinks|ar|de|es|fr|it|ja|ko|pt|ru|tr|zh}}