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.
> 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  and binary trees .
 T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein. Introduction to
Algorithms. 2nd Edition, MIT Press and McGraw-Hill, 2001.
 R. Sedgewick and K. Wayne. Algorithms. 4th Edition, Addison-Wesley,
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk