c++ - 为什么 InputIterators 只有一次通过？

Question

来自

24.2.3 输入迭代器[input.iterators]

3) [...] Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. [...]

这个 IMO 限制了一些相当直接的优化(例如通过容器一次以查看它有多少元素)- 唉，动机不在问题的范围内。

为什么有这个要求？

Answer 1

输入迭代器用于迭代没有物质实现的范围(id est 它们的元素实际上并不存在于内存中的某个地方)，比如来自网络流的字节，或者来自/dev/的随机数序列随机的。考虑最后一个示例:一旦您使用了第一个随机数，就无法再次检索它。

另一方面，前向迭代器提供对具有物质实现(id est 所有元素实际上存在于内存中某处)或可以轻松重新计算†的范围的访问。就其本质而言，容器通常提供前向迭代器:容器本身就是范围的具体化。

有时可以将使用输入迭代器定义的范围转换为使用前向迭代器定义的范围，方法是简单地实现它:只需使用一次传递将整个范围复制到一个容器中，然后根据需要在该容器上进行迭代.显然，这并非在所有情况下都是可取的，有时甚至是不可能的:某些范围，例如/dev/random 中的字节，是无限的，永远无法完全实现。

如果算法可以一次性编写，就没有理由禁止它与输入迭代器一起使用。然而，当给定前向或更好的迭代器时，没有什么可以禁止这种算法使用执行多次传递的优化版本。

---

† 例如，所有偶数的范围不需要具体化容器中的所有数字，但可以很容易地从给定的迭代器重新开始，因为再次重新计算数字是可能的，而且成本很低。