title: std::map with efficient nth element access
body: <p>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 <em>nth</em> element without walking through the entire map (there may sometimes be tens of thousands of items in it).</p>
  
  <p>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 <em>nth</em> element for any <em>n</em> in roughly the same time as finding a key.</p>
  
  <p>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.</p>
  
  <hr>
  
  <p>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.</p>
  
  <p>It <em>is</em> 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.</p>