On Fri, Aug 29, 2008 at 11:12 AM, Arno Schödl <aschoedl@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.
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@think-cell.com Technical Director
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 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