Re: [boost] [countertree] New Version c.f. Intrusive Splay containers

Subject: Re: [boost] [countertree] New Version c.f. Intrusive Splay containers
From: Marsh Ray (marsh_at_[hidden])
Date: 2011-05-02 14:16:25

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