Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/iterator"

From cppreference.com
< cpp
m (→‎Iterator categories: Kudos for table transposition. Trying to clarify legacy-iterators "write" status (in the table))
(Link update.)
 
(33 intermediate revisions by 10 users not shown)
Line 2: Line 2:
 
{{cpp/iterator/navbar}}
 
{{cpp/iterator/navbar}}
  
−
The iterator library provides definitions for iterators, as well as iterator traits, adaptors, and utility functions.
+
Iterators are a generalization of {{lt|cpp/language/pointer}}s that allow a C++ program to work with different data structures (for example, {{lt|cpp/container}}s{{rev inl|since=c++20| and {{lt|cpp/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 {{lt|cpp/language/function template}} that takes iterators works as well with regular pointers.
  
 
===Iterator categories===
 
===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}}}}.
+
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}}}}. (See also {{named req|Iterator}} 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 {{named req|RandomAccessIterator}}, so a pointer can be used anywhere a {{named req|RandomAccessIterator}} is expected.
+
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.
 
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.
  
−
{| class="wikitable"
+
{{rrev|since=c++20|
 +
Iterators are called ''constexpr'' iterators if all operations provided to meet iterator category requirements are {{ls|cpp/language/constexpr#constexpr function}}s.
 +
}}
 +
 
 +
{|class="wikitable"
 
!rowspan="3"|Iterator category
 
!rowspan="3"|Iterator category
−
!colspan="7"|Defined operations
+
!colspan="7"|Operations and storage requirement
−
|- style="text-align:center;"
+
|-style="text-align:center;"
−
|rowspan="2"|&nbsp;&nbsp;&nbsp;write&nbsp;&nbsp;&nbsp;
+
|rowspan="2"|{{nbsp|5}}write{{nbsp|5}}
−
|rowspan="2"|&nbsp;&nbsp;&nbsp;read&nbsp;&nbsp;&nbsp;
+
|rowspan="2"|{{nbsp|5}}read{{nbsp|5}}
 
|colspan="2"|increment
 
|colspan="2"|increment
−
|rowspan="2"|&nbsp;decrement&nbsp;
+
|rowspan="2"|{{nbsp}}decrement{{nbsp}}
−
|rowspan="2"|random access
+
|rowspan="2"|{{nbsp|3}}random{{nbsp|3}}<br>access
−
|rowspan="2"|contiguous storage
+
|rowspan="2"|{{nbsp}}contiguous{{nbsp}}<br>storage
−
|- style="text-align:center;"
+
|-style="text-align:center;"
−
|without multiple passes
+
|without<br>{{nbsp|3}}multiple{{nbsp|3}}<br>passes
−
|with multiple passes
+
|with<br>{{nbsp|3}}multiple{{nbsp|3}}<br>passes
−
|- style="text-align:center;"
+
|-style="text-align:center;"
 +
|{{named req|Iterator}}
 +
|
 +
|
 +
|{{yes|Required}}
 +
|
 +
|
 +
|
 +
|
 +
|-style="text-align:center;"
 
|{{named req|OutputIterator}}
 
|{{named req|OutputIterator}}
−
|{{yes}}
+
|{{yes|Required}}
 
|
 
|
−
|{{yes}}
+
|{{yes|Required}}
 
|
 
|
 
|
 
|
 
|
 
|
 
|
 
|
−
|- style="text-align:center;"
+
|-style="text-align:center;"
−
|{{named req|InputIterator}}
+
|{{named req|InputIterator}}<br>{{small|(mutable if supports write operation)}}
−
|{{maybe|1=<span title="Only if mutable">Yes*</span>}}
+
−
|{{yes}}
+
−
|{{yes}}
+
 
|
 
|
 +
|{{yes|Required}}
 +
|{{yes|Required}}
 
|
 
|
 
|
 
|
 
|
 
|
−
|- style="text-align:center;"
 
−
|{{named req|ForwardIterator}}
 
−
|{{maybe|1=<span title="Only if mutable">Yes*</span>}}
 
−
|{{yes}}
 
−
|{{yes}}
 
−
|{{yes}}
 
 
|
 
|
 +
|-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}}
 
−
|{{maybe|1=<span title="Only if mutable">Yes*</span>}}
 
−
|{{yes}}
 
−
|{{yes}}
 
−
|{{yes}}
 
−
|{{yes}}
 
 
|
 
|
 
|
 
|
−
|- style="text-align:center;"
+
|-style="text-align:center;"
−
|{{named req|RandomAccessIterator}}
+
|{{named req|BidirectionalIterator}}<br>{{small|(also satisfies {{named req|ForwardIterator}})}}
−
|{{maybe|1=<span title="Only if mutable">Yes*</span>}}
+
−
|{{yes}}
+
−
|{{yes}}
+
−
|{{yes}}
+
−
|{{yes}}
+
−
|{{yes}}
+
 
|
 
|
−
|- style="text-align:center;"
+
|{{yes|Required}}
−
|{{named req|ContiguousIterator}}
+
|{{yes|Required}}
−
|{{maybe|1=<span title="Only if mutable">Yes*</span>}}
+
|{{yes|Required}}
−
|{{yes}}
+
|{{yes|Required}}
−
|{{yes}}
+
|
−
|{{yes}}
+
|
−
|{{yes}}
+
|-style="text-align:center;"
−
|{{yes}}
+
|{{named req|RandomAccessIterator}}<br>{{small|(also satisfies {{named req|BidirectionalIterator}})}}
−
|{{yes}}
+
|
 +
|{{yes|Required}}
 +
|{{yes|Required}}
 +
|{{yes|Required}}
 +
|{{yes|Required}}
 +
|{{yes|Required}}
 +
|
 +
|-style="text-align:center;"
 +
|{{nbsp|3}}{{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.
  
−
Note: {{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.
+
===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.
  
−
===Iterator concepts===
+
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}}.
−
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.
+
 
 +
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|{{rl|is-integer-like|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'' can be denoted by either
 +
* {{range|i|s}}, with 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
 +
* {{counted range|i|n}}, with 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.
 +
 
 +
=====Iterator-sentinel 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.
 +
 
 +
{{anchor|Iterator concepts}}
 +
 
 +
===Iterator concepts {{mark since c++20}}===
 +
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 begin}}
 
{{dsc namespace|std}}
 
{{dsc namespace|std}}
−
{{dsc inc| cpp/iterator/dsc indirectly_readable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_readable}}
−
{{dsc inc| cpp/iterator/dsc indirectly_writable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_writable}}
−
{{dsc inc| cpp/iterator/dsc weakly_incrementable}}
+
{{dsc inc|cpp/iterator/dsc weakly_incrementable}}
−
{{dsc inc| cpp/iterator/dsc incrementable}}
+
{{dsc inc|cpp/iterator/dsc incrementable}}
−
{{dsc inc| cpp/iterator/dsc input_or_output_iterator}}
+
{{dsc inc|cpp/iterator/dsc is-integer-like}}
−
{{dsc inc| cpp/iterator/dsc sentinel_for}}
+
{{dsc inc|cpp/iterator/dsc input_or_output_iterator}}
−
{{dsc inc| cpp/iterator/dsc sized_sentinel_for}}
+
{{dsc inc|cpp/iterator/dsc sentinel_for}}
−
{{dsc inc| cpp/iterator/dsc input_iterator}}
+
{{dsc inc|cpp/iterator/dsc sized_sentinel_for}}
−
{{dsc inc| cpp/iterator/dsc output_iterator}}
+
{{dsc inc|cpp/iterator/dsc input_iterator}}
−
{{dsc inc| cpp/iterator/dsc forward_iterator}}
+
{{dsc inc|cpp/iterator/dsc output_iterator}}
−
{{dsc inc| cpp/iterator/dsc bidirectional_iterator}}
+
{{dsc inc|cpp/iterator/dsc forward_iterator}}
−
{{dsc inc| cpp/iterator/dsc random_access_iterator}}
+
{{dsc inc|cpp/iterator/dsc bidirectional_iterator}}
−
{{dsc inc| cpp/iterator/dsc contiguous_iterator}}
+
{{dsc inc|cpp/iterator/dsc random_access_iterator}}
 +
{{dsc inc|cpp/iterator/dsc contiguous_iterator}}
 
{{dsc end}}
 
{{dsc end}}
  
Line 105: Line 181:
 
{{dsc begin}}
 
{{dsc begin}}
 
{{dsc namespace|std}}
 
{{dsc namespace|std}}
−
{{dsc inc| cpp/iterator/dsc incrementable_traits}}
+
{{dsc inc|cpp/iterator/dsc incrementable_traits}}
−
{{dsc inc| cpp/iterator/dsc indirectly_readable_traits}}
+
{{dsc inc|cpp/iterator/dsc indirectly_readable_traits}}
−
{{dsc inc| cpp/iterator/dsc iter_t}}
+
{{dsc inc|cpp/iterator/dsc iter_t}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Iterator primitives===
 
===Iterator primitives===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/iterator/dsc iterator_traits}}
+
{{dsc inc|cpp/iterator/dsc iterator_traits}}
−
{{dsc inc | cpp/iterator/dsc iterator_tags}}
+
{{dsc inc|cpp/iterator/dsc iterator_tags}}
−
{{dsc inc | cpp/iterator/dsc iterator}}
+
{{dsc inc|cpp/iterator/dsc iterator}}
 
{{dsc end}}
 
{{dsc end}}
  
Line 120: Line 196:
 
{{dsc begin}}
 
{{dsc begin}}
 
{{dsc namespace|std::ranges}}
 
{{dsc namespace|std::ranges}}
−
{{dsc inc| cpp/iterator/ranges/dsc iter_move}}
+
{{dsc inc|cpp/iterator/ranges/dsc iter_move}}
−
{{dsc inc| cpp/iterator/ranges/dsc iter_swap}}
+
{{dsc inc|cpp/iterator/ranges/dsc iter_swap}}
 
{{dsc end}}
 
{{dsc end}}
  
−
===Algorithm concepts and utilities===
+
{{anchor|Algorithm concepts and utilities}}
−
C++20 also provides a set of concepts and related utility templates designed to ease constraining common algorithm operations.
+
===Algorithm concepts and utilities {{mark since c++20}}===
 +
A set of concepts and related utility templates designed to ease constraining common algorithm operations.
  
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc header | iterator}}
+
{{dsc header|iterator}}
−
{{dsc namespace | std }}
+
{{dsc namespace|std}}
−
{{dsc h2 | Indirect callable concepts}}
+
{{dsc h2|Indirect callable concepts}}
−
{{dsc inc | cpp/iterator/dsc indirectly_unary_invocable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_unary_invocable}}
−
{{dsc inc | cpp/iterator/dsc indirect_unary_predicate}}
+
{{dsc inc|cpp/iterator/dsc indirect_unary_predicate}}
−
{{dsc inc | cpp/iterator/dsc indirect_binary_predicate}}
+
{{dsc inc|cpp/iterator/dsc indirect_binary_predicate}}
−
{{dsc inc | cpp/iterator/dsc indirect_equivalence_relation}}
+
{{dsc inc|cpp/iterator/dsc indirect_equivalence_relation}}
−
{{dsc inc | cpp/iterator/dsc indirect_strict_weak_order}}
+
{{dsc inc|cpp/iterator/dsc indirect_strict_weak_order}}
−
{{dsc h2 | Common algorithm requirements}}
+
{{dsc h2|Common algorithm requirements}}
−
{{dsc inc | cpp/iterator/dsc indirectly_movable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_movable}}
−
{{dsc inc | cpp/iterator/dsc indirectly_movable_storable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_movable_storable}}
−
{{dsc inc | cpp/iterator/dsc indirectly_copyable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_copyable}}
−
{{dsc inc | cpp/iterator/dsc indirectly_copyable_storable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_copyable_storable}}
−
{{dsc inc | cpp/iterator/dsc indirectly_swappable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_swappable}}
−
{{dsc inc | cpp/iterator/dsc indirectly_comparable}}
+
{{dsc inc|cpp/iterator/dsc indirectly_comparable}}
−
{{dsc inc | cpp/iterator/dsc permutable}}
+
{{dsc inc|cpp/iterator/dsc permutable}}
−
{{dsc inc | cpp/iterator/dsc mergeable}}
+
{{dsc inc|cpp/iterator/dsc mergeable}}
−
{{dsc inc | cpp/iterator/dsc sortable}}
+
{{dsc inc|cpp/iterator/dsc sortable}}
−
{{dsc h2 | Utilities}}
+
{{dsc h2|Utilities}}
−
{{dsc inc | cpp/iterator/dsc indirect_result_t}}
+
{{dsc inc|cpp/iterator/dsc indirect_result_t}}
−
{{dsc inc | cpp/iterator/dsc projected}}
+
{{dsc inc|cpp/iterator/dsc projected}}
 +
{{dsc inc|cpp/iterator/dsc projected_value_t}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Iterator adaptors===
 
===Iterator adaptors===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/iterator/dsc reverse_iterator}}
+
{{dsc inc|cpp/iterator/dsc reverse_iterator}}
−
{{dsc inc | cpp/iterator/dsc make_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 back_insert_iterator}}
−
{{dsc inc | cpp/iterator/dsc make_move_iterator}}
+
{{dsc inc|cpp/iterator/dsc back_inserter}}
−
{{dsc inc | cpp/iterator/dsc common_iterator}}
+
{{dsc inc|cpp/iterator/dsc front_insert_iterator}}
−
{{dsc inc | cpp/iterator/dsc default_sentinel_t}}
+
{{dsc inc|cpp/iterator/dsc front_inserter}}
−
{{dsc inc | cpp/iterator/dsc counted_iterator}}
+
{{dsc inc|cpp/iterator/dsc insert_iterator}}
−
{{dsc inc | cpp/iterator/dsc unreachable_sentinel_t}}
+
{{dsc inc|cpp/iterator/dsc inserter}}
−
{{dsc inc | cpp/iterator/dsc back_insert_iterator}}
+
 
−
{{dsc inc | cpp/iterator/dsc back_inserter}}
+
{{dsc inc|cpp/iterator/dsc basic_const_iterator}}
−
{{dsc inc | cpp/iterator/dsc front_insert_iterator}}
+
{{dsc inc|cpp/iterator/dsc const_iterator}}
−
{{dsc inc | cpp/iterator/dsc front_inserter}}
+
{{dsc inc|cpp/iterator/dsc const_sentinel}}
−
{{dsc inc | cpp/iterator/dsc insert_iterator}}
+
{{dsc inc|cpp/iterator/dsc make_const_iterator}}
−
{{dsc inc | cpp/iterator/dsc inserter}}
+
{{dsc inc|cpp/iterator/dsc make_const_sentinel}}
 +
 
 +
{{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 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 end}}
 
{{dsc end}}
  
 
===Stream iterators===
 
===Stream iterators===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/iterator/dsc istream_iterator}}
+
{{dsc inc|cpp/iterator/dsc istream_iterator}}
−
{{dsc inc | cpp/iterator/dsc ostream_iterator}}
+
{{dsc inc|cpp/iterator/dsc ostream_iterator}}
−
{{dsc inc | cpp/iterator/dsc istreambuf_iterator}}
+
{{dsc inc|cpp/iterator/dsc istreambuf_iterator}}
−
{{dsc inc | cpp/iterator/dsc ostreambuf_iterator}}
+
{{dsc inc|cpp/iterator/dsc ostreambuf_iterator}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Iterator operations===
 
===Iterator operations===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc header | iterator}}
+
{{dsc header|iterator}}
−
{{dsc inc | cpp/iterator/dsc advance}}
+
{{dsc inc|cpp/iterator/dsc advance}}
−
{{dsc inc | cpp/iterator/dsc distance}}
+
{{dsc inc|cpp/iterator/dsc distance}}
−
{{dsc inc | cpp/iterator/dsc next}}
+
{{dsc inc|cpp/iterator/dsc next}}
−
{{dsc inc | cpp/iterator/dsc prev}}
+
{{dsc inc|cpp/iterator/dsc prev}}
−
{{dsc inc | cpp/iterator/ranges/dsc advance}}
+
{{dsc inc|cpp/iterator/ranges/dsc advance}}
−
{{dsc inc | cpp/iterator/ranges/dsc distance}}
+
{{dsc inc|cpp/iterator/ranges/dsc distance}}
−
{{dsc inc | cpp/iterator/ranges/dsc next}}
+
{{dsc inc|cpp/iterator/ranges/dsc next}}
−
{{dsc inc | cpp/iterator/ranges/dsc prev}}
+
{{dsc inc|cpp/iterator/ranges/dsc prev}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Range access===
 
===Range access===
−
These non-member functions provide a generic interface for containers, plain arrays, and {{lc|std::initializer_list}}.
+
These non-member function templates provide a generic interface for containers, plain arrays, and {{lc|std::initializer_list}}.
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc header | array}}
+
{{dsc header|array}}
−
{{dsc header | deque}}
+
{{dsc header|deque}}
−
{{dsc header | forward_list}}
+
{{dsc header|flat_map}}
−
{{dsc header | iterator}}
+
{{dsc header|flat_set}}
−
{{dsc header | list}}
+
{{dsc header|forward_list}}
−
{{dsc header | map}}
+
{{dsc header|inplace_vector}}
−
{{dsc header | regex}}
+
{{dsc header|iterator}}
−
{{dsc header | set}}
+
{{dsc header|list}}
−
{{dsc header | span}}
+
{{dsc header|map}}
−
{{dsc header | string}}
+
{{dsc header|regex}}
−
{{dsc header | string_view}}
+
{{dsc header|set}}
−
{{dsc header | unordered_map}}
+
{{dsc header|span}}
−
{{dsc header | unordered_set}}
+
{{dsc header|string}}
−
{{dsc header | vector}}
+
{{dsc header|string_view}}
−
{{dsc namespace | std}}
+
{{dsc header|unordered_map}}
−
{{dsc inc | cpp/iterator/dsc begin}}
+
{{dsc header|unordered_set}}
−
{{dsc inc | cpp/iterator/dsc end}}
+
{{dsc header|vector}}
−
{{dsc inc | cpp/iterator/dsc rbegin}}
+
{{dsc namespace|std}}
−
{{dsc inc | cpp/iterator/dsc rend}}
+
{{dsc inc|cpp/iterator/dsc begin}}
−
{{dsc inc | cpp/iterator/dsc size}}
+
{{dsc inc|cpp/iterator/dsc end}}
−
{{dsc inc | cpp/iterator/dsc empty}}
+
{{dsc inc|cpp/iterator/dsc rbegin}}
−
{{dsc inc | cpp/iterator/dsc data}}
+
{{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}}
 
