Bernhard Reiter wrote:
Am Samstag, den 29.07.2006, 18:54 +0100 schrieb Stephen Dolan: [...]
A map<int, foo> is not a linear list because if I insert another element into the map, the existing elements aren't "pushed right". I can, using std::map, insert an element in log time, but to find the n-th element takes linear time. It is possible to implement a data structure supporting both the operations "insert in position n" and "find element in position n" in log time, I was wondering if there was any interest for it.
I guess "rank tree"'s just a fine name -- I'm aware of an implementation by René, http://redshift-software.com/~grafik/RankTree.h -- and it being a kind of tree, I intend to offer such a thing as part of my SoC tree project... (https://boost-consulting.com:8443/trac/soc/wiki/tree)
For those who care about names and such... The description I based it on is from the "Introduction to Algorithms" textbook. In it they refer to the category of trees that keep additional data "order-statistic tree" and the extra order info as the "rank". Not something that rolls of the tongue :-) The big change from their description is that instead of implementing it as a red-black tree with the extra rank data. I removed the color component of the node as it can be inferred from the rank information. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo