On 05/02/2011 12:49 PM, Scott McMurray wrote:
Have you considered building something atop Boost.Intrusive's Splay containers?<http://www.boost.org/doc/libs/1_41_0/doc/html/intrusive/splay_set_multiset.html>
That's looks great. I'll definitely keep that in mind when I get to the point of benchmarking and optimization.
Then you can just remove whatever's at the root of the tree each time, since moving the element to the root is the first step in deleting in a splay tree anyway, and you get good (average-case) performance for the "sometimes" inserts.
Actually, your "done" set could be a splay_set too, since (barring inserts) you'll be inserting an element that was a child of the previously inserted element...
So many data structures, so little time ... :-) - Marsh