迭代器的后继不一定是常规函数：怎么可能？

Question

在 Elements of Programming 一书的第 91 页中，Stepanov 和 McJones 说 Iterator 的概念需要一个 successor 函数，但那是 不一定 正常因为

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

我理解相反的 successor(i) = successor(j) 并不意味着 i=j（例如在两个空终止列表中）并且可能没有为某些输入定义 successor 函数。但是我不明白i = j怎么可能导致successor(i) != successor(j)。

他们指的是什么情况？ 也许是一些随机（如随机）跳跃的迭代器？或某些具有隐藏状态的迭代器，并且 "jumps" 在指向同一元素（并在这个意义上比较相等）后与另一个迭代器不同。

他们立即跳转到需要常规 successor 函数的改进 (ForwardIterator)，所以我不清楚。

最初我以为输入迭代器可以有这个属性。然而，我仍然很难看出这是否构成反例：（在 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 编译）

Answer 1

一个例子可以是 successor 函数，它使用数据流（正如他们在书中提到的那样）。
当你读完 i-th 元素后，理论上你可以为它调用一次 successor 函数。如果你尝试调用它两次，结果是不同的。
简单想象一下，successor(i) 从流中读取下一个元素，即第 i-th+1 个元素。它实际上意味着消耗它并且它将不再可用。如果您再次调用 successor(i)，您将从流中获得第 i-th+2 个元素。
因此，如果输入相同 (i = j)，则无法保证输出相同 (successor(i) = successor(j))。

Answer 2

考虑类型 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 特别是不正常。给定 iter 类型的两个对象 i 和 j 使得 i == j，极有可能 successor(i) != successor(j).

迭代器的后继不一定是常规函数：怎么可能？

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

c++

iterator

regular-type