The iterators don't store the position, because after the creation of an iterator, if you insert or delete elements in the tree, the position of the element pointed bu the iterator can change. The iterators need to travel to the root of the tree for to know their position, with the exception of the iterators end(), and rend(). Normally relate the iterators of vectors with random access iterators O(1), and iterators of a list or set with not random access iterators O(N). These iterators are in the middle O (log N). I don't know other iterators similar. I say random access iterator because you can use the random access algorithms of the STL library as std::sort, std::binary_search wit good results. Obviously they are not so fast as the iterators of a vector, but run well and fast. The std::sort over a counter_tree<int> with 1000000 random elements, spend 2.3 seconds on my computer. If I don't define the iterator as random access I can't use these functions. I examined much information about the iterators, beginning with your Boost library iterators and many other documents and I have not a solution. Perhaps you can help me in order to find a solution which permit to access to the STL library functions without the definition as random access. Sincerely yours Francisco Tapia