On Fri, Oct 5, 2012 at 2:20 AM, Francisco José Tapia <fjtapia@gmail.com>wrote:
The countertree 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 countertree iterators need to travel to the root of the tree for to know their position, with the exception of the iterators end(), and rend().
I understand that the random access iterators permit you access directly to the element, without a sequential access. Commonly they are associated with the vectors with iterators O(1), and the iterators of a list or set with are sequential and not random access iterators O(N). The iterators of the vector_tree are in the middle O (log N), but permit you access to the elements directly without sequential access. I don't know other iterators similar.
The dynamically allocated augmented B+ trees support the functionality of both random access and bidirectional iterators. The computational complexity of operators of these iterators is better than in proposed augmented red black trees. However, I dropped the support of this functionality in array based augmented B+ trees. In addition to this, Boost.Container offers containers, such as stable_vector, with random access iterators that are not invalidated by insert/erase operations. This is possible, since these containers have features of both array based and dynamically allocated data structures. IMO, these iterators are superior to iterators in augmented dynamically allocated data structures.
Regards, Vadim Stadnik