I am a teacher of programming in a Technical Professional Training School in Madrid ( Spain). I had wrote a counter balanced red-black tree in C++. The balanced trees have a counter in each node, which represent the number of nodes under it including itself. This counter permit to access to the nodes by their position in the tree. Due to this you can use a counter tree as a vector, access by position and insert and delete by position. Of course, the iterators of this trees have random access, an you can add or decrement the iterators any value . vector_tree<int>::iterator Alfa, Beta ; Alfa = Beta + 17 ; The algorithms are built from zero,without any book or article, because you need in each operation , not only modify the pointers, you must modify the counters too. The speed is good. In the worst case the delay respect to the equivalent STL functions is around 20%. I had checked in windows ( Visual Studio ) and Linux (GCC). My version have a 5 classes interface : vector_tree : This class is a counter balanced red-black tree and have the same interface than the STL class vector. The insertion , deletion and access to elements are log(N) operations. The other four classes are set , multiset , map and multimap. Internally they have a vector_tree. They have the same interface than the STL classes, plus the access by position and the random access iterators. My idea is to send you to examine , and if you think useful, make a new boost library. Today is finished to 95% . I hope have all finished by the first weeks of September. I am writing you because today, looking for other think I discovered a US patent “Positional access using a B-tree” ( US patent Number 7,120,637B2 Oct, 10, 2006), and I don't know if this patent prevent the publication of the code in your library, because you can consider the red-black trees an simplification of B-trees If prevent, and you don't have an idea about the utility of the code, I will stop the develop, and I will spend my time with new ideas The idea about the counter trees you can find in “The art of computer Programming “ Donald Knuth, and I have a previous version of this code wrote 10 years ago and presented in my exposition in the Oposiciones a Catedrático de Informática ( Madrid 2001) If you are interested in the code, mail me and I will send you. Francisco José Tapia E-Mail : fjtapia@gmail.com