Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-10-04 12:20:21

  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.

Independently of the classification, 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, more or less like to insert the elements in a STL set

 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
the Boost library iterators and many other documents and I have not a
solution. Perhaps someone can help me in order to find a solution which
permit to access to the STL library functions without the definition as
random access.

 The main utility of the vector_tree is when you must insert or delete many
elements in central positions. It is not worst or best than others data
structures, it is different. It is only an option more, with different
features than other data structures. If you consider it useful, use .Only
that

 The suballocator concept have two big parts. First, from where and how
obtain the memory the allocator. Second How dispatch the memory to the data
structure. The suballocator is the second part with a big number of fixed
size elements data structures ( STL list, set , multiset, map and multimap)

About the suballocator. It is a simple layer over the allocator. It have
the same interface. The data structure received a suballocator as template
parameter. But the suballocator use internally an allocator. It request a
big chuck of memory to the allocator , and manage in a fast and easy way.
When a chuck of memory is unused by the data structure, is returned to the
allocator. Usually, that big chucks of memory are returned to the Operating
System from the allocator , and this reduce the memory consumption of the
program. You can see this , running the benchmark_allocator.cpp.

 The suballocator run over ANY allocator with the STL allocator interface.
It don't take care about the kind of allocator or the origin of the memory.

If you want to know more about the algorithm of the suballocator, in the
documentation , in the point 5.2 you have a document with a description of
the data structure and algorithms.

 About the C++11 stateful allocators, I need a bite of time for to study in
deep , and provide you something more than a trivial opinion Sorry!

  For Luc . Don't worry about your English. I am sure than sometimes I
destroy the English dictionary, but the Boost people are well-mannered and
don't say me nothing. And about myself, you can ask me, if I know, I will
respond you, and if I don't know, we will share our ignorance, which is the
main reason for to study more.

Sincerely yours

Francisco Tapia