RE: [boost] Is there any interest in this container?

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.