[Boost-users] Re: Efficient removal of std::list items

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-20 07:42:21

Victor A. Wagner Jr. wrote:
>> >> are the lists sorted?
>> >
>>Cory Nelson wrote:
>> > Yep.  If you're going where I think you're going (binary search), I
>> > was about halfway through the modifications when I opened the email.
>> > Lack of sleep will get to you... :(
>>

Dave Abrahams wrote:
>>That'll only work if the ranges are non-overlapping.  Otherwise you'll
>>need to use an interval tree to avoid an O(N) search for each interval
>>you want to remove.
> 
Victor A. Wagner Jr. Replied:
> you're likely correct, but we were looking at handling some stuff with 
> imprecise (error probabilities) results and we were on the track of doing 
> some stuff along these lines.  The project was cancelled (shame, I think it 
> would fit well with the physical quantities systems... you just can't 
> measure things as closely as you'd like) so we never got to see how/if all 
> of the algorithms would work or whether we'd have to specialize them for 
> "fuzzy" numbers.  

Have you seen the Boost Interval library?

> I think it's worth pursuing for ranges tho.

Why should the OP pursue anything that's likely (your words) to be
O(N^2) when there's a known and proven O(N log N) approach?

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com