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