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.