Re: [boost] new proposal: order statistics tree (Szymon Wojciechowski)

Subject: Re: [boost] new proposal: order statistics tree (Szymon Wojciechowski)
From: Szymon Wojciechowski (sw10_at_[hidden])
Date: 2013-01-07 15:49:08

"Leo Goodstadt" <leo.goodstadt_at_[hidden]> pisze:
> > On Fri, Jan 04, 2013; 4:33am, "Rahul Sr"  wrote:
> > > On Wed, Jan 2, 2013 at 3:46 PM, Szymon Wojciechowski  wrote:
> > > 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.
> >
> > Will it be like this?
> > http://stackoverflow.com/questions/11230734/c-stl-order-statistic-tree
> >
> http://www.opensource.apple.com/source/llvmgcc42/llvmgcc42-2336.9/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
> 
> The libstdc++ policy based data structure (pb_ds) order statistic tree only
> has "set" behaviour. It takes a certain amount of extra work to use it as a
> replacement for multiset and multimap. They recommend using a set (tree) of
> lists to use pb_ds::tree like a multiset. However, this obviously doesn't
> work for order_statistic tree: each of the duplicates is only counted once
> (each list of duplicates is a single element in the tree).
> Does your order statistic tree allow duplicates?
> Leo Goodstadt

My current implementation allows duplicated values and handles it correctly - each node has it's own rank. However, of course I think that it's easy and probably necessary to get both variants: unique and not unique.

Best regards,
Szymon Wojciechowski