On 09/11/2015 08:16 AM, Rene Rivera wrote:
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.
The complexity of all operations in my container are already documented in the link I provided. I've most often heard this data structure refered to as a counted tree, my implementation in particular is a counted B+Tree, the elements it contains are not ordered.