Boost logo

Boost :

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:


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.


Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229

Boost list run by bdawes at, gregod at, cpdaniel at, john at