Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-02 01:26:31

> > Isn't my problem concrete enough? I need a stackable difference_range without
> > exponential storage bloat. 

> Yeah, but why?  What algorithm are you trying to implement that leads
> you to think about stacking difference_range?  I don't imagine that a
> stacked difference_range is a good way to do anything efficiently.

> For example, if you're trying to do compute something like

>    A - B - C - D

> where A,B,C, and D are sorted ranges, and you're doing it without a
> heap, it *will* be needlessly inefficient.

The RangeEx documentation writes something like "what algorithms are to containers, adaptor ranges are to ranges". Whenever you are applying one (non-permutating) algorithm to a container, and then another and then another, you can stack range adaptors. It's like lazy evaluation of a Haskell list. 

Looking through our code for adaptor ranges, I find:

unique_range
union_range
difference_range
filter_range
concat_range

These ranges are all actually used in our program. All these ranges need an end iterator, and any stacking of any combination of these ranges leads to the problems we are discussing here. I don't find this impractical.

-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