Re: [boost] Input caching iterator adaptor

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-06-30 16:38:24

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>
>
> 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?

Yes. Table 72 sez:

"If a==b and (a,b) is in the domain of == then *a is equivalent to *b."

> 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 don't think so (unless you want it to work on empty ranges ;-)).

> 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>.

I think the table sez it all.

> 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.

So what has this got to do with your proposal?

> 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.

Huh? Which value types are you referring to? Not the value_types of standard
containers! At least I know this about STLPort.

> 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.

I don't think I've changed my mind yet...

-Dave