Re: [boost] new proposal: order statistics tree (Szymon Wojciechowski)
On Fri, Jan 04, 2013; 4:33am, "Rahul Sr" <srivasrrahul@gmail.com> 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++-... 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
"Leo Goodstadt" <leo.goodstadt@llew.org.uk> 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++-...
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
participants (2)
-
Leo Goodstadt -
Szymon Wojciechowski