Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Luke Simonson (simoluk_at_[hidden])
Date: 2012-10-03 23:39:00

>>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?

I think that he means he implemented O(log N) operator[] on the
container and presumably can perform O(log N) iterator arithmetic,
allowing him to provide the same syntax as random access containers
and iterators.  However, since constant time is a requirement of STL
random access iterator concept he probably should rephrase his
description of the library.

I'm not sure I see the use case of O(log N) operator[] or O(log N)
iterator arithmetic on maps and sets.  I find the sub-allocator much
more interesting.  Can't we implement the same allocation scheme using
C++11 stateful allocators?  Does this really need special support
within the containers themselves?  There has been some recent
discussion of the need for a Boost.Allocator library.

Regards,
Luke