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

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-19 22:35:17

Cory Nelson 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?

I suggest you use something known as an interval tree, which can
identify overlapping ranges in O(log N) time.  It essentially stores
intervals sorted based on their start values and keeps a record in each
node of the greatest end value in any of its children or grandchildren
or great-grandchildren, etc.

If you're industrious you can probably hack up your STL's rb tree
implementation (the one it uses for the associative containers) to
support the end value; that's what I did years ago when I needed such a
thing.  You just need to figure out how to maintain the "greatest end
value in subtree" fields when the tree is rebalanced.

At the time I remember that literature on interval trees was a little
hard to find, but  if that's still true, once you understand the data
structure you should be able to figure out the O(log N) search algorithm.

Good Luck,

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