9

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?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
nknight
  • 1,034
  • 8
  • 17
  • Oh how I detest these language-lawyer questions. Might as well argue about how many angels dance on the head of a pin. – Mark Ransom Aug 13 '12 at 06:37
  • 4
    @MarkRansom Yeah, I sure hate when people try to understand the language they're using. Damn them all... And I need to tell the world about my hatred for them here in *this* comment (for the record, iterator categories are kind of a big deal in C++. Understanding what each of them can do is pretty useful) – jalf Aug 13 '12 at 08:10
  • @MarkRansom: My question is important to me because an affirmative answer means I have to add another proxy object to my class to handle mutable input iterators, just like Boost does. The consensus below suggests that there's no such thing as a mutable input iterator (despite the comment in 24.2.1:4). This in turn suggests Boost is incorrect in its handling of "mutable input iterators" --- if even the Boost developers misunderstood this aspect of the standard, isn't this an issue that should be addressed? – nknight Aug 13 '12 at 19:58
  • @nknight, I wrote my comment late at night and it was certainly more snarky than it needed to be. I wrote it out of frustration of being unable to imagine a case where the answer would matter, even while I knew the problem was more likely with my imagination than with the question. Thanks for giving a little more context, and please forgive me for being so rude. – Mark Ransom Aug 13 '12 at 20:07

2 Answers2

6

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.

Bo Persson
  • 90,663
  • 31
  • 146
  • 203
  • I'm still confused, sorry. Are you saying that for a mutable input iterator to not invalidate old values, it must satisfy the multi-pass guarantee? I appreciate your answer! – nknight Aug 13 '12 at 06:48
  • 2
    No, I'm saying that a forward iterator is required to do what you want, an input iterator is not. The standard has nothing in-between. Even if you have *some* of the attributes of a forward iterator, it is still an input or output iterator until *all* requirements are fullfilled. Consider that an input iterator could be connected to a keybord. Even if you save a copy of it, you can't back up and have me retype the text. Similar for an output iterator, it could go directly to a printer. – Bo Persson Aug 13 '12 at 06:58
  • 2
    Oh! I'll save that keyboard/printer analogy for future reuse :D – Matthieu M. Aug 13 '12 at 08:49
  • "*The standard has nothing in-between*" -- to clarify, are you saying that it the standard makes it *impossible* for an input iterator (that is not also a forward iterator) to additionally satisfy the output iterator requirements? If this is the claim, then rather than discussing the multi-pass guarantee, could we just say that it's impossible to satisfy the operational semantics of an output iterator's postfix increment if old iterators can be invalidated? This issue is related to merging requirements from input and output iterators; which requirements win in the case of a conflict? – nknight Aug 13 '12 at 19:44
  • 2
    @nknight There isn't anything in the standard between an input iterator and a forward iterator. You can certainly write something that works for you, but it doesn't fit the iterator categories of the standard. There has been proposals for a more fine grained categorization, and separation of traversal from ways of accessing the objects. Nothing came out of that though, that affected the standard. – Bo Persson Aug 13 '12 at 19:51
  • @BoPersson: Thank you for your time and thoughtful answer, on both this question and others I have asked. Best, – nknight Aug 13 '12 at 20:01
4

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.

jalf
  • 243,077
  • 51
  • 345
  • 550
  • "*All other iterators pointing to the same underlying sequence are invalidated when you increment an iterator.*" --- indeed this is the intent of the standard (for both input and output iterators), although C++11 doesn't make this explicit for output iterators, since this fix: (http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2035) did not make it into the published version ( see http://stackoverflow.com/a/11938988/985943 for more details). – nknight Aug 13 '12 at 20:18