[iterator.cpp17] (original) (raw)

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,aandbdenote values of typeX or const X,difference_­type and reference refer to the types iterator_­traits<X>​::​difference_­type anditerator_­traits<X>​::​reference, respectively,ndenotes a value ofdifference_­type,u,tmp, andmdenote identifiers,rdenotes a value ofX&,tdenotes a value of value typeT,odenotes 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:

• X meets the Cpp17CopyConstructible, Cpp17CopyAssignable, and_Cpp17Destructible_ requirements ([utility.arg.requirements]) and lvalues of type X are swappable ([swappable.requirements]), and
• iterator_­traits<X>​::​difference_­type is a signed integer type or void, and
• the expressions in Table 84 are valid and have the indicated semantics.

Table 84: Cpp17Iterator requirements [tab:iterator]

23.3.5.3 Input iterators [input.iterators]

A class or pointer typeXmeets the requirements of an input iterator for the value typeTifX 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 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 ahas the property _p_defined as follows:b has property _p_and a value ihas property p_if (*i==x) or if (*i!=xand++ihas property_p).

— _end example_]

Table 85: Cpp17InputIterator requirements (in addition to Cpp17Iterator) [tab:inputiterator]

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 theistream_­iteratorclass template.

— _end note_]

23.3.5.4 Output iterators [output.iterators]

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

Table 86: Cpp17OutputIterator requirements (in addition to Cpp17Iterator) [tab:outputiterator]

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 typeXmeets 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 87are 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 themulti-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 thata == bimplies++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]

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

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

23.3.5.6 Bidirectional iterators [bidirectional.iterators]

A class or pointer typeXmeets 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]

[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 typeXmeets 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]