Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-08-29 08:50:51

For iterators, the make_ helpers are great:

vector<int> vecnA;
vector<int> vecnB;

DoSomethingWithRangeThatStoresIterators( 
        make_difference_iterator( vecnA.begin(), vecnA,end(), vecnB.begin(), vecnB.end() ),
        make_difference_iterator( vecnA.end(), vecnA,end(), vecnB.end(), vecnB.end() )
);

The equivalent with ranges, supposedly easier, would now look like this:

vector<int> vecnA;
vector<int> vecnB;

difference_range< int, int > diffrng( vecnA, vecnB ); // watch out with scope
DoSomethingWithRangeThatStoresIterators( diffrng ); 

as opposed to the much nicer:

vector<int> vecnA;
vector<int> vecnB;

DoSomethingWithRangeThatStoresIterators( make_difference_iterator( vecnA, vecnB ) );

If we drive this stacking to one or more levels, things pretty quickly become pretty ugly. Do we really want that?

Arno

-----Original Message-----
From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]] On Behalf Of David Abrahams
Sent: Friday, August 29, 2008 1:01 PM
To: boost_at_[hidden]
Subject: Re: [boost] lifetime of ranges vs. iterators

on Fri Aug 29 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

> Hello,
>
>  
>
> some adaptor ranges need certain constant information about their
> underlying ranges. For example, iterating over a forward
> "difference_range", the difference between two sorted ranges, requires
> access to the ends of the underlying ranges. These two additional
> iterators are constant, they do not change when the
> difference_iterator is incremented.
>
>  
>
> Now, where should this additional constant information be stored?
>
>  
>
> a) In the difference_range, and each iterator holds a reference to the
> difference_range? That requires the difference_range to be alive as
> long as its iterators are alive. This may be difficult to ensure if
> the difference_range is a temporary.
>
> b) In the iterators, so the lifetime of adaptor iterators is
> independent of the adaptor range. Of course, one can use shared_ptrs
> and so on, but still the iterators are ultimately responsible to keep
> that information available.
>
> This initially seemed more natural to me, but if implemented naively
> by storing the additional iterators in the iterator itself, it leads
> to storage bloat: each difference_iterator needs 4 instead of 2 of its
> underlying iterators. When stacking difference iterators, the
> difference in required storage grows exponentially: instead of 2^N,
> you need 4^N storage...
>
> I feel that in order to solidify the range concept, one needs to make
> a choice whether a) or b) is "standard", because any user of ranges
> would need to know. Any thoughts on this?

Aren't standard containers supposed to satisfy the Range concepts?  When
the container is destroyed, its iterators are invalidated, right?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229