Re: [boost] Interval Trees & ICL

Subject: Re: [boost] Interval Trees & ICL
From: Dave Abrahams (dave_at_[hidden])
Date: 2010-12-15 16:22:25

At Wed, 15 Dec 2010 21:34:44 +0100,
Joachim Faulhaber wrote:
> 
> 2010/12/15 Dave Abrahams <dave_at_[hidden]>:
> > On Wed, Dec 15, 2010 at 12:49 PM, Joachim Faulhaber
> > <afojgo_at_[hidden]> wrote:
> >>> The two main candidates would be something like to boost::split_interval_set or
> >>> a centred interval tree
> >>> (along the lines of http://en.wikipedia.org/wiki/Interval_tree).
> >>> It seems to me that the characteristics of an interval tree differ sufficiently
> >>> from the containers defined in ICL that they might make a useful addition.
> >>
> >> No doubt, interval_trees would be a useful addition to the library.
> >> For certain use cases they perform better than the interval container
> >> currently available in the ICL.
> >
> > In the cases where I've needed them, only a container that preserved
> > the inserted intervals
> 
> interesting
> 
> > (and information about overlaps)
> 
> isn't this the hairy part?

Not too hairy; an interval tree I made by modifying my STL's rbtree
implementation worked just fine.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com