Response to Rene Rivera : You are right. I wrote the documentation in that format only by time economy. I wrote in a final format instead of do an intermediate format. I will do a first page of the documentation where indicate it is a preliminary library ,not accepted, and not part of the boost library. The idea about the namespace is right too. I willl change the boost namespace by other dependant of it. About the idea of the rank tree, it is very easy and fast to implement with the countertree library. The idea is very similar to the exposed in the previous message. You have the data stored in a vector, or a file or any other container. You have a “reference” to access to each elements. You implement the index as map or multimaps with pairs (Value, ”Reference”). Imagine you have several index. You make the query with upper_bound and lower_bound. With the countertree map and multimap you can know the size of every query in a O(log N) operation. In a countertree vector_tree, you insert only the “References” of the range with less elements. With the “Reference” , access to each element and check if the values of the others index are in the rank desired, if not , delete it of the vector_tree (It is a O(log N) operation). At the end of the process, in the vector_tree you have the valid “References” . I used this in a 3D locator in a simulator of silicon doping , and it was really fast, with the additional problem of a continuous creation and destroy of elements. In my opinion, if you have an easy way to implement it, it is unnecessary create a complex data structure in order to manage it. Response to Marsh Ray In all the containers of countertree, all the insertion or deletion operation are O(log N). The operation with the first and last elements are slighty faster , because there are pointers to them. But depending of the cost of the comparison, you can expect several millions of operations per second with 1 core, even with data structures of millions of elements. In my computer 1000000 of insertions and deletions in a vector_tree with 1000000 elements spend 0.631 seconds in win32 and 2.23 seconds with GCC 4.5 64 bits Response to Scott McMurray The splay tree must be rebalanced for to optimize the access. The most significant disadvantage is that the height of the splay tree can be linear. The countertree is fast, but if you need more speed, you can build a small cache over the tree, but must be carefully if you store too the position , because if you insert or delete in a previous position to the element stored in the cache, the position of the element change too. In my opinion, the red-black tree make outdated the splay trees, except , perhaps in a very limited environment.