Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback

Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback
From: Alex Kupriianov (alexkupri_at_[hidden])
Date: 2014-04-08 09:07:45

Vadim Stadnik <vadimstdk <at> gmail.com> writes:
> 
> IIUC, this data structure is a variant of an augmented B+ tree, since it
> stores elements of a data set in external nodes only and provides access to
> the elements through a B-tree, which implements augmenting with the counts
> of elements. It is a combination of two data structures, which is one of
> the main features of B+ trees. This data structure is quite similar to
> augmented B+ trees implemented in the library "STL Extensions" submitted
> for Boost review https://github.com/vstadnik/stl_ext_adv_review.
> 
Hi, Vadim!
I've compared current performance of our containers. Mine outperforms yours 
roughly by 1.5-2 times in random single insert, delete and random access. 
However, yours outperforms mine up to 3 times on large arrays in iterative 
access. 
Additionally, yours keeps additional pointer per each element. This seems me 
quite unnecessary and ineffective. Yours takes roughly 2 times more memory.
I understood for myself, how to implement iterators, so that they will be 
relatively fast and compatible with std::vector interface. This will be my 
priority #1, because everybody wants stl compatibility.

Best regards,
A.K.