depish/cppdraft_translate
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
cppdraft_translate/cppdraft/iterator/cpp17.md
Leonov Artur (Depish) 043225d523 Init
2025-10-25 03:02:53 +03:00

322 lines
20 KiB
Markdown
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

[iterator.cpp17]
# 24 Iterators library [[iterators]](./#iterators)
## 24.3 Iterator requirements [[iterator.requirements]](iterator.requirements#iterator.cpp17)
### 24.3.5 C++17 iterator requirements [iterator.cpp17]
#### [24.3.5.1](#general) General [[iterator.cpp17.general]](iterator.cpp17.general)
[1](#general-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L1992)
In the following sections,a andb denote values of typeX or const X,difference_type and reference refer to the
types iterator_traits<X>​::​difference_type anditerator_traits<X>​::​reference, respectively,n denotes a value ofdifference_type,u,tmp,
andm denote identifiers,r denotes a value ofX&,t denotes a value of value typeT,o denotes a value of some type that is writable to the output iterator[.](#general-1.sentence-1)
[*Note [1](#general-note-1)*:
For an iterator type X there must be an instantiation
of iterator_traits<X> ([[iterator.traits]](iterator.traits "24.3.2.3 Iterator traits"))[.](#general-1.sentence-2)
— *end note*]
#### [24.3.5.2](#iterator.iterators) *Cpp17Iterator* [[iterator.iterators]](iterator.iterators)
[1](#iterator.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2025)
The *Cpp17Iterator* requirements form the basis of the iterator
taxonomy; every iterator meets the *Cpp17Iterator* requirements[.](#iterator.iterators-1.sentence-1)
This
set of requirements specifies operations for dereferencing and incrementing
an iterator[.](#iterator.iterators-1.sentence-2)
Most algorithms will require additional operations to
read ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")) or write ([[output.iterators]](#output.iterators "24.3.5.4 Output iterators")) values, or
to provide a richer set of iterator movements ([[forward.iterators]](#forward.iterators "24.3.5.5 Forward iterators"), [[bidirectional.iterators]](#bidirectional.iterators "24.3.5.6 Bidirectional iterators"), [[random.access.iterators]](#random.access.iterators "24.3.5.7 Random access iterators"))[.](#iterator.iterators-1.sentence-3)
[2](#iterator.iterators-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2034)
A type X meets the *Cpp17Iterator* requirements if
- [(2.1)](#iterator.iterators-2.1)
X meets the *Cpp17CopyConstructible*, *Cpp17CopyAssignable*, *Cpp17Swappable*, and*Cpp17Destructible* requirements ([[utility.arg.requirements]](utility.arg.requirements "16.4.4.2 Template argument requirements"), [[swappable.requirements]](swappable.requirements "16.4.4.3 Swappable requirements")), and
- [(2.2)](#iterator.iterators-2.2)
iterator_traits<X>​::​difference_type is a signed integer type or void, and
- [(2.3)](#iterator.iterators-2.3)
the expressions in Table [78](#tab:iterator "Table 78: Cpp17Iterator requirements") are valid and have
the indicated semantics[.](#iterator.iterators-2.sentence-1)
Table [78](#tab:iterator) — *Cpp17Iterator* requirements [[tab:iterator]](./tab:iterator)
| [🔗](#tab:iterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:iterator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:iterator-row-3)<br>*r | unspecified | | *Preconditions*: r is dereferenceable[.](#tab:iterator-row-3-column-4-sentence-1) |
| [🔗](#tab:iterator-row-4)<br>++r | X& | | |
#### [24.3.5.3](#input.iterators) Input iterators [[input.iterators]](input.iterators)
[1](#input.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2067)
A class or pointer typeX meets the requirements of an input iterator for the value typeT ifX meets the *Cpp17Iterator* ([[iterator.iterators]](#iterator.iterators "24.3.5.2 Cpp17Iterator")) and*Cpp17EqualityComparable* (Table [28](utility.arg.requirements#tab:cpp17.equalitycomparable "Table 28: Cpp17EqualityComparable requirements")) requirements and
the expressions in Table [79](#tab:inputiterator "Table 79: Cpp17InputIterator requirements (in addition to Cpp17Iterator)") are valid and have
the indicated semantics[.](#input.iterators-1.sentence-1)
[2](#input.iterators-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2078)
In Table [79](#tab:inputiterator "Table 79: Cpp17InputIterator requirements (in addition to Cpp17Iterator)"), the term[*the domain of ==*](#def:the_domain_of_==) is used in the ordinary mathematical sense to denote
the set of values over which== is (required to be) defined[.](#input.iterators-2.sentence-1)
This set can change over time[.](#input.iterators-2.sentence-2)
Each algorithm places additional requirements on the domain of== for the iterator values it uses[.](#input.iterators-2.sentence-3)
These requirements can be inferred from the uses that algorithm
makes of == and !=[.](#input.iterators-2.sentence-4)
[*Example [1](#input.iterators-example-1)*:
The call find(a,b,x) is defined only if the value of a has the property *p* defined as follows:b has property *p* and a value i has property *p* if
(*i==x)
or if
(*i!=x and++i has property*p*)[.](#input.iterators-2.sentence-5)
— *end example*]
Table [79](#tab:inputiterator) — *Cpp17InputIterator* requirements (in addition to *Cpp17Iterator*) [[tab:inputiterator]](./tab:inputiterator)
| [🔗](#tab:inputiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:inputiterator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:inputiterator-row-3)<br>a != b | decltype(a != b) models *boolean-testable* | !(a == b) | *Preconditions*: (a, b) is in the domain of ==[.](#tab:inputiterator-row-3-column-4-sentence-1) |
| [🔗](#tab:inputiterator-row-4)<br>*a | reference, convertible to T | | *Preconditions*: a is dereferenceable[.](#tab:inputiterator-row-4-column-4-sentence-1)<br> The expression (void)*a, *a is equivalent to *a[.](#tab:inputiterator-row-4-column-4-sentence-2)<br> If a == b and (a, b) is in the domain of == then *a is equivalent to *b[.](#tab:inputiterator-row-4-column-4-sentence-3) |
| [🔗](#tab:inputiterator-row-5)<br>a->m | | (*a).m | *Preconditions*: a is dereferenceable[.](#tab:inputiterator-row-5-column-4-sentence-1) |
| [🔗](#tab:inputiterator-row-6)<br>++r | X& | | *Preconditions*: r is dereferenceable[.](#tab:inputiterator-row-6-column-4-sentence-1)<br> *Postconditions*: r is dereferenceable or r is past-the-end; any copies of the previous value of r are no longer required to be dereferenceable nor to be in the domain of ==[.](#tab:inputiterator-row-6-column-4-sentence-2) |
| [🔗](#tab:inputiterator-row-7)<br>(void)r++ | | | equivalent to (void)++r |
| [🔗](#tab:inputiterator-row-8)<br>*r++ | convertible to T | { T tmp = *r; ++r; return tmp; } | |
[3](#input.iterators-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2155)
*Recommended practice*: The implementation of an algorithm on input iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single pass algorithm[.](#input.iterators-3.sentence-1)
[*Note [1](#input.iterators-note-1)*:
For input iterators, a == b does not imply ++a == ++b[.](#input.iterators-3.sentence-2)
(Equality does not guarantee the substitution property or referential transparency[.](#input.iterators-3.sentence-3))
Value type T is not required to be a *Cpp17CopyAssignable* type (Table [34](utility.arg.requirements#tab:cpp17.copyassignable "Table 34: Cpp17CopyAssignable requirements (in addition to Cpp17MoveAssignable)"))[.](#input.iterators-3.sentence-4)
Such an algorithm can be used with istreams as the source of the input data through theistream_iterator class template[.](#input.iterators-3.sentence-5)
— *end note*]
#### [24.3.5.4](#output.iterators) Output iterators [[output.iterators]](output.iterators)
[1](#output.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2174)
A class or pointer typeX meets the requirements of an output iterator
if X meets the *Cpp17Iterator* requirements ([[iterator.iterators]](#iterator.iterators "24.3.5.2 Cpp17Iterator"))
and the expressions in Table [80](#tab:outputiterator "Table 80: Cpp17OutputIterator requirements (in addition to Cpp17Iterator)") are valid and have the indicated semantics[.](#output.iterators-1.sentence-1)
Table [80](#tab:outputiterator) — *Cpp17OutputIterator* requirements (in addition to *Cpp17Iterator*) [[tab:outputiterator]](./tab:outputiterator)
| [🔗](#tab:outputiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:outputiterator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:outputiterator-row-3)<br>*r = o | result is not used | | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-3-column-4-sentence-1)<br> *Postconditions*: r is incrementable[.](#tab:outputiterator-row-3-column-4-sentence-2) |
| [🔗](#tab:outputiterator-row-4)<br>++r | X& | | addressof(r) == addressof(++r)[.](#tab:outputiterator-row-4-column-4-sentence-1)<br> *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-4-column-4-sentence-2)<br> *Postconditions*: r is incrementable[.](#tab:outputiterator-row-4-column-4-sentence-3) |
| [🔗](#tab:outputiterator-row-5)<br>r++ | convertible to const X& | { X tmp = r; ++r; return tmp; } | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-5-column-4-sentence-1)<br> *Postconditions*: r is incrementable[.](#tab:outputiterator-row-5-column-4-sentence-2) |
| [🔗](#tab:outputiterator-row-6)<br>*r++ = o | result is not used | | *Remarks*: After this operation r is not required to be dereferenceable[.](#tab:outputiterator-row-6-column-4-sentence-1)<br> *Postconditions*: r is incrementable[.](#tab:outputiterator-row-6-column-4-sentence-2) |
[2](#output.iterators-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2216)
*Recommended practice*: The implementation of an algorithm on output iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single-pass algorithm[.](#output.iterators-2.sentence-1)
[*Note [1](#output.iterators-note-1)*:
The only valid use of an operator* is on the left side of the assignment statement[.](#output.iterators-2.sentence-2)
Assignment through the same value of the iterator happens only once[.](#output.iterators-2.sentence-3)
Equality and inequality are not necessarily defined[.](#output.iterators-2.sentence-4)
— *end note*]
#### [24.3.5.5](#forward.iterators) Forward iterators [[forward.iterators]](forward.iterators)
[1](#forward.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2230)
A class or pointer typeX meets the *Cpp17ForwardIterator* requirements if
- [(1.1)](#forward.iterators-1.1)
X meets the *Cpp17InputIterator* requirements ([[input.iterators]](#input.iterators "24.3.5.3 Input iterators")),
- [(1.2)](#forward.iterators-1.2)
X meets the *Cpp17DefaultConstructible* requirements ([[utility.arg.requirements]](utility.arg.requirements "16.4.4.2 Template argument requirements")),
- [(1.3)](#forward.iterators-1.3)
if X is a mutable iterator, reference is a reference to T;
if X is a constant iterator, reference is a reference to const T,
- [(1.4)](#forward.iterators-1.4)
the expressions in Table [81](#tab:forwarditerator "Table 81: Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator)") are valid and have the indicated semantics, and
- [(1.5)](#forward.iterators-1.5)
objects of type X offer the multi-pass guarantee, described below[.](#forward.iterators-1.sentence-1)
[2](#forward.iterators-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2249)
The domain of == for forward iterators is that of iterators over the same
underlying sequence[.](#forward.iterators-2.sentence-1)
However, value-initialized iterators may be compared and
shall compare equal to other value-initialized iterators of the same type[.](#forward.iterators-2.sentence-2)
[*Note [1](#forward.iterators-note-1)*:
Value-initialized iterators behave as if they refer past the end of
the same empty sequence[.](#forward.iterators-2.sentence-3)
— *end note*]
[3](#forward.iterators-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2258)
Two dereferenceable iterators a and b of type X offer the[*multi-pass guarantee*](#def:multi-pass_guarantee "24.3.5.5 Forward iterators [forward.iterators]") if
- [(3.1)](#forward.iterators-3.1)
a == b implies ++a == ++b and
- [(3.2)](#forward.iterators-3.2)
X is a pointer type or the expression(void)++X(a), *a is equivalent to the expression *a[.](#forward.iterators-3.sentence-1)
[4](#forward.iterators-4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2267)
[*Note [2](#forward.iterators-note-2)*:
The requirement thata == b implies++a == ++b (which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through
a mutable iterator
(which applies to output iterators)
allows the use of multi-pass one-directional algorithms with forward iterators[.](#forward.iterators-4.sentence-1)
— *end note*]
Table [81](#tab:forwarditerator) — *Cpp17ForwardIterator* requirements (in addition to *Cpp17InputIterator*) [[tab:forwarditerator]](./tab:forwarditerator)
| [🔗](#tab:forwarditerator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:forwarditerator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:forwarditerator-row-3)<br>r++ | convertible to const X& | { X tmp = r; ++r; return tmp; } | |
| [🔗](#tab:forwarditerator-row-4)<br>*r++ | reference | | |
[5](#forward.iterators-5)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2297)
If a and b are equal, then either a and b are both dereferenceable
or else neither is dereferenceable[.](#forward.iterators-5.sentence-1)
[6](#forward.iterators-6)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2302)
If a and b are both dereferenceable, then a == b if and only if*a and *b are bound to the same object[.](#forward.iterators-6.sentence-1)
#### [24.3.5.6](#bidirectional.iterators) Bidirectional iterators [[bidirectional.iterators]](bidirectional.iterators)
[1](#bidirectional.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2309)
A class or pointer typeX meets the requirements of a bidirectional iterator if,
in addition to meeting the *Cpp17ForwardIterator* requirements,
the following expressions are valid as shown in Table [82](#tab:bidirectionaliterator "Table 82: Cpp17BidirectionalIterator requirements (in addition to Cpp17ForwardIterator)")[.](#bidirectional.iterators-1.sentence-1)
Table [82](#tab:bidirectionaliterator) — *Cpp17BidirectionalIterator* requirements (in addition to *Cpp17ForwardIterator*) [[tab:bidirectionaliterator]](./tab:bidirectionaliterator)
| [🔗](#tab:bidirectionaliterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:bidirectionaliterator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:bidirectionaliterator-row-3)<br>--r | X& | | *Preconditions*: there exists s such that r == ++s[.](#tab:bidirectionaliterator-row-3-column-4-sentence-1)<br> *Postconditions*: r is dereferenceable[.](#tab:bidirectionaliterator-row-3-column-4-sentence-2)<br> --(++r) == r[.](#tab:bidirectionaliterator-row-3-column-4-sentence-3)<br> --r == --s implies r == s[.](#tab:bidirectionaliterator-row-3-column-4-sentence-4)<br> addressof(r) == addressof(--r)[.](#tab:bidirectionaliterator-row-3-column-4-sentence-5) |
| [🔗](#tab:bidirectionaliterator-row-4)<br>r-- | convertible to const X& | { X tmp = r; --r; return tmp; } | |
| [🔗](#tab:bidirectionaliterator-row-5)<br>*r-- | reference | | |
[2](#bidirectional.iterators-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2342)
[*Note [1](#bidirectional.iterators-note-1)*:
Bidirectional iterators allow algorithms to move iterators backward as well as forward[.](#bidirectional.iterators-2.sentence-1)
— *end note*]
#### [24.3.5.7](#random.access.iterators) Random access iterators [[random.access.iterators]](random.access.iterators)
[1](#random.access.iterators-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2349)
A class or pointer typeX meets the requirements of a random access iterator if,
in addition to meeting the *Cpp17BidirectionalIterator* requirements,
the following expressions are valid as shown in Table [83](#tab:randomaccessiterator "Table 83: Cpp17RandomAccessIterator requirements (in addition to Cpp17BidirectionalIterator)")[.](#random.access.iterators-1.sentence-1)
Table [83](#tab:randomaccessiterator) — *Cpp17RandomAccessIterator* requirements (in addition to *Cpp17BidirectionalIterator*) [[tab:randomaccessiterator]](./tab:randomaccessiterator)
| [🔗](#tab:randomaccessiterator-row-1)<br>**Expression** | **Return type** | **Operational** | **Assertion/note** |
| --- | --- | --- | --- |
| [🔗](#tab:randomaccessiterator-row-2) | | **semantics** | **pre-/post-condition** |
| [🔗](#tab:randomaccessiterator-row-3)<br>r += n | X& | { difference_type m = n; if (m >= 0) while (m--) ++r; else while (m++) --r; return r; } | |
| [🔗](#tab:randomaccessiterator-row-4)<br>a + n n + a | X | { X tmp = a; return tmp += n; } | a + n == n + a[.](#tab:randomaccessiterator-row-4-column-4-sentence-1) |
| [🔗](#tab:randomaccessiterator-row-5)<br>r -= n | X& | return r += -n; | *Preconditions*: the absolute value of n is in the range of representable values of difference_type[.](#tab:randomaccessiterator-row-5-column-4-sentence-1) |
| [🔗](#tab:randomaccessiterator-row-6)<br>a - n | X | { X tmp = a; return tmp -= n; } | |
| [🔗](#tab:randomaccessiterator-row-7)<br>b - a | difference_type | return n; | *Preconditions*: there exists a value n of type difference_type such that a + n == b[.](#tab:randomaccessiterator-row-7-column-4-sentence-1)<br> b == a + (b - a)[.](#tab:randomaccessiterator-row-7-column-4-sentence-2) |
| [🔗](#tab:randomaccessiterator-row-8)<br>a[n] | convertible to reference | *(a + n) | |
| [🔗](#tab:randomaccessiterator-row-9)<br>a < b | decltype(a < b) models *boolean-testable* | *Effects*: Equivalent to: return b - a > 0; | < is a total ordering relation |
| [🔗](#tab:randomaccessiterator-row-10)<br>a > b | decltype(a > b) models *boolean-testable* | b < a | > is a total ordering relation opposite to <[.](#tab:randomaccessiterator-row-10-column-4-sentence-1) |
| [🔗](#tab:randomaccessiterator-row-11)<br>a >= b | decltype(a >= b) models *boolean-testable* | !(a < b) | |
| [🔗](#tab:randomaccessiterator-row-12)<br>a <= b | decltype(a <= b) models *boolean-testable* | !(a > b) | |
Reference in New Issue View Git Blame Copy Permalink