Successor of iterator is not necessarily a regular function: how is it possible?

Question

In page 91 of the book Elements of Programming, Stepanov and McJones say that the concept of Iterator requires a successor function but that is not necessarily regular because

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

(see page online)

I understand the converse successor(i) = successor(j) does not imply i=j (for example in two null terminated list) and that successor function may not be defined for some inputs. But I don't understand how could it be possible that i = j can lead to successor(i) != successor(j).

What case would they be referring to? Perhaps some iterator that does random (as in aleatory) hops? or some iterator that has a hidden state and "jumps" differently than the other iterator after pointing to the same element (and comparing equal in this sense).

They immediately jump to refinements (ForwardIterator) that require a regular successor function so it is not clear to me.

---

Initially I thought that an input iterator can have this property. However is still difficult to me to see if this constitutes a counterexample: (within a certain implementation of STL).

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

Cardiogram

Answer 1

An example could be a successor function that consumes a stream of data (as they mention in the book).
When you have read the i-th element, you can theoretically invoke the successor function for it only once. If you try to invoke it twice, the results are different.
Simply imagine that successor(i) reads the next element from the stream, that is the i-th+1 element. It actually means to consume it and it won't be available anymore. If you call successor(i) 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 guarantees that the outputs are the same (successor(i) = successor(j)).

Pliske

yes, makes sense but when I want to implement a counter example the input (istream) iterators still compare equal. Even more confusing is that *it1 != *it2, maybe it is an implementation problem. (see the new code in my equation). I know I shouldn't compare the axiomatic book of Stepanov with a mundane implementation of STL, but I wonder if in practice the ideals still hold in a practice. – Cardiogram

ok, I am doing more test and it1 == it2 no matter the order of the operators. It looks like in the implementation I have the two iterators will keep being equal as long as they were assigned at some point. – Cardiogram

In context, this example looks more like a non-regular source function (*). – Cardiogram

@Cardiogram You know that I got the example from the book you are reading, right? This is the example they use to explain what you asked. – Pliske

Well, yes, but when I tried to implement an example with input iterators from STL where this is the case, I wasn't able to. True, it could be that a real STL input iterator is not a faithful representation of that case, but how else one know show an input iterator is supposed to behave or compare equal. The only thing I was able to actually prove is that source is not a regular function on input iterators. – Cardiogram

Answer 2

Consider the type iter 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 EoP's Iterator concept: it is Regular, source is a regular function, successor notably is not regular. Given two objects i and j of type iter such that i == j, it is extremely likely that successor(i) != successor(j).

Okwu

Yes, this is the example I had in mind. But it looked pretty convolved and didn't know if that is what they had in mind or if there was an application for that. I guess one can imagine an iterator that randomly covers a sequence (repeating or not repeating elements). – Cardiogram