Vadim Stadnik
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.