23 Iterators library [iterators]

23.3 Iterator requirements [iterator.requirements]

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

23.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]

23.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:

(2.1)
X meets the Cpp17CopyConstructible, Cpp17CopyAssignable, and Cpp17Destructible requirements ([utility.arg.requirements]) and lvalues of type X are swappable ([swappable.requirements]), and
(2.2)
iterator_traits<X>::difference_type is a signed integer type or void, and
(2.3)
the expressions in Table 84 are valid and have the indicated semantics.

Table 84: Cpp17Iterator requirements [tab:iterator]

🔗	Expression	Return type	Operational	Assertion/note
🔗			semantics	pre-/post-condition
🔗	*r	unspecified		Preconditions: r is dereferenceable.
🔗	++r	X&

23.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 25) requirements and the expressions in Table 85 are valid and have the indicated semantics.

In Table 85, 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 85: Cpp17InputIterator requirements (in addition to Cpp17Iterator) [tab:inputiterator]

🔗	Expression	Return type	Operational	Assertion/note
🔗			semantics	pre-/post-condition
🔗	a != b	contextually convertible to bool	!(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 31).

Such an algorithm can be used with istreams as the source of the input data through the istream_iterator class template.

— end note]

23.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 86 are valid and have the indicated semantics.

Table 86: 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 might not be defined.

— end note]

23.3.5.5 Forward iterators [forward.iterators]

A class or pointer type X meets the requirements of a forward iterator if

(1.1)
X meets the Cpp17InputIterator requirements ([input.iterators]),
(1.2)
X meets the Cpp17DefaultConstructible requirements ([utility.arg.requirements]),
(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)
the expressions in Table 87 are valid and have the indicated semantics, and
(1.5)
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:

(3.1)
a == b implies ++a == ++b and
(3.2)
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 87: 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.

23.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 88 .

Table 88: 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]

23.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 89 .

Table 89: 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	contextually convertible to bool	b - a > 0	< is a total ordering relation
🔗	a > b	contextually convertible to bool	b < a	> is a total ordering relation opposite to <.
🔗	a >= b	contextually convertible to bool	!(a < b)
🔗	a <= b	contextually convertible to bool.	!(a > b)