Angelika Langer - Training & Consulting
HOME | COURSES | TALKS | ARTICLES | GENERICS | LAMBDAS | IOSTREAMS | ABOUT | CONTACT | Twitter | Lanyrd | Linkedin
 
HOME 

  OVERVIEW

  BY TOPIC
    JAVA
    C++

  BY COLUMN
    EFFECTIVE JAVA
    EFFECTIVE STDLIB

  BY MAGAZINE
    JAVA MAGAZIN
    JAVA SPEKTRUM
    JAVA WORLD
    JAVA SOLUTIONS
    JAVA PRO
    C++ REPORT
    CUJ
    OTHER
 

GENERICS 
LAMBDAS 
IOSTREAMS 
ABOUT 
CONTACT 
Output Stream Iterators

Output Stream Iterators
Output Iterators
Why they differ from other iterators.

C++ Report, June 1998
Klaus Kreft & Angelika Langer


 
 

In our last two columns we explained (among other topics) the implementation of two iterators from the output iterator category: the insert_interator and the ostream_iterator . (See [ 1 ] and [ 2 ] for further details.) While it is natural that both implementations were highly similar, the way certain member functions were implemented is surprising if not confusing. Typical examples are the implementations of operator++() , operator++(int) , and operator*() , which all do nothing but return *this . In those columns, we explained these peculiarities in the context of each iterator implementation. This time, we want to dig a bit deeper. We want to see if there is a reason for the surprises, and what this reason is. Before we start these examinations let's pass in review iterator implementations in general, in order to point out in which aspects insert_interator and the ostream_iterator differ from a ‘normal’ iterator.

Recap: Implementing An Iterator For The Standard Library

According to interface they support, iterators fall into five different categories:


Each category adds new features to the previous one. In brevity:

  • Input iterators allow algorithms to advance the iterator and give "read only" access to the value.
  • Output iterators allow algorithms to advance the iterator and give "write only" access to the value.
  • Forward iterators combine read and write access, but only in one direction (i.e., forward).
  • Bidirectional iterators allow algorithms to traverse the sequence in both directions, forward and backward.
  • Random access iterators allow jumps and "pointer arithmetics".
The set of requirements that describes an iterator category are relatively relaxed. Consider that algorithms are function templates and iterator types are template arguments of algorithms. No more is required of an iterator type than that the function template can be instantiated, that is, certain expressions involving the iterator must compile. The iterator is entirely free to provide the required functionality by built-in operations, member functions, global functions, etc. . If user-defined operators or functions are involved not even a particular signature is required of them, because conversions, promotions, or casts can be involved.

Despite the abundance of options that exist for implementing an iterator type, there is a common, canonical approach for implementing iterators. We will demonstrate it using an example: traceIter . The traceIter is an iterator adapter that falls into the forward iterator category in our example. The functionality of the traceIter is quite simple: It adapts an existing iterator and traces when any of its operations get invoked.

The traceIter ’s implementation is given is Listing 1.

template <class Iter>
class traceIterator : public iterator<forward_iterator_tag,
                                      iterator_traits<Iter>::value_type,
                                      iterator_traits<Iter>::difference_type,
                                      iterator_traits<Iter>::pointer,
                                      iterator_traits<Iter>::reference>
{
public:
    traceIterator() {}
    traceIterator(Iter fi) : myIter(fi) {}
    // plus compiler generated copy constructor
    reference operator*() const
    {
        trace ("operator*() called !");
        return (myIter.operator*());
    }
    pointer operator->() const
    {
        trace ("operator->() called !");
        return (myIter.operator->());
    }
    traceIterator& operator++
    {
        trace ("operator++() called !");
        myIter.operator++();
        return (*this);
    }
    traceIterator operator++(int)
    {
        trace ("operator++(int) called !");
        traceIterator tmp = *this;
        myIter.operator++(0);
        return (tmp);
    }
private:
    bool compare(traceIterator rhs) const
    {
        trace ("operator==() called !");
        return (myIter == rhs.myIter);
    }
    friend bool operator==<Iter>(const traceIterator<Iter>&, const traceIterator<Iter>&);
    void trace(string txt) const { cout << txt << endl; }
    Iter myIter;
};

template <class Iter> inline bool operator==(const traceIterator<Iter>& x, const traceIterator<Iter>& y)
{ return x.compare(y); }
using rel_ops::operator!=;

Listing 1: The traceIter iterator adapter

The Base Class Template: Iterator

Any iterator of non-built-in type should be derived from the base class template iterator . The iterator base class is defined as:

template<class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&>
struct iterator
{
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category;
};
By deriving from this template an iterator specifies:
  • its iterator category,
  • its value type, which is the type of the value referred to by the iterator,
  • the difference type, which is a type that is capable to express the difference between two iterators,
  • types associated with the value type: the value’s pointer and reference type.
Inheritance from the iterator base class template also assures that the type names value_type , difference_type , pointer , reference , and iterator_category get injected into the public section of a derived iterator. The definition of these names is essential for the usability of an iterator, because other abstraction from the standard library framework rely on these names (e.g. the iterator_traits ).

