Преемник итератора не обязательно является обычной функцией: как это возможно?

Question

Преемник итератора не обязательно является обычной функцией: как это возможно?

На странице 91 книги Элементы программирования, Степанов и МакДжонс говорят, что концепция Итератора требует successor функция, но это не обязательно регулярно, потому что

…i = j не означает, что successor(i) = successor(j)…

(увидеть страница онлайн)

Я понимаю обратное successor(i) = successor(j) не подразумевает i=j (например, в два нулевых завершенных списка) и что successor функция не может быть определена для некоторых входов. Но я не понимаю, как такое возможно i = j может привести к successor(i) != successor(j),

В каком случае они будут ссылаться? Возможно, какой-то итератор, который делает случайные (как в случайном порядке) прыжки? или некоторый итератор, который имеет скрытое состояние и «скачет» иначе, чем другой итератор, после указания на тот же элемент (и сравнения в этом смысле равного).

Они сразу переходят к уточнениям (ForwardIterator), которые требуют регулярного successor Функция так что мне не понятно.

Изначально я думал, что входной итератор может иметь это свойство. Однако мне все еще трудно понять, является ли это контрпримером: (в рамках определенной реализации 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!
}

(составлено с GCC 6.1)

5

c++iterator regular-type

Решение

Другие решения

Рассмотрим тип iter определяется как:

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 удовлетворяет требованиям для EoP Iterator концепция: это Regular, source это обычная функция, successor в частности не регулярно.
Учитывая два объекта i а также j типа iter такой, что i == j, очень вероятно, что successor(i) != successor(j),

4

Источник

Accepted Answer

Примером может быть преемник функция, которая потребляет поток данных (как они упоминают в книге).
Когда вы прочитали я-я элемент, вы можете теоретически вызвать преемник Функция для него только один раз. Если вы попытаетесь вызвать его дважды, результаты будут другими.
Просто представь, что successor(i) читает следующий элемент из потока, то есть I-й + 1 элемент. Это фактически означает потреблять это, и это больше не будет доступно. Если вы позвоните successor(i) в другой раз, вы получите I-й + 2 элемент из потока.
Таким образом, если входы одинаковы (i = j), у вас нет никаких гарантий, что выходы одинаковы (successor(i) = successor(j)).

3