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@lists.boost.org> 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