Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Luc Touraille (luc_touraille_at_[hidden])
Date: 2012-10-03 17:34:18

Hello Francisco


De : Francisco José Tapia <fjtapia_at_[hidden]>
>À : boost_at_[hidden] 
>Envoyé le : Mercredi 3 octobre 2012 22h23
>Objet : [boost] [countertree] Formal Review Request
> 
>Hi all,
>I would like to request a formal review of the library “Countertree +
>Suballocator” [countertree]
>
[snip]
>
>For the people who don't know this project, this is a description :
>
>*COUNTERTREE*
>
>This library is an implementation of a binary red-black counter tree. This
>tree have an additional counter in each leaf. This permit the access to the
>elements by the position, like in a vector. It is a random access container
>with random access iterators .

I just had a look at your library because I was curious to see how you managed
to implement random access iterators on a binary tree, but it seems the
iterators you provide are not really random access: as far as I can tell from
your code, moving an iterator forward or backward is an O(log N) operation
(according to your remark about the "shift" function in file
"countertree/tree/node.hpp"), and not a constant-time operation.

Am I missing something?

Luc

P.S.: This is my first post on this mailing list, so please point out any rule or
policy I could be breaking. Moreover, English is not my mother tongue, so please
forgive the potential errors I could make.