Następca iteratora niekoniecznie jest funkcją regularną: jak to możliwe?

Question

Na stronie 91 książki Elementy programowania, Stepanov i McJones powiedzieć, że pojęcie Iterator wymaga successor funkcja ale to niekoniecznie regularne ponieważ

... i = j nie oznacza, że successor(i) = successor(j) ...

(patrz page online)

rozumiem c onverse successor(i) = successor(j) nie implikuje i=j (na przykład na dwóch zakończonych znakami pustymi listach) i dla niektórych wejść nie można zdefiniować funkcji successor. Ale nie rozumiem, jak to możliwe, że i = j może prowadzić do successor(i) != successor(j).

Jaką sprawę mieliby oni na myśli? Być może jakiś iterator, który robi losowe (jak w aleatory) chmiel? lub jakiś iterator, który ma ukryty stan i "przeskakuje" inaczej niż drugi iterator po wskazaniu tego samego elementu (i porównywaniu równym w tym sensie).

Natychmiast przeskakują do udoskonaleń (ForwardIterator), które wymagają regularnej funkcji successor, więc nie jest dla mnie jasne.

---

Początkowo myślałem, że Iterator wejścia może mieć tę właściwość. Jednak wciąż jest mi trudno sprawdzić, czy jest to kontrprzykład: (w ramach pewnej implementacji 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! 
} 

(skompilowane z GCC 6.1)

Answer 1

Przykładem może być następca funkcja, która pobiera strumień danych (jak wspominają w książce).
Po przeczytaniu elementu i-th można teoretycznie wywołać funkcję następującą po następnej tylko raz. Jeśli spróbujesz wywołać ją dwukrotnie, wyniki są inne.
Po prostu wyobraź sobie, że successor(i) odczytuje następny element ze strumienia, czyli element i-th + 1. Oznacza to, że należy go konsumować i nie będzie już dostępna. Jeśli zadzwonisz ponownie pod numer successor(i), otrzymasz ze strumienia element i-th + 2.
Tak więc, jeśli wejścia są takie same (i = j), nie ma gwarancji, że wyjścia są takie same (successor(i) = successor(j)).

Answer 2

Rozważmy typ iter zdefiniowany jako:

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 spełnia warunki Iterator koncepcji EOP: jest on Regular, source jest regularny funkcja, successor zwłaszcza jest nie regularne. Biorąc pod uwagę dwa obiekty i i j typu iter takie, że i == j, jest bardzo prawdopodobne, że successor(i) != successor(j).