I examined your documentation, and it looks very interesting the R-trees. My idea with the countertree is provide a binary balanced tree, with the additional feature of access by the position like a vector. In the unsorted structures like vector_tree, and in the sorted structures like set, map,multiset and multimap. This feature can be useful sometimes, but mainly provide comfort to the SW developers, you can manage a map with a for loop , like in a vector. Reexamining the R-trees, I remember an old project, which perhaps can be interesting to you. Many years ago I implemented the functionality of a R-tree, with 3D objects using countertrees. The capability of know the position of the iterators was extremely useful, in order to optimize the search. The insertion, deletion and access are O (logN) operations. I don't know the true utility of this, because I must study in deep the R-trees, and check the performance of the two systems, in order to evaluate them. The implementation run well with any number of dimensions. If you are interested, say me and I will write you a description, here, in Boost , or if you prefer, in a private message. If not, sorry, and forget it. If I can help you about something, say me and I will try. And, as I say before, it looks very interesting Sincerely yours Francisco Tapia