Types of Iterator:Output VS. Input VS. Forward VS. Random Access Iterator

Types of iterator : Output vs. Input vs. Forward vs. Random Access Iterator

If you can, find and read "The C++ Standard Library: A Tutorial and Reference". This book contains a whole chapter about STL iterators.

Here is a little something from the book:

Iterator Category  Ability                          Providers
-----------------  -------------------------------  ----------------------------
Input iterator     Reads forward                    istream
Output iterator    Writes forward                   ostream, inserter
Forward iterator   Reads/writes forward             forward_list,
                                                      unordered_[multi]set,
                                                      unordered_[multi]map
Bidirectional it.  Reads/writes forward/backward    list, [multi]set, [multi]map
Random access it.  Reads/writes with random access  vector, deque string, array 

Can input iterators be used where forward iterators are expected?

Can input iterators be used where forward iterators are expected?

No. The difference between an input iterator and a forward iterator is that an input iterator is a "single-pass" iterator but a forward iterator is a "multi-pass" iterator.

Once you advance an input iterator, you can no longer access the previous elements in the range. If you make a copy of an input iterator, both iterators remain valid until you advance one of them; then the other ceases to be valid.

With a forward iterator, you can iterate over the sequence any number of times, you can have multiple usable copies of an iterator at once, you can use multiple iterators into the sequence at the same time, and you can dereference an iterator as many times as you'd like before advancing it again.

So, my question is this: Is my compiler in error for allowing my call to search using istream_iterator?

There is no rule that the compiler must reject the code.

The rule is that you must be sure to pass the right type of iterator that is required by the function. Sometimes if you pass the wrong type of iterator you get a compilation error. Sometimes the program will compile but will not function correctly. Sometimes things will appear to work correctly. The results are undefined if you violate the requirements of calling the function.

---

Generic algorithms usually impose requirements on their type parameters by assuming that the type arguments provided actually meet the requirements. So, for example, an algorithm that only works with random access iterators will "enforce" this requirement by performing some operation that only works with random access iterators (e.g. it + 1). If the iterator doesn't support that operation (operator+(iterator, int) here), the code will fail to compile.

The problem is that there is no way to distinguish between input iterators and forward iterators this way: you can increment and dereference both of them; the difference is in how many times you can perform each of those operations and the sequence in which you can perform those operations. So, an algorithm like std::search will use *it and ++it, which will "work" just fine for input iterators, at least insofar as the code will compile.

In theory, an algorithm could use the std::iterator_traits class template to determine whether an iterator is an input iterator or a forward iterator; I don't know whether that would be permitted by the C++ language standard. If the library did that, you could get a compilation error for your code, which would be better.

Are Forward-Iterators Output-Iterators?

In C++11, no, forward iterators are not required to be output iterators. The output iterator requirements are like an extra set of requirements that an iterator can have, regardless of the rest of the iterator requirements it meets. Forward iterators are only required to be input iterators (§24.2.5/1):

A class or pointer type X satisfies the requirements of a forward iterator if:

• X satisfies the requirements of an input iterator
• ...

In fact, a forward iterator meets the output iterator requirements only if it is a mutable iterator to a sequence of copy-assignable types^†.

^{† or a constant iterator to a sequence of types with operator=(...) const defined with mutable members.}

More to the point, the iterator tags are defined specifically by the standard as (§24.4.3/2):

namespace std {
  struct input_iterator_tag { };
  struct output_iterator_tag { };
  struct forward_iterator_tag: public input_iterator_tag { };
  struct bidirectional_iterator_tag: public forward_iterator_tag { };
  struct random_access_iterator_tag: public bidirectional_iterator_tag { };
}

As you can see, forward_iterator_tag should only inherit from input_iterator_tag.

---

In C++03, it is stated that forward iterators satisfy the requirements of input and output iterators:

Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified.

But this is then contradicted in the following paragraph, stating that a constant forward iterator would not satisfy the requirements for output iterators:

Besides its category, a forward, bidirectional, or random access iterator can also be mutable or constant depending on whether the result of the expression *i behaves as a reference or as a reference to a constant. Constant iterators do not satisfy the requirements for output iterators, and the result of the expression *i (for constant iterator i) cannot be used in an expression where an lvalue is required.

However, the definition of the iterator tags is identical to as in C++11. There was a defect report for this contradictory wording, but it was closed as Not a Defect because the first quote is in the "introductory text" of the section and would likely be reworded in the future (which it was).

---

The SGI definition of a forward iterator is given as a refinement of both input and output iterators (thanks to @BenVoigt in the comments).

Nonetheless, if we take a look at the implementation of the iterator tags, we find that forward_iterator_tag still only inherits from input_iterator_tag.

Looks like this has been an area of quite a bit of confusion in the past, but if VS2012 is defining forward_iterator_tag as inheriting from both output_- and input_iterator_tag, I can only assume it is a bug.

Are c++ forward/bidi/random iterators always output iterators?

C++03 says (24.1/4):

Besides its category, a forward, bidirectional, or random access
iterator can also be mutable or constant depending on whether the
result of the expression *i behaves as a reference or as a reference
to a constant. Constant iterators do not satisfy the requirements for
output iterators, and the result of the expression *i (for constant
iterator i) cannot be used in an expression where an lvalue is
required.

cplusplus.com chose not to mention that. The wording in the standard is confusing, since it states "Forward iterators satisfy all the requirements of the input and output iterators", and contradicts that in the next paragraph to say that some forward iterators do not satisfy the requirements of output iterators.

C++11 simplifies a little (24.2.1/3-4):

Forward iterators satisfy all the requirements of input iterators and
can be used whenever an input iterator is specified; Bidirectional
iterators also satisfy all the requirements of forward iterators and
can be used when- ever a forward iterator is specified; Random access
iterators also satisfy all the requirements of bidirectional iterators
and can be used whenever a bidirectional iterator is specified.

Iterators that further satisfy the requirements of output iterators
are called mutable iterators. Nonmutable iterators are referred to as
constant iterators.

Canonical way to define forward output iterator

The canonical thing to do is to inherit from std::iterator<std::forward_iterator_tag, T> only. Iterators have only one category.

The standard has no algorithms (or other uses) for an output iterator that is also a forward iterator. All uses of output iterators in the standard require only single-pass.

Instead, the standard has the idea of mutable vs. immutable iterators of categories forward/bidi/randomaccess. All the algorithms that need to write through iterators, and that require better than single-pass, also read through the same iterators they write through. This is std::remove, std::sort and other mutating algorithms.

The difference between mutable and immutable iterators is not detected by iterator tag, it's determined by whether the assignment expressions are well-formed. So for example if you pass an iterator to std::sort that's immutable, then the algorithm won't compile anyway, so there's generally no need for an input iterator to also be tagged with output_iterator_tag. All algorithms that require an OutputIterator will Just Work with a mutable ForwardIterator, again there is no need for it to be tagged with output_iterator_tag.

If you have different needs from those of the standard algorithms then I can't immediately think of a reason that your proposal won't work for your iterators. But it won't detect mutable standard iterators. For example std::deque<int>::iterator and int* have iterator category random_access_iterator_tag, not your private tag and not anything to do with output_iterator_tag. So you would probably be better off defining your own traits class rather than hoping to adapt the existing iterator_traits::iterator_category to provide the information you want.

Input Iterators classification

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.

---

Related Topics