为什么InputIterators只通过一次? [英] Why are InputIterators one pass only?

问题描述

来自

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

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

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

This IMO restricts some fairly straight-forward optimizations (such as passing through the container once to see how many elements it has) - alas, the motivation is outside the scope of the question.

为什么要这样做?

推荐答案

输入迭代器用于遍历没有实质实现的范围(id元素的元素实际上不在内存中的某个位置)，例如来自网络流或/dev/random中的随机数序列.考虑最后一个例子:一旦消耗了第一个随机数，就无法再次检索它.

Input iterators are used to iterate over ranges that don't have a material realization (id est their elements do not actually exist somewhere in memory), like bytes from a network stream, or a sequence of random numbers from /dev/random. Consider this last example: once you consume the first random number, there is no way to retrieve it again.

正向迭代器提供对具有实质性实现(它们的所有元素实际上都存在于内存中的某个地方)或可以轻松重新计算的范围的访问.从本质上讲，容器通常提供正向迭代器:容器本身就是范围的实现.

Forward iterators, on the other hand, provide access to ranges that either have a material realization (id est all their elements actually exist somewhere in memory) or that can be easily recomputed†. By their very nature, containers usually provide forward iterators: the containers themselves are the materialization of the range.

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

Ranges defined with input iterators can sometimes be converted to a range define with forward iterators, by simply materializing it: just use the single pass to copy the whole range into a container, and then iterate on that container as much as you like. Obviously this won't be desirable in all situations, and sometimes it is not even possible: some ranges, like the bytes from /dev/random, are infinite and can never be materialized in full.

如果算法可以单遍编写，则没有理由禁止将其与输入迭代器一起使用.但是，在给定正向迭代器或更好的迭代器时，没有什么可以禁止这种算法使用执行多次通过的优化版本的.

If an algorithm can be written in a single pass, there is no reason to forbid its use with input iterators. However, there is nothing that forbids such an algorithm from using an optimised version that performs multiple passes, when given forward or better iterators.

†例如，所有偶数范围都不需要在容器中具体化所有数字，但是可以很容易地从给定的迭代器重新开始，因为它可以廉价地重新计算数字.

† For instance, a range of all the even numbers does not need to materialize all numbers in a container, but one can easily start again from a given iterator since it is possible and cheap to recompute the numbers again.

这篇关于为什么InputIterators只通过一次?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！