Re: [boost] lifetime of ranges vs. iterators

From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2008-09-01 14:37:05

AMDG

David Abrahams wrote:
> on Mon Sep 01 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> 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.

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

In Christ,
Steven Watanabe