Re: [boost] Input caching iterator adaptor

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-30 16:28:22

On Saturday 30 June 2001 03:31, you wrote:
> ----- Original Message -----
> From: "Douglas Gregor" <gregod_at_[hidden]>
>
> > Hello all,
> > I've written a simple iterator adaptor that caches the result of
> > dereferencing the underlying iterator. This sort of adaptor is essential
>
> to
>
> > make the transform_iterator adaptor standards conforming.
>
> Not so. transform_iterator_generator generates standard conforming input
> iterators.

It comes down to this, I think: If I have an input iterator i, must I get the 
same result if I evaluate *i twice without an intervening increment? Consider 
a somewhat naive implementation of a a function that returns the maximum 
value from a pair of input iterators:

template<typename InputIterator>
typename InputIterator::value_type
max_value(InputIterator first, InputIterator last)
{
  typedef typename InputIterator::value_type T;
  for(T max =  *first++; first != last; ++first)
    max = (*first > max)? *first : max;

  return max;
}

In reassigning "max", *first may be evaluated twice, so this implementation 
of max_value requires that consecutive dereferences return the same value for 
it to be correct. Is the algorithm incorrect?

I have not yet been able to find the answer to this within the specification 
of iterators. One argument is that input stream iterators cache their results 
(see 24.5.1p1), so we can use proof by example to say that two consecutive 
dereferences should return the same value <G>.

The most convincing argument I've heard that consecutive dereferences are all 
equivalent is to consider std::find_if. It returns an input iterator (which 
it would have dereferenced already to call the predicate). std::find_if would 
be useless if you couldn't rely on getting the same value back when you 
dereferenced the result.

[snip forward iterator stuff]

> > The code, documentation, and test for the input caching iterator is in
> > the vault at:
> > http://groups.yahoo.com/group/boost/files/input_cache_iter.zip
> >
> > The policy is short enough that I'll post it here as well for discussion.
>
> I notice that it places a default-constructibility constraint on T.

Sad but true. Note that STLport and GCC's libstdc++ v3 (both variants of 
SGI's STL) require their value types to be default constructible.

> > If there is sufficient interest, I'd like to integrate this iterator
>
> adaptor
>
> > with the iterator adaptors library.
>
> This adapter may in fact be useful, but I think you need to think about the
> rationale and application a bit more carefully. The one you gave doesn't
> seem to work.
>
> -Dave

        Doug