On Mon, May 2, 2011 at 10:12, Marsh Ray <marsh@extendedsubset.com> wrote:
However, with your container I'd have decent access to an arbitrary element of the set. Then the part that was remove_first_element(set&) could instead be "remove randomly selected element from set". This way I'd expect average case rather than worst-case performance.
What would be even cooler though would be operations like "give me an element among those most efficient to remove" and "most efficient to insert before/after".
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> 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... ~ Scott