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
Have you considered building something atop Boost.Intrusive's Splay
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...
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk