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-06 07:50:14

On Sun, Apr 6, 2014 at 12:45 AM, Alexander Kuprijanov
<alexkupri_at_[hidden]>wrote:

>
>> Message: 11
>> Date: Fri, 4 Apr 2014 23:23:09 +1000
>> From: Vadim Stadnik <vadimstdk_at_[hidden]>
>> Could you please provide a figure that shows data association with nodes
>> in
>> your data structure?
>>
> I updated the doc, follow the link above.
>
>
Thank you for the figure!

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.

For comparison, please have a look at Figure 1 in the section "Design and
implementation of B+ trees" that shows an example of a string
representation. This data structures is a combinations of a segmented array
and a dynamically allocated B-tree. The difference is that this data
structure is a level-linked B+ trees. It has additional links so that nodes
at every internal level of the tree form a linked list. The main advantage
of the level-linked variant of B+ trees is that with multiple augmenting
they can support not only fast access and update operations on sequences of
elements, but also fast sequential summation algorithms, which have
logarithmic running time.

The first suggestion is to implement a container that provides a union of
interfaces of STL sequences and can be used as a replacement for
std::vector, std::list and std::deque. In the library "STL extensions" this
container is named std_ext_adv::sequence. In addition to this, the data
structure that you developed can be used to store sorted elements. Thus, it
can support interfaces of STL containers std::set, std::multiset, std::map
and std::multimap. Did you consider the development of these associative
containers?

I would suggest implementing all of these STL containers without fast
summation algorithms for the first version. The users will be able to take
advantage of interchangeable containers and choose the best one for a
specific application.

Regards,

Vadim Stadnik