As we have already mentioned, the traceIter shall be a forward iterator. For this reason, the first template argument for the base class template iterator is forward_iterator_tag , which is a type that is already defined in the standard library. For all other template parameters we use the types that come with the iterator that is adapted.

Operations Required By The Forward Iterator Category

Because the traceIter shall be a forward iterator, the standard requires that at least the following operations can be applied to this iterator:

  • Default construction.
  • Copy construction.
  • The operator * .
  • The operator -> .
  • The postfix and prefix increment operators.
  • Operators == and != which allow to compare two iterators for equality and inequality.
The operations required for other categories differ according to the different functionality that comes with the respective categories. The operations can be sorted into three groups. We are going to discuss these three groups and the typical approach for there implementations in the following.

Operations that give access to the referenced value.

The operators * and -> are those operations that give access to the value that is referenced by the iterator. They are typically implemented as the iterator’s public members: operator*() and operator->() . The operator*() returns a reference to the value, while the operator->() returns a pointer to it. Their return types are denoted by the inherited nested types reference and pointer . Note, that for an input iterator (which is similar to a forward iterator except that it allows only read access to the value) the return types are the const reference respectively the const pointer to the value. Their nested type names, however, are still reference and pointer .

Operations that move the iterator.

For a forward iterator, the postfix and prefix increment are the only two operations that can be used to move the iterator. They are typically implemented as the iterator’s public members: operator++() and operator++(int) . They return a reference to the iterator itself so that other iterator operations can be chained to an increment operation. Other iterator categories support additional operations to move the iterator. Bidirectional iterators for example can also be decremented, and random access iterators allow to add and subtract values of the difference type to and from the iterators. They are generally implemented in a similar way as the increment operators.

Operations that allow to compare iterators.

Forward iterators allow to be compared for equality and inequality. Typically an operator==() is implemented as a global function, because as a public member it would not allow to behave symmetrically with respect to the two operands. No operator!=() is provided because the standard supplies a global template operator operator!=() based on the negation of operator==() ’s result. Other iterator categories can support more sophisticated ways for iterator comparison. Random access iterators, for instance, are required to define an ordering, that is operator<(), etc.
 
 

Further Reading

This recap is quite brief and focused on those areas where the typical iterator implementation differs from those of an output iterator. For further information, take a look at some of our older articles. [ 4 ] explains in more detail and with additional background information (including iterator_traits ) how iterators from the standard library are implement. [ 3 ] explains the same issues about iterators from the original STL. An comprehensive example for a user defined iterator, which can work with the STL and the standard library, is given in [ 5 ].
 
 

Output Iterators Are Different

The source code of the insert_iterator given in Listing 2 reveals some differences compared to the general rules for iterator implementation given above.

template <class Container>
class insert_iterator :
public iterator<output_iterator_tag,void,void,void,void>
{
public:
    typedef Container container_type;
    insert_iterator<Conatiner>(Container& c, typename Container::iterator i)
    : container(c), iter(i) {};
    insert_iterator<Container>& operator=(typename Container::const_reference value)
    {
        iter = container->insert (iter, value);
        iter++;
        return *this;
    }
    insert_iterator<Container>& operator*() { return *this; }
    ^insert_iterator<Container>& operator++() { return *this; }
    insert_iterator<Container>& operator++(int) { return *this; }
protected:
    Container* container;
    typename Container::iterator iter;
};
Listing 2: The implementation of insert_iterator











Output Iterators Allow Only Write Access

Let's start with those operations that give access to the referenced value. No operator->() is provided. The reason for this is simple: It is not required for an output iterator.

The implementation of the operator*() looks highly surprising. One would expect that operator*() gives access to the value referenced by the iterator That is what the canonical implementation of the traceIter in the example above does: it returns a reference to the value. Why do output iterators like insert_iterator return a reference to the iterator itself instead? The crucial point is that an output iterator is only allowed to give write access to the referred value. So, what should it return? There is no way to specify write-only access to an object in C++; solely read-only access can be expressed in C++ by using the qualifier const . The requirements of prohibiting read-access means that an output iterator’s operator*() cannot give direct access to the referred value at all. Obviously we need a work around to implement write-only access. Let’s consider a typical situation in which the write-only access to the output iterator’s value is needed:

*iter = newValue; After applying the operator * to the iterator, a new value is assigned. As we mentioned earlier in the recap, neither an iterator’s exact operations nor their exact signature is specified. For this reason, an output iterator can define a special assignment operator that allows to assign a new value to the value that the iterator currently refers to. This assignment operator, together with an operator*() that returns *this , permits the write access to the referenced value and prohibits the read access. The insert_iterator ‘s special assignment operator is: insert_iterator<Container>& operator=(typename Container::const_reference value) . Out example line of code: *iter = newValue; evaluates to different operations depending on the category of the iterator. For an output iterator, such as the insert_iterator , it will evaluate to the following sequence of invocations:
  • As user defined operators gets invoked from left to right, insert_iterator::operator*() gets invoke first. It does nothing but return *this .
  • This allows that insert_iterator::operator=(typename Container::const_reference value) can be invoked on iter . Next the body of this operator (shown in Listing 2) is executed.
