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: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2014-04-09 05:31:42

On Tue, Apr 8, 2014 at 11:07 PM, Alex Kupriianov <alexkupri_at_[hidden]>wrote:

> 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.
>
>
Thank you for the comparison of performance.

The performance of an algorithm is normally better in a native data
structure than in its STL variant unless the latter can take advantage of a
fast allocator. When you implement STL compliant containers your data
structures can be compared with many other data structures: linked lists,
red-black trees, arrays, vectors, and other augmented trees.

The current implementation of augmented B+ trees that you tested is quite
general. At this stage I would like to avoid the problem of premature
optimization. The use of space and performance of specific algorithms can
be improved in this variant of B+ trees. This task requires specification
of priorities.

Regards,

Vadim Stadnik