Re: [boost] [Countertree + Suballocator] New Version

Subject: Re: [boost] [Countertree + Suballocator] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-04-12 13:29:36

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