Re: [boost] lifetime of ranges vs. iterators

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

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.

-- 
gpd