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

Question

从

3) [...] 输入迭代器上的算法永远不应该尝试通过同一个迭代器两次。它们应该是单通道算法。[...]

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

为什么有这个要求？

score 9 · Accepted Answer

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

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

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

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

† 例如，所有偶数的范围不需要具体化容器中的所有数字，但是可以轻松地从给定的迭代器重新开始，因为重新计算数字是可能且便宜的。

score 4 · Accepted Answer

选择的名称已经暗示了原因：将迭代器视为对输入流（如键盘输入或网络流）的迭代。没有办法对流进行两次迭代，因此存在限制。

在需要优化并且我们不介意提高迭代器要求的情况下，前向迭代器或更强大的东西是自然的选择。

2 回答 2