Example of Input Iterator where `end()` actually denotes one-past-the end?

Question

I'm currently trying to make sense of some ideas wrt. C++ iterators, and I have been wondering ...

Given an Incremental / Single Pass / Input / Output Iterator, can there actually exist such a thing as a one-past-the-end position/element for such an Iterator, or are all InputIterator end() Iterators "naturally" some form of singular values that are treated specially by operator==?

I think what I mean is this: For anything from ForwardIterator on "upwards", it can make total sense to have a trivial operator== that just checks whether the two iterator objects, regardless of end-ness, point to the same element. Can this ever make sense for an InputIterator?

Answer 1

An InputIterator that is not a ForwardIterator is one for which incrementing it invalidates the prior value (meaning any iterator with the same value, i.e. any copies of the original).

In general it is only valid to compare iterators from "the same sequence" (that is, were one is reachable from the other). For the iterators you're talking about, this means the only valid comparisons are between:

• two equal non-end iterators
• two end iterators
• an end iterator and a non-end iterator

You can't (by the guarantees of this interface) compare two unequal non-end iterators because you never have two valid non-end iterators where one is reachable from the other. The one that's "behind" has already been invalidated.

So it seems likely that you could implement the iterator such that it contains a data member that has one value in end iterators and a different value in non-end iterators. For the typical example of a stream iterator, that data member could be bool isEndOfStream. Then operator== would not need to contain any special case code, it just needs to compare that field. It would then be natural for all end iterators to be interchangeable: that field is the only thing on them that will ever be used.

It might well be efficient, since iterators become end iterators far less frequently than iterators are compared, so a write in the rare case to allow the common case to be just a read and compare would seem sensible. Such an iterator comparison would return true for any two non-end iterators, but that's fine because either they're genuinely equal (in which case returning true is correct) or else comparing them is not valid (in which case behavior is undefined).

Answer 2

The canonical example is the istream_iterator (template), which becomes singular when the underlying stream extraction fails. This can be detected by comparing against a default-constructed iterator of the same type, which is equivalent to a singular iterator. For example:

std::vector<int> v(std::istream_iterator<int>(std::cin), {});

This is the equivalent of:

std::vector<int> v;
for (int n; std::cin >> n; ) { v.push_back(n); }

To stress again: all one-past-the-end istream iterators are equivalent, independent of the stream they came from. These iterators are an example where "singular" (= not associated with any container) and "one-past-the-end" (= result of incrementing the last dereferenceable iterator) mean the same thing.