Why are InputIterators one pass only?

Question

From

24.2.3 Input iterators [input.iterators]

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

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.

Why this requirement?

Answer 1

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.

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.

Answer 2

The name chosen already gives a hint as to why: think of the iterator as iterating over an input stream such as keyboard input or a network stream. There is no way to iterate over a stream twice, hence the restriction.

In situations where optimization is desired and we don't mind upping the requirements from the iterator, a forward iterator or something even more powerful is the natural choice.

Related question: What's the difference between input iterators and read-only forward iterators?