[boost] Iterator Adaptors

From: Anthony Williams (anthwil_at_[hidden])
Date: 2002-09-16 06:54:51

After submitting my bounded_generator_iterator policies for use with the
iterator adaptors, I came across the following:

If you use your bounded_generator_iterator in expressions of the form *it++,
then you will often generate _two_ values, and discard one of them. This is
because of the combination of the way the iterator adaptor template works, and
the way my bounded_generator works.

The "normal" generator iterator assumes the generator function can be called
any number of times, and calls the function on construction and increment. The
"bounded" generator iterator assumes that certain instances of the generator
may not be callable, as they are end-of-sequence markers. Therefore the
generator is only called when explicitly dereferenced, or when incremented
without a prior dereferencing. This works well, provided that no copies of
undereferenced iterators are made. If an undereferenced iterator is copied,
then both copies will call the generator when they are dereferenced or
incremented. For true copies, this is OK --- it just makes the generator
iterators behave like other Input Iterators, of which only one of a pair of
copies can be used (like istream_iterators).

The problem occurs with the way that iterator_adaptor implements
post-increment --- copy, increment, return copy. This makes a pair of copies
--- the original, and the new one --- of which only one is usable, but then
uses both --- the original is incremented, and the copy is returned for
dereference. For Forward Iterators and greater, this is OK. For Input
Iterators, it may not be.

For the bounded_generator, one safe solution is just to call dereference
inside the post increment, before copying, however this is not correct for all
possible input iterators.

The only safe solution is to return a magic proxy (as permitted by the Input
Iterator requirements) that can only be dereferenced, when the category is
InputIterator --- the current iterator can then be dereferenced, and the value
stored in the proxy which is to be returned, and then incremented.

e.g.

template<typename value_type>
class iterator_return_proxy
{
private:
    value_type data;
public:
    iterator_return_proxy(value_type data_):
        data(data_)
    {}
    value_type operator*() const
    {
        return data;
    }
};

then in iterator_adaptor:

    iterator_return_proxy<value_type> operator++(int) { 
        iterator_return_proxy<value_type> tmp(policies().dereference(*this));
        ++*this; return tmp; }

when the category is input_iterator_tag.

Anthony