Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2013-01-07 16:31:51

On Mon, Jan 7, 2013 at 3:57 PM, Szymon Wojciechowski <sw10_at_[hidden]>wrote:

> "Gottlob Frege" <gottlobfrege_at_[hidden]> pisze:
> > On Wed, Jan 2, 2013 at 4:46 PM, Szymon Wojciechowski wrote:
> >
> > >
> > > Hi,
> > >
> > > 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?
> > >
> > > Best regards,
> > > Szymon Wojciechowski
> > >
> > >
> > This should be compared against using boost multi-index.  I suspect it
> has
> > significant differences, but might still be enlightening.
> > Tony
> >
>
> Could you explain to me, what do you mean, please?
>
> Best regards,
> Szymon Wojciechowski
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

 Basically both an order statistics tree and boost multi-index are examples
of containers with multiple indices.  I suspect there may be interesting
results from a compare/contrast type of study.

Boost MultiIndex allows indexing of a container via any number/type of
indices.  So you could have a container indexed via key, and also indexed
via integer.  Now the difference, I think, is that MultiIndex uses
independent indexes - changing a entry's key from "alpha" to "beta" doesn't
change its integer index from 1 to 2.

So that is a significant difference.  Might be worth mentioning in docs or
somewhere, just to avoid confusion.

But furthermore, I could probably implement the same behaviour as a order
statistics tree by using Boost.MultiIndex internally (and maintaining the
interrelationships of the indices as needed).  Would that be drastically
less efficient?

And also, how do the interfaces compare?  Should there be any
alignmen/consistency t in the interfaces, so that some template code could
use either?  Not sure how much template code exists that requires "any
container with 2 indices, one of which is an int".  Probably consistency of
interface is more important for learning/understanding/remembering than for
template code.

Tony