Re: Potential order statistic tree?

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2020-12-29 09:06:38

On 28/12/2020 3:51, René Ferdinand Rivera Morell via Boost wrote:
> On Sun, Dec 27, 2020 at 6:00 PM Soronel Haetir via Boost <
> boost_at_[hidden]> wrote:
> 
>> Would there be interest in adding an order statistic tree to the boost
>> library?
>>
> 
> I had to search my Boost dev email history to recall how many times that
> data structure has been suggested... It's at least half a dozen times :-)
> It's been suggested enough that Boost Multiindex already supports it <
> https://www.boost.org/doc/libs/1_75_0/libs/multi_index/doc/tutorial/indices.html#rnk_indices>.
> Hence you'll need to point out a comparison between what you did and what
> exists (and possibly what has been suggested in the past) to better inform
> why your version of this should be adopted. As, clearly, there's historical
> interest.

There was a pull request to Boost.Intrusive adding Augmented binary 
search trees. At that time there was not much interest from other users, 
but it seems a good starting point, it does not seem a very big patch:

https://github.com/boostorg/intrusive/pull/3

We'd need to add tests to this feature to make sure it is not broken in 
newer versions.

Best,

Ion