Boost logo

Boost :

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-07-29 15:38:08

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é, -- and it being
> a kind of tree, I intend to offer such a thing as part of my SoC tree
> project... (

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

-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. -
-- rrivera/ - grafik/
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

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