Hi this message is to announce the new version of the [countertree + suballocator] library. You can find in (http://dl.dropbox.com/u/8437476/works/countertree/index.html)<http://dl.dropbox.com/u/8437476/works/countertree/index.html> When I was writing the document explaining the allocator's algorithm. I reexamined my code , and It run well and have an easy interface , but the internal design was obscure and difficult to understand. Due this, I decided redesign it in order to make it clear and easy to understand. I changed too the version of the GCC compiler form the 4.6 to 4.7, and the machine used for the benchmarks. My old computer, where I developed the code, had a good cache but a bad bus memory (Single channel 533Mz), and this introduce a distortion in the comparison of some algorithms. The new machine is a QuadCore with 8M of cache and 8G dual channel 1066 MHz. The results obtained are more similar to the obtained in a modern machine. I added a new point to the documentation explaining the additional features of the countertree set, multiset, map and multimap with two examples. You can find in ( http://dl.dropbox.com/u/8437476/works/countertree/ordered.html#functionality) For the people who don't know this project, this is a description : *COUNTERTREE* This library is an implementation of a binary red-black counter tree. This tree have an additional counter in each leaf. This permit the access to the elements by the position, like in a vector. It is a random access container with random access iterators . With this tree we have vectors (cntree::vector_tree) with identical interface than std::vector. The vector_tree have the same speed inserting and deleting in any position (all the operations are O(log N)).It is slower than std:vector inserting and deleting at end, but much faster for to insert and delete in any other position. With ordered information, we have in the cntree namespace the classes set, multiset, map and multimap, with identical interface than the STL classes, with the plus of access to the elements by position, like in a vector. The iterators are random access , and you can subtract two iterators in a O(log N) time for to know the number of nodes between them (even with the end( ) and rend( ) iterators) *SUBALLOCATOR* The allocator is the data structure defined in the STL, as interface between the data structures and the memory provided by the Operating System (O.S.). The allocator manages the memory received from the Operating System, and the memory requested in the allocate operations and the memory returned in the deallocate operations. To write an allocator for to manage a wide range of size elements and a big number of elements (several millions) of each size in a fast way, it's a very difficult task. When the number of elements grows, many allocators begin to have speed problems. For to improve the speed allocating of the small size elements, many allocators request to the Operating System big chucks of memory. With this, the allocator don't need request memory to the operating system for each allocation. But many allocators don't return well the unused chucks of memory to the Operating System and the memory used by the allocator is the maximum used, never decrease . These allocators are named pool allocators. If you have a small number of elements, you have a small problem, small resources and small time operations. But, if you have several millions of elements allocated, perhaps you are using several GB of memory. Running a program with GB of memory don't used, because the allocator don't return the memory request, is a great waste of resources. This problem is specially important in two environments : - When you have a limited resources, as occurs in the mobile phones, pads , tablets... - When the programs must run continuously in a multitask environment If you use an allocator for the allocation of variable size elements, and a pool allocator for the allocation of fixed size elements, this improve the speed, but increase the memory consumption, which is the sum of the maximum memory of the pool allocator and the memory used by the allocator. If the pool allocator don't return to the Operating System the unused memory, this can't be reused by the allocator. The *suballocator is a solution to these problems*, and others memory problems described in the suballocator page. The suballocator is a layer between the allocator and the data structures, compatible with any allocator with the STL definition. The suballocator request memory to the allocator, and return to it when unused. With the suballocator a) *We have a very fast allocation* *(around 2 times faster than the std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See details in the *Suballocator Benchmark<http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html#benchmark> *)* b) *Return memory to the allocator, for to be used by others types of data*. Many allocators, return this memory to the Operating System, and decrease the memory used by the program, *( as you can see in the *Suballocator Benchmark <http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html#benchmark> *)* c) *You can use with any allocator if it is according with the STL definition*. The suballocator provides speed and memory management to any allocator d) Even the time of the allocation is a small part of the time spent in the insertion in a std::set, the suballocator obtain time reductions over over the 30% respect the std::allocator. The secret is the cache performance due to the data locality improvement. *COUNTERTREE + SUBALLOCATOR* The join of the two ideas provide us data structures with a suballocator built-in. They are, in the namespace cntree, the vector_tree_pool, set_pool, multiset_pool,map_pool and multimap_pool, with identical interface than the STL classes but better performance. Tray it. It fast, useful and easy to understand and use,. They are the STL classes with a few additional functions. I had checked this code with GCC 4.7 (32 and 64) , CLANG/LLVM 3.0 and Visual Studio 1010 (32 and 64). If you find any error or problem in the code , the documentation or in any other part ( as friendly do Mr Rene Rivera in the first version). Please mail me ( fjtapia@gmail.com) or if you mail Boost, please insert [countertree] in the head of the message. Some days I have not time to read all messages arrived to my mail, but if I see that I detect and respond first. If you have some idea, or have any comment, please mail me, always two legs run more than only one in the pursuit of the goal, to be useful to the community of programmers in the same way than our predecessors had been useful to us. Sincerely yours Francisco Tapia fjtapia@gmail.com