From: Peter Palotas (peter_at_[hidden])
Date: 2004-03-17 05:06:14
Jeremy Maitin-Shepard wrote:
> This seems like a useful data structure, although I can't
> think of any specific use cases.
> 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.)
Yes, that is correct. I'm implementing it as a red-black tree keeping track
of the number of nodes rooted at each node just as you described. I'm also
thinking about managing a linked list of the elements in the container to
allow for constant time iteration through the list. This would add a small
O(1) overhead to insertions and deletions, but on the other hand it would
probably speed up deletions a little bit as well so it might be a good idea.
The use I wanted this structure for is the same as Rene wrote about; for
keeping track of eg. a GUI list that can have items inserted/removed in it.
Not sure if there are other usages as well nor if this is a general enough
usage to include in a library such as boost, but I know I've wanted this
container for this purpose on a number of occasions.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk