Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk