Re: [boost] Determining interest in container with efficient random access insert and erase

Subject: Re: [boost] Determining interest in container with efficient random access insert and erase
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2015-09-11 11:16:33

On Fri, Sep 11, 2015 at 5:10 AM, Chris Clearwater <chris_at_[hidden]> wrote:

> Greetings,
>
> I have written a library with the intention of submitting it to
> Boost.Container. My container implements O(log n) random access
> insert/erase and has a strong focus on performance while supporting the
> interfaces of the standard library sequence types. An example application
> would be the character buffer of a text editor.
>
> Useful links:
>  - Source code: https://github.com/det/segmented_tree_seq
>  - Documentation: http://det.github.io/segmented_tree_seq/
>  - Benchmarks: https://github.com/det/segmented_tree_seq/tree/benchmarks
>
> Any feedback is greatly appreciated.
>

First.. You are going to need to add some documentation as to how your
container works with regards to complexity order. Second.. Your
implementation is rather hard to follow (but this is not a necessarily a
bad thing). I say that because I was trying to figure out how your
container attains the O9log n) you claim. And AFAICT, because of this <
https://github.com/det/segmented_tree_seq/blob/master/include/boost/container/segmented_tree_seq.hpp#L1278>,
that your container is just another implementation of an order statistic
tree <https://en.wikipedia.org/wiki/Order_statistic_tree>. Which is a data
structure that has been proposed for Boost (and standardization) at various
times.

-- 
-- Rene Rivera
-- Grafik - Don't Assume Anything
-- Robot Dreams - http://robot-dreams.net
-- rrivera/acm.org (msn) - grafikrobot/aim,yahoo,skype,efnet,gmail