Re: new component, extent_set<>

From: ncmcantrip (ncm-yahoospam_at_[hidden])
Date: 2001-12-30 03:03:47

--- In boost_at_y..., Darin Adler <darin_at_b...> wrote:
> On 12/26/01 12:26 AM, Nathan Meyers <ncm-yahoospam_at_c...> wrote:
> 
> > boost::extent_set<> implements a set of half-open ranges on a 
> > scalar type, with automatic splitting and merging, appropriate
> > for managing ranges of disk blocks or video frames.
> 
> On a previous project in 1995, my colleague Waldemar Horwat 
> implemented three different data structures like the one you
> propose. One we called RangeSet was like the extent_set you 
> propose. We also had RangeMap that mapped half-open ranges to
> values. 

Interesting: in my application I also am using an extent map,
probably for the same reason.  If extent_set<> turns out to
be welcome, I will package up extent_map as well.

> And we had IncrementalRangeMap that
> mapped half-open numeric ranges to numeric value ranges of the 
> same size.  The IncrementalRangeMap was an efficient data 
> structure to express what goes where when you are rearranging
> something.

I'd like to learn more about this.

> The one thing I'm slightly uncomfortable with is the interface 
> that uses separate integers rather than something like 
> half_open_range. I'm not sure I can clearly articulate the 
> reason I'd prefer using half_open_range in the interface, 
> and I'm also not certain how it would affect the details,
> but I suspect that I'd prefer the higher-level interface even 
> if it has a cost.

You mean that you'd rather see set.insert(boost::range(100,200))
in place of set.insert(100,200)?  

It would help to centralize error checking, and make overloading
safer.  On the ISO/ANSI C++ Standard effort we encountered several
problems with template overload matching that would have been 
avoided if the STL used an explicit range type.  Still, I chose 
not to expose a range type mainly because the STL doesn't.  

Back when the STL was still being prepared for submission as
part of the standard library, I suggested it should use a range
type in its interfaces.  Stepanov said they had tried that and 
it had been a disaster.  I don't know whether that was because 
of the primitive compiler they were using (cfront) or something 
more fundamental.  It might be worth asking again; things might
be different today.

Nathan Myers
ncm at cantrip dot org