cppdraft_translate/cppdraft/iterator/cpp17.md

[iterator.cpp17]

24 Iterators library [iterators]

24.3 Iterator requirements [iterator.requirements]

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

24.3.5.1 General [iterator.cpp17.general]

1

#

In the following sections,a andb denote values of typeX or const X,difference_type and reference refer to the types iterator_traits​::​difference_type anditerator_traits​::​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.

[Note 1:

For an iterator type X there must be an instantiation of iterator_traits ([iterator.traits]).

— end note]

24.3.5.2 Cpp17Iterator [iterator.iterators]

1

#

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

2

#

A type X meets the Cpp17Iterator requirements if

• (2.1)

X meets the Cpp17CopyConstructible, Cpp17CopyAssignable, Cpp17Swappable, andCpp17Destructible requirements ([utility.arg.requirements], [swappable.requirements]), and

• (2.2)

iterator_traits​::​difference_type is a signed integer type or void, and

• (2.3)

the expressions in Table 78 are valid and have the indicated semantics.

Table 78 — Cpp17Iterator requirements [tab:iterator]

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

24.3.5.3 Input iterators [input.iterators]

1

#

A class or pointer typeX meets the requirements of an input iterator for the value typeT ifX meets the Cpp17Iterator ([iterator.iterators]) andCpp17EqualityComparable (Table 28) requirements and the expressions in Table 79 are valid and have the indicated semantics.

2

#

In Table 79, the termthe 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 propertyp).

— end example]

Table 79 — 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; }

3

#

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 theistream_iterator class template.

— end note]

24.3.5.4 Output iterators [output.iterators]

1

#

A class or pointer typeX meets the requirements of an output iterator if X meets the Cpp17Iterator requirements ([iterator.iterators]) and the expressions in Table 80 are valid and have the indicated semantics.

Table 80 — 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.

2

#

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]

24.3.5.5 Forward iterators [forward.iterators]

1

#

A class or pointer typeX meets the Cpp17ForwardIterator requirements 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 81 are valid and have the indicated semantics, and

• (1.5)

objects of type X offer the multi-pass guarantee, described below.

2

#

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]

3

#

Two dereferenceable iterators a and b of type X offer themulti-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.

4

#

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

— end note]

Table 81 — 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

5

#

If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.

6

#

If a and b are both dereferenceable, then a == b if and only if*a and *b are bound to the same object.

24.3.5.6 Bidirectional iterators [bidirectional.iterators]

1

#

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.

Table 82 — 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

2

#

[Note 1:

Bidirectional iterators allow algorithms to move iterators backward as well as forward.

— end note]

24.3.5.7 Random access iterators [random.access.iterators]

1

#

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.

Table 83 — 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)