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

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-19 23:16:37

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... :(
> 
> 
> On Sun, 19 Dec 2004 20:22:01 -0700, Victor A. Wagner Jr.
> <vawjr_at_[hidden]> wrote:
>> At Sunday 2004-12-19 17:54, you wrote:
>> >This seems like the type of thing boost may have an answer to, yet I
>> >still havn't found it:
>> >
>> >I have two std::lists, about 50,000 items in each.  The items are all
>> >number ranges so two uints start and end.  I need to remove one list
>> >from the other - exact matches or subranges only.  Currently I'm using
>> >remove_if() to remove/shrink/split them but it is taking forever,
>> >around 30sec.
>> >
>> >Anyone know of a better solution?
>> 
>> are the lists sorted?

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.

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