Boost logo

Boost :

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2004-03-17 00:24:49

Jeremy Maitin-Shepard wrote:
> This seems like a useful data structure, although I can't think of any
> specific use cases.

I use such a data structure right... keeping track of a GUI list that can have
items inserted/removed in it. A regular number->item map doesn't work as it
has to change the index of items on inserts/deletes.

> I am assuming you are implementing it as a balanced binary tree where
> you keep track of the number of nodes in the subtree rooted at each
> node. (This allows finding a node by its numeric index in time.)

That is how I implemented it. The data structure is called a "rank tree",
describe in the white book. I've mentioned the structure in this list before :-)

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

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