Boost logo

Boost :

Subject: Re: [boost] new proposal: order statistics tree
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2013-01-04 18:19:44


On Fri, Jan 4, 2013 at 3:39 PM, Szymon Wojciechowski <sw10_at_[hidden]>wrote:

>
> "Rene Rivera" <grafikrobot_at_[hidden]> pisze:
> > On Wed, Jan 2, 2013 at 3:46 PM, Szymon Wojciechowski wrote:
> >
> > >
> > > I would like to propose to add new data structure - order statistics
> tree.
> > > Briefly, it is container which allows logarithmic inserting, searching
> and
> > > erasing as in set, but additionally it permits to access elements via
> > > numerical value - key order. I have some ready implementation with all
> > > appropriate functions (without their all overloaded forms) with gtest
> > > regression list, but the code isn't boostified. The regression passes
> on
> > > gcc 4.6.3 and vs2010.
> > >
> > > Is there anybody interested in?
> > >
> >
> > How does it compare to <
> >
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.augment
> >
> > and the half dozen other augmented tree implementations that have
> appeared
> > in the Boost list? (one as recent as last year).
> >
>
> It is exactly, what you have shown in the article. However, is this
> implementation available somewhere? Generally, I can't find any
> implementation of this kind of tree except that from Rahul's links.
>

The current state of that TR is at <
http://svn.boost.org/svn/boost/sandbox/tree/>. Although a few notes about
it..

* The code is old and since Bernhard wrote it I don't know at the moment
the state of closely it follows the TR. Since most of it was written before
the TR.

* I've been updating the docs rather slowly (too many other projects going
on). But I'm hoping to get an update of the TR done by in the Spring. And
work again on the implementation after that.

-- 
-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk