[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) |  |