Boost logo

Boost :

Subject: Re: [boost] [countertree] New Version
From: Scott McMurray ([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? <>

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at