4.2.1 Input Iterators and Output Iterators

An input iterator has the fewest requirements. It has to be possible to declare an input iterator. It also has to provide a constructor. The assignment operator has to be defined, too. Two input iterators have to be comparable for equality and inequality. operator* has to be defined and it must be possible to increment an input iterator.

Input Iterator Requirements:

Output iterators have to satisfy the following requirements:

Output Iterator Requirements:

These abstract requirements should get clear if you look at special input and output iterators provided by the library - the istream iterator and the ostream iterator.

"To make it possible for algorithmic templates to work directly with input/output streams, appropriate iterator-like template classes are provided", [2]. These template classes are named istream_iterator and ostream_iterator. Assume we have a file filled with 0's and 1's. We want to read the values from a file and write them to cout. In C++ one would write:

ifstream ifile ("example_file"); 
int tmp;
while (ifile >> tmp) cout << tmp;

Output (example): 110101110111011

Note: The 0's and 1's in the file have to be separated by whitespaces (blank, tab, newline, formfeed or carriage return). To use ifstream include fstream.h

To use streams like cin and cout and operator<<, operator>> for streams include iostream.h

Using an istream and an ostream iterator in combination with the algorithm copy enables us to write the following:

ifstream ifile ("example_file"); 
copy (istream_iterator<int, ptrdiff_t> (ifile),         
      istream_iterator<int, ptrdiff_t> (),
      ostream_iterator<int> (cout) );

Note: To use istream_iteator or ostream_iterator include iterator.h

If you have to include algo.h (as in this example), iterator.h is already included by algo.h

The output will be the same as in the above C++ example. copy is an algorithm that takes two iterators to specify the range from which elements are copied and a third iterator to specify the destination where the elements should be copied to. The template function looks as follows:

template <class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, 
                     OutputIterator result);

The template arguments have semantic meaning, they describe the iterator categories of that iterators provided to the function at least have to be. The iterators specifiying the input range have to be at least input iterators, that means that it must be possible to increment and dereference them to get the appropriate values. The iterator specifying the result position has to be at least of the output iterator category. Since forward, bidirectional and random access iterators satisfy the requirements of input and output iterators, they can be used instead with the same functionality.

Dereferencing an output iterator has to result in a lvalue, that means it has to be possible to assign a value to the dereferenced output iterator (that is as you know an object of the value type of the iterator). For output iterators, the only valid use of the operator* is on the left side of the assignment statement:

a is an output iterator, t is a value of value type T
*a = t; valid
t = *a; invalid

For output iterators, the three following conditions should hold: Assignment through the same value of the iterator should happen only once:

ostream_iterator<int> r (cout);
*r = 0;
*r = 1; 
is not a valid code sequence.

Any iterator value sould be assigned before it is incremented:

ostream_iterator<int> r (cout);
is not a valid code sequence.

Any value of an output iterator may have at most one active copy at any given time:

i and j are output iterators, a and b are values written to a iterator position
i = j;
*i++ = a;
*j = b;
is not a valid code sequence.

For both input and output iterators algorithms working on them are assumed to be single pass algorithms. Such algorithms are never assumed to attempt to pass the same iterator twice.

For input iterators r and s, r==s does not imply ++r == ++s:

ifstream ifile ("example_file")     // example_file: 0 1 2 3
istream_iterator<int, ptrdiff_t> r (ifile);
istream_iterator<int, ptrdiff_t> s (ifile);

(r==s) ? cout << "equal" : cout << "not equal";
cout << endl;


cout << *r << endl;
cout << *s << endl;

(r==s) ? cout << "equal" : cout << "not equal";
cout << endl;

Output: equal

Output: 2

Output: 3

Output: equal

Note: For two input iterators a and b, a == b implies *a == *b. For istream iterators, this condition doesn't hold.

When incrementing an input iterator, a value is read from the input stream and stored temporarily in the input iterator object. Dereferencing the input iterator returns the value stored.

The constructor of the istream iterator takes an input stream as its argument from which values are read. To yield an end-of-stream iterator which represents the end of file (EOF) of the input stream, the default constructor has to be used. To successfully construct an istream iterator, two template arguments have to be provided, too. The first argument specifies the type of the elements read from the input stream, the second is ptrdiff_t, that is the type of the difference of two pointers in the actual memory model (see section 4.5 - allocators).

The constructor of the ostream iterator can take one or two arguments. However, the first argument specifies the output stream to which values are written. The alternative second argument is a string which is printed between the written values. ostream_iterator takes a template argument which determines the type of the values written to the output stream.

It will often be asked to copy elements from an input stream (e.g. a file) directly into a container:

vector<int> v;

ifstream ifile ("example_file"); 
copy (istream_iterator<int, ptrdiff_t> (ifile),         
      istream_iterator<int, ptrdiff_t> (),
      back_inserter(v) );

The function back_inserter returns a back_insert_iterator. This is a so-called iterator adaptor (explained in detail in section 4.4) and is a kind of past-the-end iterator to the container. The container, for which a back insert iterator is to be created, has to be handed over to back_inserter. When a value is written to the back insert iterator, it is appended to the specified container as its last element. If, for example, v.end() is used instead of the back insert iterator in the example above, all the values inserted will be written to the same vector position (v.end()), because v.end() isn't incremented after writing to it. This increment is internally done by the back insert iterator by calling the container member function push_back.

Continue with section 4.2.2

Back to index

Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996