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