Re: [boost] lifetime of ranges vs. iterators

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

On Mon, Sep 1, 2008 at 8:55 PM, Arno Schödl <aschoedl_at_[hidden]> wrote:
>> If I understand Giovanni's implementation correctly, it only needs to
>> expand one layer at a time.
>
> Let's expand it:
>
>  iterator begin() const{
>       return iterator(begin(m_range), end(m_range), m_f);
>  }
>
> -->
>
>  return iterator( iterator( begin(subrange), end(subrange), m_f ), iterator( end(subrange), end(subrange), m_f ), m_f);
>
> -->
>
>  ...
>
>
> The expansion will terminate when begin/end(sub...subrange) is the base iterator.
>Then the call is made to the filter_iterator ctor, which calls the
> associated_range<filter_iterator> ctor, which condenses everything back down.
>

I see the problem.

I think that for non complex iterators, the optimizer can still manage
to fix the problem.

For more complex iterators (think of an any_iterator, whose
constructor and copy operator happen to be fairly expensive), things
get bad.

A general fix is having the constructor of the filter iterator take a
range parameter instead of two iterators, and use that range to
directly initialize its containing range (note that the two ranges do
not need to be of the same type). That should take care of the doubly
recursive call in begin.

It doesn't fix end though, and we cannot pass a range because we
obviously do not have one. We need another constructor that only takes
a single iterator and initializes both ends of the subrange with that
iterator. You would still have a (tail and static) recursive call to
end(), but it would be O(N), which shouldn't be a problem. NRVO should
take care of eliminating excessive copying.

Arno, can you see other exponential expansions?

[btw, for long chains of filter and map iterators it is not really a
problem because you can always transform them exactly to one each of
map and filter iterator]

-- 
gpd