Re: [boost] [Iterator Adaptors] Bug in filter_iterator_policies

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-24 13:49:45

Oh, nevermind: we store the end iterator in the policies so that's not a
problem. OK, the change looks good; please patch the CVS, Doug.

Thanks,
Dave

P.S. you might want to give a little thought to avoiding redundant predicate
checks when an iterator is compared often. Maybe it would be best to cache
the state of whether the predicate is satisfied.

P.P.S. you also might want to give a little thought to the same issues when
used with distance measurement and ordered comparison.

----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, December 24, 2001 1:46 PM
Subject: Re: [boost] [Iterator Adaptors] Bug in filter_iterator_policies

> I'm a little nervous about this change: what if the one-past-the-end
> iterator for a range fails to satisfy the predicate?
>
> ----- Original Message -----
> From: "Douglas Gregor" <gregod_at_[hidden]>
> To: <boost_at_[hidden]>
> Sent: Monday, December 24, 2001 10:52 AM
> Subject: [boost] [Iterator Adaptors] Bug in filter_iterator_policies
>
>
> > Hello,
> >   There's a bug in filter_iterator_policies, where the predicate may not
> be
> > satisfied for the underlying iterator under extreme circumstances. The
> > problem is here:
> >
> > template <class IteratorAdaptor1, class IteratorAdaptor2>
> > bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
> >   { return x.base() == y.base(); }
> >
> > Consider the following code, for "first" and "last" being iterators with
a
> > filter_iterator somewhere in them:
> >
> > while (first != last)
> >   *first++;
> >
> > Now make *first an operation that can modify the result of the predicate
> on
> > the next iterator in the sequence. Then we have:
> >
> > first++ advances the underlying iterator, then satisfies the predicate.
A
> > copy of the previous iterator is returned
> >
> > *first dereferences the previous iterator, possibly changing the result
of
> > the predicates in-between the old position and the new position.
> >
> > One simple fix is to instead use:
> >
> > template <class IteratorAdaptor1, class IteratorAdaptor2>
> > bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
> >
>
> >   satisfy_predicate(const_cast<Iterator&>(x.base()));
> >   satisfy_predicate(const_cast<Iterator&>(y.base()));
> >   return x.base() == y.base();
> > }
> >
> > This fix will work well with one additional (reasonable) restriction on
> the
> > predicate: if the predicate ever returns false for an iterator, all
> > successive predicate calls for that iterator must return false.
> >
> > Just to prove that I'm not crying wolf, go ahead and look at the
> > deletion_test testcase in the "current" (November 25) Boost.Signals
> library.
> > I had precisely the same bug in the slot call iterator.
> >
> > I can check in the fix and documentation of the above limitation, or
> provide
> > a real patch.
> >
> > Doug
> >
> > Info: http://www.boost.org  Send unsubscribe requests to:
> <mailto:boost-unsubscribe_at_[hidden]>
> >
> > Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
> >
> >
> >
>
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>