Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk