Re: [boost] [countertree] New Version

Subject: Re: [boost] [countertree] New Version
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2011-05-02 11:33:57

On 5/1/2011 4:08 PM, Francisco José Tapia wrote:
> or  if you want a quick look , you can see in my web page<
> http://fjtapia.webs.com/works/countertree/index.html>

Please adjust your docs to make it *very* clear this is not an official, 
or accepted, Boost C++ Library.

Preliminaries...

Have you looked at the past rank tree and general tree conversations in 
the Boost dev list? Specifically the TR paper and partial implementation 
on this subject that was created as a GSoC project?

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

Have you considered that it's possible to do away with the red-black 
information as the rank/count information is enough to create the 
balanced tree?

> If the information stored is unordered, we have the class boost::vectortree.

You really should have some sub-namespace in that. I.e. 
"boost::countertree::vectortree" or such. It is frowned upon to insert 
things into the main boost namespace.

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

Are there other differences than performance to the standard containers? 
I.e. why would I use vectortree instead of some other container? For 
example, why use a vectortree<std::string> vs. a 
hashmap<size_t,std::string>?

NOTE: Yes, I'm asking very loaded question.. So assume I know a lot 
about the particulars of this subject ;-)

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org (msn) - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail