Title
multi-pass property of Forward Iterator underspecified
Status
resolved
Section
[forward.iterators]
Submitter
Alisdair Meredith

Created on 2010-02-07.00:00:00 last changed 170 months ago

Messages

Date: 2010-10-21.18:28:33

Rationale:

Solved by N3066.

Date: 2010-12-05.00:09:22

[ 2010 Pittsburgh: Moved to NAD EditorialResolved. Rationale added below. ]

Date: 2011-11-21.23:14:17

The following example demonstrates code that would meet the guarantees of a Forward Iterator, but only permits a single traversal of the underlying sequence:

template< typename ForwardIterator>
struct bad_iterator {
  shared_ptr<ForwardIterator> impl;

  bad_iterator( ForwardIterator iter ) {
     : impl{new ForwardIterator{iter} } 
     {
  }

  auto operator*() const -> decltype(*ForwardIterator{}) {
     return **impl;
  }

  auto operator->() const -> ForwardIterator {
     return *impl;
  }

  auto operator==(bad_iterator const & rhs) const -> bool {
     return impl == rhs.impl;
  }

  auto operator++() -> bad_iterator& {
     ++(*impl);
     return *this;
  }
  // other operations as necessary...
};

Here, we use shared_ptr to wrap a forward iterator, so all iterators constructed from the same original iterator share the same 'value', and incrementing any one copy increments all others.

There is a missing guarantee, expressed by the following code sequence

FwdIter x = seq.begin();  // obtain forward iterator from a sequence
FwdIter y = x;            // copy the iterator
assert(x == y);           // iterators must be the same
++x;                      // increment *just one* iterator
assert(x != y);           // iterators *must now be different*
++y;                      // increment the other iterator
assert(x == y);           // now the iterators must be the same again

That inequality in the middle is an essential guarantee. Note that this list is simplified, as each assertion should also note that they refer to exactly the same element (&*x == &*y) but I am not complicating the issue with tests to support proxy iterators, or value types overloading unary operator+.

I have not yet found a perverse example that can meet this additional constraint, and not meet the multi-pass expectations of a Forward Iterator without also violating other Forward Iterator requirements.

Note that I do not yet have standard-ready wording to resolve the problem, as saying this neatly and succinctly in 'standardese' is more difficult.

History
Date User Action Args
2010-12-05 00:09:22adminsetstatus: nad editorial -> resolved
2010-10-21 18:28:33adminsetmessages: + msg1554
2010-10-21 18:28:33adminsetmessages: + msg1553
2010-02-07 00:00:00admincreate