Francisco José Tapia
[snip] The concurrent version is *thread safe with all the operations*, one thread can be read and other writing over the same data structure in a safe mode ( as you can see in 2.3 -examples)
I haven't looked too carefully at the library, but certainly a tree that maintains rank information is a useful data structure. In principle it seems it would be ideal to make it as generic as possible, i.e. built on top of a generic binary search tree that supports maintaining an arbitrary aggregate statistic, i.e. with a user-specified type and user-specified update function. Your countertree, which would provide random access iterators, etc. could then be a simple wrapper over the more generic tree library. It also seems it would be ideal if your library could interface with the Boost Multi Index Containers library, as that would maximize usage options, but I don't know how feasible that is. Another comment is that my own experience is that more often than not, in a multithreaded program, synchronization is needed for more than just maintaining the invariants of a particular data structure, like your countertree, and therefore it generally makes sense for any necessary locking to be handled by the application rather than by any particular data structure library. That is, the set of operations that need to appear atomic will depend on the application, and may likely involve things outside the control of your single data structure. Lock-free data structures are the exception, where you actually gain something by integrating the syncronization with the data structure.