23 Iterators library [iterators]

23.3 Iterator requirements [iterator.requirements]

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

1
#
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
:
For an iterator type X there must be an instantiation of iterator_­traits<X> ([iterator.traits]).
— end note
]

23.3.5.1 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, 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.2 Input iterators [input.iterators]

1
#
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.
2
#
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
:
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; }
3
#
[Note
:
For input iterators, a == b does not imply ++a == ++b.
(Equality does not guarantee the substitution property or referential transparency.)
Algorithms on input iterators should never attempt to pass through the same iterator twice.
They should be single pass algorithms.
Value type T is not required to be a Cpp17CopyAssignable type (Table 31).
These algorithms can be used with istreams as the source of the input data through the istream_­iterator class template.
— end note
]

23.3.5.3 Output iterators [output.iterators]

1
#
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.
2
#
[Note
:
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.
Algorithms on output iterators should never attempt to pass through the same iterator twice.
They should be single-pass algorithms.
Equality and inequality might not be defined.
— end note
]

23.3.5.4 Forward iterators [forward.iterators]

1
#
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.
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
:
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 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.
4
#
[Note
:
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
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.

23.3.5.5 Bidirectional iterators [bidirectional.iterators]

1
#
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
2
#
[Note
:
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
— end note
]

23.3.5.6 Random access iterators [random.access.iterators]

1
#
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)