{{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=1185|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 item|wg=lwg|dr=1210|paper=N3066|std=C++98|before=the definition of iterator singularity and<br>reachability depended on containers|after=depend on sequences instead}}
 +
{{dr list item|wg=lwg|dr=3009|std=C++17|before={{header|string_view}} did not provide the<br>range access function templates|after=provides these templates}}
 +
{{dr list item|wg=lwg|dr=3987|std=C++23|before={{header|flat_map}} and {{header|flat_set}} did not<br>provide the range access function templates|after=provide these templates}}
 +
{{dr list end}}
  
 
{{langlinks|ar|de|es|fr|it|ja|ko|pt|ru|tr|zh}}
 
{{langlinks|ar|de|es|fr|it|ja|ko|pt|ru|tr|zh}}

Latest revision as of 18:50, 9 September 2024

 
C++
 
Iterator library
Iterator concepts
Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (for example, containers and ranges(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 function template that takes iterators works as well with regular pointers.

Contents

[edit] Iterator categories

There are five(until C++17)six(since C++17) kinds of iterators: LegacyInputIterator, LegacyOutputIterator, LegacyForwardIterator, LegacyBidirectionalIterator, LegacyRandomAccessIterator, and LegacyContiguousIterator(since C++17). (See also LegacyIterator 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 LegacyRandomAccessIterator, so a pointer can be used anywhere a LegacyRandomAccessIterator is expected.

All of the iterator categories (except LegacyOutputIterator) can be organized into a hierarchy, where more powerful iterator categories (e.g. LegacyRandomAccessIterator) support the operations of less powerful categories (e.g. LegacyInputIterator). If an iterator falls into one of these categories and also satisfies the requirements of LegacyOutputIterator, 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 constexpr functions.

(since C++20)
Iterator category Operations and storage requirement
     write           read      increment  decrement     random   
access 		 contiguous 
storage
without
   multiple   
passes 		with
   multiple   
passes
LegacyIterator Required
LegacyOutputIterator Required Required
LegacyInputIterator
(mutable if supports write operation) 		Required Required
LegacyForwardIterator
(also satisfies LegacyInputIterator) 		Required Required Required
LegacyBidirectionalIterator
(also satisfies LegacyForwardIterator) 		Required Required Required Required
LegacyRandomAccessIterator
(also satisfies LegacyBidirectionalIterator) 		Required Required Required Required Required
   LegacyContiguousIterator[1]
(also satisfies LegacyRandomAccessIterator) 		Required Required Required Required Required Required
  1. ↑ LegacyContiguousIterator category was only formally specified in C++17, but the iterators of std::vector, std::basic_string, std::array, and std::valarray, 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.

[edit] Definitions

[edit] Types and writability

An input iterator i supports the expression *i, resulting in a value of some object type 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)indirectly_writable(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 X for which equality is defined(until C++20), there is a corresponding signed integer(until C++20)integer-like(since C++20) type called the difference type of the iterator.

[edit] Dereferenceability and validity

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. 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 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 DefaultConstructible requirements, using a value-initialized 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.

[edit] 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 sentinel s 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 range

An 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 range

A counted range i + [​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.

[edit] Iterator concepts (since C++20)

A new system of iterators based on concepts 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) [edit]
(C++20)
 specifies that a value can be written to an iterator's referenced object
(concept) [edit]
(C++20)
 specifies that a semiregular type can be incremented with pre- and post-increment operators
(concept) [edit]
(C++20)
 specifies that the increment operation on a weakly_incrementable type is equality-preserving and that the type is equality_comparable
(concept) [edit]
(C++20)(C++20)
 specifies that a type behaves as a (signed) integer type
(exposition-only concept*)[edit]
(C++20)
 specifies that objects of a type can be incremented and dereferenced
(concept) [edit]
(C++20)
 specifies a type is a sentinel for an input_or_output_iterator type
(concept) [edit]
(C++20)
 specifies that the - operator can be applied to an iterator and a sentinel to calculate their difference in constant time
(concept) [edit]
(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) [edit]
(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) [edit]
(C++20)
 specifies that an input_iterator is a forward iterator, supporting equality comparison and multi-pass
(concept) [edit]
(C++20)
 specifies that a forward_iterator is a bidirectional iterator, supporting movement backwards
(concept) [edit]
(C++20)
 specifies that a bidirectional_iterator is a random-access iterator, supporting advancement in constant time and subscripting
(concept) [edit]
(C++20)
 specifies that a random_access_iterator is a contiguous iterator, referring to elements that are contiguous in memory
(concept) [edit]

[edit] Iterator associated types

Defined in namespace std
(C++20)
 computes the difference type of a weakly_incrementable type
(class template) [edit]
(C++20)
 computes the value type of an indirectly_readable type
(class template) [edit]
(C++20)(C++20)(C++23)(C++20)(C++20)(C++20)
 computes the associated types of an iterator
(alias template)[edit]

[edit] Iterator primitives

 provides uniform interface to the properties of an iterator
(class template) [edit]
(C++20)
 empty class types used to indicate iterator categories
(class) [edit]
(deprecated in C++17)
 base class to ease the definition of required types for simple iterators
(class template) [edit]

[edit] Iterator customization points

Defined in namespace std::ranges
(C++20)
 casts the result of dereferencing an object to its associated rvalue reference type
(customization point object)[edit]
(C++20)
 swaps the values referenced by two dereferenceable objects
(customization point object)[edit]

[edit] 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 <iterator>
Defined in namespace std
Indirect callable concepts
(C++20)(C++20)
 specifies that a callable type can be invoked with the result of dereferencing an indirectly_readable type
(concept) [edit]
(C++20)
 specifies that a callable type, when invoked with the result of dereferencing an indirectly_readable type, satisfies predicate
(concept) [edit]
(C++20)
 specifies that a callable type, when invoked with the result of dereferencing two indirectly_readable types, satisfies predicate
(concept) [edit]
(C++20)
 specifies that a callable type, when invoked with the result of dereferencing two indirectly_readable types, satisfies equivalence_relation
(concept) [edit]
(C++20)
 specifies that a callable type, when invoked with the result of dereferencing two indirectly_readable types, satisfies strict_weak_order
(concept) [edit]
Common algorithm requirements
(C++20)
 specifies that values may be moved from an indirectly_readable type to an indirectly_writable type
(concept) [edit]
(C++20)
 specifies that values may be moved from an indirectly_readable type to an indirectly_writable type and that the move may be performed via an intermediate object
(concept) [edit]
(C++20)
 specifies that values may be copied from an indirectly_readable type to an indirectly_writable type
(concept) [edit]
(C++20)
 specifies that values may be copied from an indirectly_readable type to an indirectly_writable type and that the copy may be performed via an intermediate object
(concept) [edit]
(C++20)
 specifies that the values referenced by two indirectly_readable types can be swapped
(concept) [edit]
(C++20)
 specifies that the values referenced by two indirectly_readable types can be compared
(concept) [edit]
(C++20)
 specifies the common requirements of algorithms that reorder elements in place
(concept) [edit]
(C++20)
 specifies the requirements of algorithms that merge sorted sequences into an output sequence by copying elements
(concept) [edit]
(C++20)
 specifies the common requirements of algorithms that permute sequences into ordered sequences
(concept) [edit]
Utilities
(C++20)
 computes the result of invoking a callable object on the result of dereferencing some set of indirectly_readable types
(alias template)[edit]
(C++20)
 helper template for specifying the constraints on algorithms that accept projections
(class template) [edit]
(C++26)
 computes the value type of an indirectly_readable type by projection
(alias template)[edit]

[edit] Iterator adaptors

 iterator adaptor for reverse-order traversal
(class template) [edit]
(C++14)
 creates a std::reverse_iterator of type inferred from the argument
(function template) [edit]
iterator adaptor for insertion at the end of a container
(class template) [edit]
creates a std::back_insert_iterator of type inferred from the argument
(function template) [edit]
iterator adaptor for insertion at the front of a container
(class template) [edit]
creates a std::front_insert_iterator of type inferred from the argument
(function template) [edit]
iterator adaptor for insertion into a container
(class template) [edit]
creates a std::insert_iterator of type inferred from the argument
(function template) [edit]
(C++23)
 iterator adaptor that converts an iterator into a constant iterator
(class template) [edit]
(C++23)
 computes a constant iterator type for a given type
(alias template)[edit]
(C++23)
 computes a sentinel type to be used with constant iterators
(alias template)[edit]
(C++23)
 creates a std::const_iterator of type inferred from the argument
(function template) [edit]
(C++23)
 creates a std::const_sentinel of type inferred from the argument
(function template) [edit]
(C++11)
 iterator adaptor which dereferences to an rvalue
(class template) [edit]
(C++20)
 sentinel adaptor for std::move_iterator
(class template) [edit]
(C++11)
 creates a std::move_iterator of type inferred from the argument
(function template) [edit]
(C++20)
 adapts an iterator type and its sentinel into a common iterator type
(class template) [edit]
(C++20)
 default sentinel for use with iterators that know the bound of their range
(class) [edit]
(C++20)
 iterator adaptor that tracks the distance to the end of the range
(class template) [edit]
(C++20)
 sentinel that always compares unequal to any weakly_incrementable type
(class) [edit]

[edit] Stream iterators

 input iterator that reads from std::basic_istream
(class template) [edit]
output iterator that writes to std::basic_ostream
(class template) [edit]
input iterator that reads from std::basic_streambuf
(class template) [edit]
output iterator that writes to std::basic_streambuf
(class template) [edit]

[edit] Iterator operations

Defined in header <iterator>
advances an iterator by given distance
(function template) [edit]
returns the distance between two iterators
(function template) [edit]
(C++11)
 increment an iterator
(function template) [edit]
(C++11)
 decrement an iterator
(function template) [edit]
(C++20)
 advances an iterator by given distance or to a given bound
(niebloid)[edit]
(C++20)
 returns the distance between an iterator and a sentinel, or between the beginning and end of a range
(niebloid)[edit]
(C++20)
 increment an iterator by a given distance or to a bound
(niebloid)[edit]
(C++20)
 decrement an iterator by a given distance or to a bound
(niebloid)[edit]

[edit] Range access

These non-member function templates provide a generic interface for containers, plain arrays, and std::initializer_list.

Defined in header <array>
Defined in header <deque>
Defined in header <flat_map>
Defined in header <flat_set>
Defined in header <forward_list>
Defined in header <inplace_vector>
Defined in header <iterator>
Defined in header <list>
Defined in header <map>
Defined in header <regex>
Defined in header <set>
Defined in header <span>
Defined in header <string>
Defined in header <string_view>
Defined in header <unordered_map>
Defined in header <unordered_set>
Defined in header <vector>
Defined in namespace std
(C++11)(C++14)
 returns an iterator to the beginning of a container or array
(function template) [edit]
(C++11)(C++14)
 returns an iterator to the end of a container or array
(function template) [edit]
(C++14)
 returns a reverse iterator to the beginning of a container or array
(function template) [edit]
(C++14)
 returns a reverse end iterator for a container or array
(function template) [edit]
(C++17)(C++20)
 returns the size of a container or array
(function template) [edit]
(C++17)
 checks whether the container is empty
(function template) [edit]
(C++17)
 obtains the pointer to the underlying array
(function template) [edit]

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
CWG 1181 C++98 array types could not be value types they can
LWG 208 C++98 past-the-end iterators were always non-singular they can be singular
LWG 278 C++98 the validity of an iterator was not defined defined to be always non-singular
LWG 324 C++98 output iterators had value types output iterators have writable types instead
LWG 407 C++98 singular iterators could not be destroyed allowed
LWG 408
(N3066) 		C++98 singular iterators could not be copied allowed if they are value-initialized
LWG 1185
(N3066) 		C++98 LegacyForwardIterator, LegacyBidirectionalIterator
and LegacyRandomAccessIterator
always satisfy LegacyOutputIterator 		they might not satisfy LegacyOutputIterator
LWG 1210
(N3066) 		C++98 the definition of iterator singularity and
reachability depended on containers 		depend on sequences instead
LWG 3009 C++17 <string_view> did not provide the
range access function templates 		provides these templates
LWG 3987 C++23 <flat_map> and <flat_set> did not
provide the range access function templates 		provide these templates
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/iterator&oldid=175988"