CODEWITHSUNDEEP
c++iterator
nknight
nknight

Reputation: 1076

Does incrementing a mutable input iterator invalidate old iterator values?

Iterators that further satisfy the requirements of output iterators are called mutable iterators. Nonmutable iterators are referred to as constant iterators. [24.2.1:4]

This suggests you could have a mutable input iterator, which meets the requirements of both input and output iterators.

After incrementing an input iterator, copies of its old value need not be dereferenceable [24.2.3]. However, the standard does not say the same for output iterators; in fact, the operational semantics for postfix increment are given as { X tmp = r; ++r; return tmp; }, suggesting that output iterators may not invalidate (copies of) old iterator values.

So, can incrementing a mutable input iterator invalidate old iterator copies?

If so, how would you support code like X a(r++); *a = t or X::reference p(*r++); p = t with (e.g.) a proxy object?

If not, then why does boost::iterator claim it needs a proxy object? (Link is code; scroll down to read the comments on structs writable_postfix_increment_proxy and postfix_increment_result). That is, if you can return a (dereferenceable) copy of the old iterator value, why would you need to wrap this copy in a proxy?

Upvotes: 9

Views: 940

Answers (2)

Stack Overflow is garbage
Stack Overflow is garbage

Reputation: 248199

Input and output iterators are basically designed to allow single-pass traversal: to describe sequences where each element can only be visited once.

Streams are a great example. If you read from stdin or a socket, or write to a file, then there is only the stream's current position. All other iterators pointing to the same underlying sequence are invalidated when you increment an iterator.

Forward iterators allow multi-pass traversal, the additional guarantee you need: they ensure that you can copy your iterator, increment the original, and the copy will still point to the old position, so you can iterate from there.

Upvotes: 4

Bo Persson
Bo Persson

Reputation: 92341

The explanation if found in the next section, [24.2.5] Forward iterators, where it is stated how these differ from input and output iterators:

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

Unfortunately, the standard must be read as a whole, and the explanation is not always where you expect it to be.

Upvotes: 6

Related Questions