Re: [boost] lifetime of ranges vs. iterators

From: Neil Groves (neil_at_[hidden])
Date: 2008-08-29 06:59:01

On Fri, Aug 29, 2008 at 11:12 AM, Arno Schödl <aschoedl_at_[hidden]>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.
>
>
Option a, is the solution that I prefer due to the lower memory overhead. I
am of the opinion that there is no need to provide a uniform lifetime
arrangement since it would often make optimal implementations impossible.
The difference_range should be implemented with the requirement that it be
held for as long as the iterators. The iterator invalidation of the standard
containers being different for same named operations on different classes is
perhaps an appropriate analogy.

>
>
> 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?
>
>
I don't think this needs to be unified. I think there is a preference for
range lifetimes to be as forgiving as possible, and for most ranges the
range lifetime may be less than the underlying iterators. This is very
convenient for the vast majority of cases. I also see that there are times
when this is too expensive, and then a range implemented with an alternative
arrangement is the logical choice. In practice it does not appear to
measurably effect the number of defects in software.

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

I hope this helps. Best wishes,

Neil Groves

>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>