14

I was reading Stanley Lippman's book C++ Primer to learn more about C++ 11.

In the chapter on Generic Algorithms he mentions that iterators used in the generic algorithms can be classified into 5 types based on the operations they support : input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators.

Quote from his book:

Input iterators can read elements in a sequence. They must provide the following operators - equality (==), inequality (!=), dereference (*), postfix & prefix increment (++) and the arrow operator (->). Input iterators may be used only sequentially. We are guaranteed that *it++ is valid, but incrementing an input iterator may invalidate all other iterators on that stream. As a result there is no guarantee that we can save the state of an input iterator and examine an element through that saved iterator

I have trouble understanding the quote in bold. Why would incrementing an input iterator which is meant only for reading elements invalidate other iterators? Why cant we save the state of an input iterator?

Improve this question

3 Answers 3

Reset to default
10

An input iterator can refer to anything that models an input stream, which includes:

  • a file on a physical disc
  • a human typing on a keyboard
  • bytes sent over a network connection

While it may be possible to save the state of an input stream in some cases, it is impossible in general (the file could have changed or have been deleted, the human forgets what he has typed, the network connection also has no memory). Therefore you cannot save an input iterator.

To allow a different possible implementations and optimizations (e.g. buffering), the standard allows that incementing an input iterator invalidates all other iterators of that stream.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

An example might illustrate it:

Assume you have a stream with an (tiny) internal buffer and an input iterator referencing to that buffer. If you increment the input iterator, all saved input iterators, referencing that buffer, will become invalid as soon as the stream buffer gets new content (underflows).

Regarding the comment:

Different algorithms in C++ utilizing iterators have different requirements on the iterator. An algorithm which just needs an input iterator, does not require any previous state of that iterator. However, a forward, bidirectional, ..., iterator fulfill the requirements of an input iterator and can be used in algorithms requiring an input iterator.

Improve this answer

2 Comments

So when you or Stanley uses the term stream, you don't mean the containers (sequences) in STL but just some input stream like cin or fstream or something similar? So can I safely assume that the quote above refers only to iterators referring to streams like these and not for iterators into containers. The reason why I got confused is because Stanley mentions that input iterators are required in the context of algorithms like find and accumulate which are typically ones that we would use on elements in a container.
Thanks Dieter Lücking.
4

Typically, input iterators don't have an underlying container in memory. The classical example is an std::istream_iterator. When you increment one of the iterators, you actually advance in the underlying external sequence (the file), which means that the other iterators on that sequence are also modified.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.