std::map with efficient nth element access

Question

I've got a set of data that I need to store in an ordered map (i.e. with efficient insertion, deletion, and locating items by key), but I also need to be able to find the nth element without walking through the entire map (there may sometimes be tens of thousands of items in it).

I know of one way to do it: use a red/black tree, but keep the total number of child items on one of the legs of each node as well. It makes insertion and deletion a little slower (because you have to update the counts on each node along the path as you do), but you can find the nth element for any n in roughly the same time as finding a key.

I'm wondering if there's an existing C++ implementation of such a thing that I can use. I can write it myself if not, but I'd really rather not.

---

EDIT: I got some clarification on the use-case for it. I misunderstood it slightly: after looking up an item by key, they need the ability to efficiently find out what index the found item is, to properly display the scroll bars.

It is a legitimate need, and the data structure I described above will still work for it, so I'm still looking for an answer. But as it seems that no one has come up with one yet, I'm going to start coding it myself.

Answer 1

This is my answer of other question considering similar issue.

associative / random access container

I guess this might also apply to your question.

---

I have been looking for such a data structure for a long time.

Recently, I found quite promising library which has all the functionality that you are looking for.

See the cntree::set with random access in O(log n).

here is the link. http://dl.dropbox.com/u/8437476/works/countertree/index.html

Although it seems to be under development, I see it is quite usable.