Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-10-05 07:52:52

On Fri, Oct 5, 2012 at 2:20 AM, Francisco José Tapia <fjtapia_at_[hidden]>wrote:

>   The countertree iterators don't store the position, because after the
> creation of an iterator, if you insert or delete elements in the tree, the
> position of the element pointed bu the iterator can change. The countertree
> iterators need to travel to the root of the tree for to know their
> position, with the exception of the iterators end(), and rend().
>
>  I understand that the random access iterators permit you access directly
> to the element, without a sequential access. Commonly they are associated
> with the vectors with iterators O(1), and the iterators of a list or set
> with are sequential and not random access iterators O(N). The iterators of
> the vector_tree are in the middle O (log N), but permit you access to the
> elements directly without sequential access. I don't know other iterators
> similar.
>
> The dynamically allocated augmented B+ trees support the functionality of
both random access and bidirectional iterators. The computational
complexity of operators of these iterators is better than in proposed
augmented red black trees. However, I dropped the support of this
functionality in array based augmented B+ trees.
In addition to this, Boost.Container offers containers, such as
stable_vector, with random access iterators that are not invalidated by
insert/erase operations.    This is possible, since these containers have
features of both array based and dynamically allocated data structures.
 IMO, these iterators are superior to iterators in augmented dynamically
allocated data structures.

Regards,
Vadim Stadnik