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

Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase (Glen Fernandes)
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2014-04-04 09:23:09

On Fri, Apr 4, 2014 at 9:42 AM, Alexander Kuprijanov <alexkupri_at_[hidden]>wrote:

> Hi, again,
> I've implemented a container which should replace vector and have
> O(log(N)) for insert/delete.
> Please review.
> https://github.com/alexkupri/array/blob/master/description/description.txt
> The code is small, the description is verbose.
>

Could you please provide a figure that shows data association with nodes in
your data structure?

In the simplest form, it can be done as in counted B-trees already
mentioned by Adam. For better representation you can have a look at the
description of augmented red-black trees [1] and binary trees [2].

Regards,
Vadim Stadnik

[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein. Introduction to
Algorithms. 2nd Edition, MIT Press and McGraw-Hill, 2001.
[2] R. Sedgewick and K. Wayne. Algorithms. 4th Edition, Addison-Wesley,
2011.