For an iterator of any other category (except input iterators, which do not allow write access at all) it evaluates differently. Let's consider the traceIter from our previous example:
  • First, traceIter::operator*() gets invoked, which returns a reference to the value referred to by the iterator.
  • To handle the assignment of the new value to the returned reference of the old value, the assignment operator for traceIter::value_type is called.
While the special assignment work around helps output iterators to provide write-only access to their referenced values, it does not come without a disadvantage. Because of the special assignment operator that does all the work and the operator*() that does nothing but return *this , it is possible to omit the operator*() entirely and assign the value directly to the iterator: iter = newValue; We discourage using such code in any algorithm. In the world of generic programming, an iterator with more capabilities than an output iterator, e.g. a forward iterator, can be used in place of an output iterator. Then, unfortunately, the code will not compile and the algorithm is restricted to output iterators.

The fact that an output iterator’s operator*() cannot give direct access to the referred to value has another consequence for the implementation of output iterators. It is reflected in the template parameters that are used for the base class template iterator . insert_iterator for example is defined as:

template <class Container> class insert_iterator :
public iterator<output_iterator_tag,void,void,void,void> { ... };
The value type and its associated pointer type and reference type are void . The reason for this is fairly simple. Since the ostream_iterator ’s operator*() does not allow direct access to the referred value, it does not make sense to specify the value type at all. Making the value type in the iterator base class template void is the way to declare the value type as unspecified. When the value type is unspecified, consequently its associated types should also be unspecified. That explains why the pointer type and the reference type are void , too. There is a different reasoning that motivates why the difference type is also void . We explain it below.

Immovable Output Iterators

While the implementation techniques described above apply to all output iterators, insert_iterator and ostream_iterator have other implementation details in common that are not necessarily typical for all output iterators. These are their implementations of the prefix and postfix operator ++ , which all do nothing but return *this . The reasons is that both iterators cannot really be advanced.

  • The insert_iterator has truly static semantics: It indicates the fixed position before which new elements are inserted. Hence its ++ operators should not have any real effect.
  • The ostream_iterator in a way has dynamic semantics: The position of the underlying stream changes whenever an object is assigned to the de-referenced ostream_iterator . This position change is caused automatically when the ostream_iterator ‘s special assignment operator uses the value type’s stream inserter, and there is no task left for the ostream_iterator ‘s ++ operators.
The fact that insert_iterator s and ostream_iterator s cannot really be advanced has further consequence: the difference of two iterator objects cannot be expressed. What is the difference between two iterators? The difference between two random access iterators can be calculated as iter2-iter1 , because random access iterators support pointer arithmetics. For other categories, the difference is calculated as distance(iter1,iter2) . In general, the difference of two iterators is the number of increments or decrements needed to get from iter1 to iter2 . How many increments does it take to get from one immovable insert_iterator to an other iterator of the same type. Infinitely many, or none, depending on how you see it. The point is that incrementing an insert_iterator or an ostream_iterator does not advance the iterator and therefore no other iterator can ever be reached. This explains why the difference type template parameter, which is the third parameter from the iterator base class template, is void for insert_iterator and ostream_iterator .

Summary

The implementations of the insert_iterator and ostream_iterator from our last columns showed some interesting similarities. Some of them stem from the fact that output iterator’s operator*() cannot grant direct access to the value referred by the iterator, because there is no way to specify write-only access in C++. The result is an implementation for output iterators that is different from other iterators' implementation. Other similarities are based on the coincidental commonality that insert_iterator and ostream_iterator cannot be advanced.

References

  1. Insert Iterators

  2. Klaus Kreft & Angelika Langer
    C++ Report, February 1999
  3. Stream Iterators

  4. Klaus Kreft & Angelika Langer
    C++ Report, April 1999
  5. Iterators in the Standard Template Library (STL)

  6. Klaus Kreft & Angelika Langer
    C++ Report, July 1996
  7. Iterators in the Standard C++ Library

  8. Klaus Kreft & Angelika Langer
    C++ Report, Nov./Dec. 1996
  9. Building an Iterator for STL & Standard Library

  10. Klaus Kreft & Angelika Langer
    C++ Report, February 1997

 
 

If you are interested to hear more about this and related topics you might want to check out the following seminar:
Seminar
 
Effective STL Programming - The Standard Template Library in Depth
4-day seminar (open enrollment and on-site)
IOStreams and Locales - Standard C++ IOStreams and Locales in Depth
5-day seminar (open enrollment and on-site)
 
  © Copyright 1995-2003 by Angelika Langer.  All Rights Reserved.    URL: < http://www.AngelikaLanger.com/Articles/C++Report/OutputIterators/OutputIterators.html  last update: 22 Nov 2003