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

With my commercial background I am very septical about O(lg(N)) search algorithms as they do not work well on modern hardware unless you are very careful with the data layout. A vector will linear search faster than a tree with up to a few hundred elements. Easy to prove and search for Stroustrup's opininion on complex data structures. A middle-first tree is often better (I don't now if there is an academic equivlent). Store the middle element first in a vector and the two quartiles second and third etc. The first few and last few accesses are in the same cache lines. I see a lot of pointers and allocated data structures in this as well as about eight levels of indirection of push_back which will be fun in debug mode :) I don't want to piss on the bonfire... Andy. On 11/09/2015 16:16, Rene Rivera wrote:

On Fri, Sep 11, 2015 at 5:10 AM, Chris Clearwater 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.

--- This email has been checked for viruses by Avast antivirus software. http://www.avast.com