Re: [boost] Re: new component, extent_set<>

From: joel de guzman (djowel_at_[hidden])
Date: 2002-01-01 13:14:13

----- Original Message ----- 
From: "Nathan Myers" :
 
> I hadn't thought of them as separable components; I got thrown off
> by the reference counting.  The range_run<> type is indeed very similar 
> to extent_set<>, and more complete.
...
> 
> I agree, we could merge range_set and extent_set with probably minimal 
> upset to either.  A policy argument for whether to use a vector or a map 
> to represent it, to trade off space against update speed, also seems 
> workable, in principle.  
> 
> An important difference is that with a tree representation, incrementing 
> or decrementing the iterator can be pretty expensive, so the algorithms
> need to be careful not to do it unnecessarily.  (That is why extent_set<>
> stores its extents in reverse order; map<>::lower_bound gives the right
> answer, then.)

I'd gladly contribute the vector implementation and modify it according
to agreed upon interfaces. I agree with you fully that "range" is indeed
not a good name. I find "extent" better and avoids 'overloading' stl's
range concept. However, I do find the stl-like first-last interface rather 
cumbersome. I don't know what difficulties the stl designers encountered 
with a range vs. iterator interface. I haven't experienced any problems with 
the range (er, extent) interface. Also, have you decided to use closed-ranges
instead of half-open ranges (er, extents :-)?

> It's not clear to me whether all these should be unified under a policy
> parameter, or just presented as a family of components.  Probably the
> latter, although they might be able to share some implementation code.
> in the way that std::set<> and std::map<> do.

The range-run / extent-set can and should be unified (IMO). The semantics
and the interface can be synchronized. I am not sure about the others
though as these are quite specialized.

--Joel