Boost logo

Boost :

Subject: Re: [boost] [countertree] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2011-05-15 05:35:48


this message is to announce the new version of the countertree library.
According with the sugest of Rene Rivera ( Thanks), I had changed the
namespaceof the library. Now all is in the namespace cntree. And in the
documentation I have a big title with the text preliminary in the head of
all the pages. If something is not OK , please mail me , and I will change
as soon as possible.

You can find the zip file with the code and the documentation in <>
or if you want a quick look , you can see in my web page <>

The counter trees are trees where each node have an additional counter. This
counter represent the number of nodes under it, including itself. This
permit to access to the elements of the tree by their position, like a
vector. You can mix safely access by iterators and access by position.

This Library provide us :

1.- Vectors with the same speed inserting and deleting in the extreme
positions than in the central positions. They are a bit slower than the STL
vector inserting and deleting in the extreme positions, but much more faster
inserting and deleting in the central positions.

2.- Set, multiset, map, multimap fully compatible with the STL set,
multiset, map and multimap, with similar speed.The iterators are, like in a
vector, random access (you can add or subtract any integer value to an
iterator). You have too access to the elements by position like in a vector,
with the function at (position) as you can see in the next example code

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

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

The iterators and the data structures are fully compatible with the STL
functions and algorithms.

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 quickly.

Francisco Tapia


Boost list run by bdawes at, gregod at, cpdaniel at, john at