Boost logo

Boost :

Subject: Re: [boost] new proposal: order statistics tree
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-01-08 04:13:57

On Tue, Jan 8, 2013 at 7:47 AM, Szymon Wojciechowski <sw10_at_[hidden]>wrote:

> I implemented augmented red-black tree which doesn't check the uniqueness
> of values. I have conducted a simple survey: I prepared 5 input files with
> unique 2,7*10e7 integers. The first data set has sorted values as other has
> randomized. I repeated 7 times on every input. A simple program reads from
> input integers and puts it to set (maybe I should use multiset) from
> VisualStudio or my order statistics tree. After that I measured time. Then
> program erases values from data structure in ordered way (from 0, 1, 2...).
> After that I also measured how much time it takes. I uploaded the results
> here: - it's a little bit strange.
> What kind of performance test would you think about?

Did you implement or is it possible to implement for this augmented red
black tree split, join and splice operations with logarithmic computational

As for tests, there are a number of performance tests of basic container
operations in the following projects:

1. For augmented dynamically allocated B+ trees:

I have added this link, since this project has results of performance tests
for Boost.MultiIndex.

2. For augmented array based B+ trees:

This project is prepared for Boost review. It compares performance of new
containers with standard containers and Boost.Container.
The file "boost_performance.cpp" uses Boost.Chrono timer. If your
containers are STL compliant you should not have any problem with this test

Vadim Stadnik

Boost list run by bdawes at, gregod at, cpdaniel at, john at