The successor of an iterator is not necessarily a regular function: how is this possible?

Question

On page 91 of the Programming Elements book, Stepanov and McJones say that the Iterator concept requires the successor function, but this is not necessary regularly because

... i = j does not mean that successor(i) = successor(j) ...

(see web page )

I understand that the reverse successor(i) = successor(j) does not mean i=j (for example, in two lists with zero completion) and that the successor function cannot be defined for some inputs. But I do not understand how it is possible that i = j can lead to successor(i) != successor(j) .

In which case will they be referenced? Perhaps some kind of iterator that makes random (as in aleatory) hops? or some iterator that has a hidden state and “jumps” differently than another iterator, pointing to the same element (and comparing in this sense).

They immediately proceed to refinements (ForwardIterator), which require the regular successor function, so this is not clear to me.

---

Initially, I thought that an input iterator could have this property. However, it’s still hard for me to understand if this is a counterexample: (within the framework of a specific STL implementation).

 #include <iostream> #include <sstream> #include <iterator> #include <numeric> #include <cassert> using std::cout; using std::endl; int main(){ std::istream_iterator<int> it1(std::cin); // wait for one input std::istream_iterator<int> it2 = it1; assert(it1 == it2); cout << "*it1 = " << *it1 << endl; cout << "*it2 = " << *it2 << endl; cout << "now sucessor" << endl; ++it1; // wait for one input ++it2; // wait for another input assert(it1 == it2); // inputs still compare equal ! cout << "*it1 = " << *it1 << endl; cout << "*it2 = " << *it2 << endl; assert(it1 == it2); // also here ! and yet they point to different values... assert(*it1 == *it2); // assert fails! } 

(compiled with GCC 6.1)

Answer 1

Consider an iter type defined as:

 struct iter { unsigned value; }; inline bool operator==(iter const& x, iter const& y) { return x.value == y.value; } inline bool operator!=(iter const& x, iter const& y) { return !(x == y); } auto source(iter const& x) { return x.value; } iter successor(iter const&) { std::random_device engine{}; std::uniform_int_distribution<unsigned> dist{}; return {dist(engine)}; } 

IIRC, iter satisfies the requirements for the EoP Iterator concept: Regular , source is a regular function, successor , in particular, is not regular. For two objects i and j type iter such that i == j , it is very likely that successor(i) != successor(j) .

Answer 2

An example would be a successor function that consumes a stream of data (as they mention in the book).
When you read the ith element, theoretically you can call the successor function only once. If you try to call it twice, the results will be different.
Just imagine that successor(i) reading the next element from the stream, that is, the i-th + 1 element. This actually means consuming it, and it will no longer be available. If you call successor(i) at another time, you will get the i-th + 2 element from the stream.
Thus, if the inputs are the same ( i = j ), you have no guarantee that the outputs are the same ( successor(i) = successor(j) ).