You have these characteristic in the Countertree library ( https://github.com/fjtapia/countertree_2.0) You have a data structure with the same interface than the std::vector and std::deque, with access by position like the vectors. All the operations ( read, write, modification ) are O (logN). You can find a concurrent and not concurrent version of the data structure. You have Random access iterators with access time O(logN) ( you can run a std::sort over the data structure with good results). You have too, a STL compatible set, multiset , map and multimap, with concurrent versions, with a new type of mutex designed for to improve the concurrency. And associated to this , parallel algorithms over these data structures. The library is pending of the final approval since more than a year ago. Actually, I am busy with the parallel sorting algorithms. When finish with it, I will continue with the Countertree I have designed the main part of the new version, designed for a very big trees, with new parallel algorithms. By example : create a std::set with 30000000 random elements uint64_t, my computer needs 52 seconds, with the new algorithms with 1 thread 6 seconds , and with 4 threads 3 seconds. This can be important, for the data base in memory, and in many search applications. ( A single server permit millions of operations per second ). When finish the new version , I will propose to the Boost community for the acceptation test