[boost] [countertree] New Version

Subject: [boost] [countertree] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2011-05-01 17:08:36

Hi

this message is to announce the new version of the countertree library. You
can find the zip file with the code and the documentation in  <
http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename=countertree.zip&directory=Containers&>
or  if you want a quick look , you can see in my web page <
http://fjtapia.webs.com/works/countertree/index.html>

Technically this library is an implementation of a binary red-black counter
tree. Colloquially is a balanced tree with 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.

If the information stored is unordered, we have the class boost::vectortree.
This class have the same interface than a std::vector. The std::vector is
very fast O(k) inserting and deleting at end , but very slow O(N) if you
must do in other positions . In the vectortree all the operations are
O(logN). It is a bite slower than std:vector inserting and deleting at end,
but much more faster for to insert and delete in any other position.

If the information stored is ordered, you have the classes boost::set,
boost::multiset boost::map and boost::multimap. These classes have identical
interfaz than the std::set , std::multiset, std::map and std::multimap, and
additionally, access by position with the function at(pos). The iterators
are random access and have a function pos() which return their position in
the container. You can mix safely access by iterators and access by
position. The performance of these classes are similar to the classes of the
STL.

#include <boost/countertree/set.hpp>
#include <iostream>

int main ( void )
{ //------------------------ begin --------------------
  boost::set<int> A ;
  for ( int i = 0 ; i< 100 ; ++i) A.insert(i);
  for ( int i = 0 ; i < A.size() ; ++i) std::cout<<A.at(i);
  return 0 ;
};

For to show the utility of this, imagine a large unordered file with the
information about the employees of a big company. You have indexes
implemented with multimaps, with pairs [value, position], and use the
upper_bound and lower_bound functions . You need to select the employees in
a range of age and weight. With the boost:multimap you can know the number
of elements of the selection.

In the weight query we found 100 elements and in the age query 10000
elements. To travel the elements of the weight query asking for the age, is
faster than the opposite.

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 (32 and 64) and Visual Studio 2008 (32) and
Visual Studio 1010 (32 and 64). Please, if you find any problem, please mail
me ( <fjtapia_at_[hidden]>) 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.

Francisco Tapia

<fjtapia_at_[hidden]>