25 Iterators library [iterators]

25.3 Iterator requirements [iterator.requirements]

25.3.5 C++17 iterator requirements [iterator.cpp17]

25.3.5.1 General [iterator.cpp17.general]

In the following sections, a and b denote values of type X or const X, difference_type and reference refer to the types iterator_traits<X>​::​difference_type and iterator_traits<X>​::​reference, respectively, n denotes a value of difference_type, u, tmp, and m denote identifiers, r denotes a value of X&, t denotes a value of value type T, o denotes a value of some type that is writable to the output iterator.
[Note 1: 
For an iterator type X there must be an instantiation of iterator_traits<X> ([iterator.traits]).
— end note]

25.3.5.2 Cpp17Iterator [iterator.iterators]

The Cpp17Iterator requirements form the basis of the iterator taxonomy; every iterator meets the Cpp17Iterator requirements.
This set of requirements specifies operations for dereferencing and incrementing an iterator.
Most algorithms will require additional operations to read ([input.iterators]) or write ([output.iterators]) values, or to provide a richer set of iterator movements ([forward.iterators], [bidirectional.iterators], [random.access.iterators]).
A type X meets the Cpp17Iterator requirements if:
Table 86: Cpp17Iterator requirements [tab:iterator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r
unspecified
Preconditions: r is dereferenceable.
++r
X&

25.3.5.3 Input iterators [input.iterators]

A class or pointer type X meets the requirements of an input iterator for the value type T if X meets the Cpp17Iterator ([iterator.iterators]) and Cpp17EqualityComparable (Table 28) requirements and the expressions in Table 87 are valid and have the indicated semantics.
In Table 87, the term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined.
This set can change over time.
Each algorithm places additional requirements on the domain of == for the iterator values it uses.
These requirements can be inferred from the uses that algorithm makes of == and !=.
[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).
— end example]
Table 87: Cpp17InputIterator requirements (in addition to Cpp17Iterator) [tab:inputiterator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
a != b
decltype(a != b) models boolean-testable
!(a == b)
Preconditions: (a, b) is in the domain of ==.
*a
reference, convertible to T
Preconditions: a is dereferenceable.

The expression
(void)*a, *a is equivalent to *a.

If a == b and (a, b) is in the domain of == then *a is equivalent to *b.
a->m
(*a).m
Preconditions: a is dereferenceable.
++r
X&
Preconditions: r is dereferenceable.

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 ==.
(void)r++
equivalent to (void)++r
*r++
convertible to T
{ T tmp = *r;
++r;
return tmp; }
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.
[Note 1: 
For input iterators, a == b does not imply ++a == ++b.
(Equality does not guarantee the substitution property or referential transparency.)
Value type T is not required to be a Cpp17CopyAssignable type (Table 34).
Such an algorithm can be used with istreams as the source of the input data through the istream_iterator class template.
— end note]

25.3.5.4 Output iterators [output.iterators]

A class or pointer type X meets the requirements of an output iterator if X meets the Cpp17Iterator requirements ([iterator.iterators]) and the expressions in Table 88 are valid and have the indicated semantics.
Table 88: Cpp17OutputIterator requirements (in addition to Cpp17Iterator) [tab:outputiterator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r = o
result is not used
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
++r
X&
addressof(r) == addressof(++r).

Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
r++
convertible to const X&
{ X tmp = r;
++r;
return tmp; }
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
*r++ = o
result is not used
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
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.
[Note 1: 
The only valid use of an operator* is on the left side of the assignment statement.
Assignment through the same value of the iterator happens only once.
Equality and inequality are not necessarily defined.
— end note]

25.3.5.5 Forward iterators [forward.iterators]

A class or pointer type X meets the requirements of a forward iterator if
  • X meets the Cpp17InputIterator requirements ([input.iterators]),
  • X meets the Cpp17DefaultConstructible requirements ([utility.arg.requirements]),
  • 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,
  • the expressions in Table 89 are valid and have the indicated semantics, and
  • objects of type X offer the multi-pass guarantee, described below.
The domain of == for forward iterators is that of iterators over the same underlying sequence.
However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type.
[Note 1: 
Value-initialized iterators behave as if they refer past the end of the same empty sequence.
— end note]
Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:
  • a == b implies ++a == ++b and
  • X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.
[Note 2: 
The requirement that a == 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.
— end note]
Table 89: Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator) [tab:forwarditerator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r++
convertible to const X&
{ X tmp = r;
++r;
return tmp; }
*r++
reference
If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.
If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

25.3.5.6 Bidirectional iterators [bidirectional.iterators]

A class or pointer type X meets the requirements of a bidirectional iterator if, in addition to meeting the Cpp17ForwardIterator requirements, the following expressions are valid as shown in Table 90.
Table 90: Cpp17BidirectionalIterator requirements (in addition to Cpp17ForwardIterator) [tab:bidirectionaliterator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
--r
X&
Preconditions: there exists s such that r == ++s.

Postconditions: r is dereferenceable.

--(++r) == r.

--r == --s implies r == s.

addressof(r) == addressof(--r).
r--
convertible to const X&
{ X tmp = r;
--r;
return tmp; }
*r--
reference
[Note 1: 
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
— end note]

25.3.5.7 Random access iterators [random.access.iterators]

A class or pointer type X 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 91.
Table 91: Cpp17RandomAccessIterator requirements (in addition to Cpp17BidirectionalIterator) [tab:randomaccessiterator]
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r += n
X&
{ difference_type m = n;
if (m >= 0)
while (m--)
++r;
else
while (m++)
--r;
return r; }
a + n
n + a
X
{ X tmp = a;
return tmp += n; }
a + n == n + a.
r -= n
X&
return r += -n;
Preconditions: the absolute value of n is in the range of representable values of difference_type.
a - n
X
{ X tmp = a;
return tmp -= n; }
b - a
difference_type
return n;
Preconditions: there exists a value n of type difference_type such that a + n == b.

b == a + (b - a).
a[n]
convertible to reference
*(a + n)
a < b
decltype(a < b) models boolean-testable
Effects: Equivalent to: return b - a > 0;
< is a total ordering relation
a > b
decltype(a > b) models boolean-testable
b < a
> is a total ordering relation opposite to <.
a >= b
decltype(a >= b) models boolean-testable
!(a < b)
a <= b
decltype(a <= b) models boolean-testable
!(a > b)