Re: [boost] [countertree] New Version

Subject: Re: [boost] [countertree] New Version
From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2011-05-02 13:49:37

On Mon, May 2, 2011 at 10:12, Marsh Ray <marsh_at_[hidden]> 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