Boost logo

Boost :

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-09-01 14:53:15

On Mon, Sep 1, 2008 at 8:37 PM, Steven Watanabe <watanabesj_at_[hidden]> wrote:
> David Abrahams wrote:
>> on Mon Sep 01 2008, "Giovanni Piero Deretta" <>
>> wrote:
>>> Need to think about it. Could you give a practical example of an
>>> iterator adapter needing three iterators?
>> E.g., a bidirectional filtered_iterator needs to be prevented from
>> stepping off both ends of the underlying data to avoid undefined
>> behavior.
> Do we really have to worry about stepping off the beginning?
> I mean, you aren't allowed to decrement the iterator at the
> beginning of a range, anyway, and if you decrement any other
> iterator, the predicate is guaranteed to stop it before it goes
> off the beginning.

That's right! It can only be one of three cases: or the range is empty
and you can't move at all; or you are at the beginning and you can't
go back anyway; or it exist at least one element before the current
one such as the predicate is true.

It's so obvious that I never though of it. <ashamed/>

... and in fact boost::filter_iterator only holds the current and end iterator.

>> On the other hand, you shouldn't have to pay for those endpoint
>> comparisons all the time, which tells me that something may be wrong
>> with the design.
> Hmm. Iterating over a range using a filtered_iterator
> on an underlying range of size n for which the predicate
> is true on m elements results in m + n + 2 comparisons
> of the underlying iterator and n calls to the predicate.
> A hand-coded loop
> for(; begin != end; ++begin) {
> if(f(*begin)) {
> // do stuff
> }
> }
> uses only n + 1 iterator comparisons.
> I'm not sure how often this is significant, but
> the only way I can see to avoid it is
> to combine the iterator increment and comparison
> into a single step.

for filter_iteator at least, I guess that the badly predictable 'if'
will dominate over everything else.


Boost list run by bdawes at, gregod at, cpdaniel at, john at