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