std::map with efficient nth element access

If you used a modified Trie where non-terminal nodes kept track of how many terminal nodes were below it, you could do quick ordered lookup.

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.

I've never used boost::multi_index_container<>, but it sounds like it might have the capability to do what you want (though I'm not really sure - it's a pretty complex library at first glance).

It has a random access key type, but I'm not sure how you'd update the random index in a way that keeps inserted element's index synchronized with the other index's ordering. Also, note the following from the tutorial on using a random index:

This added flexibility comes at a price: insertions and deletions at positions other than the end of the index have linear complexity, whereas these operations are constant time for sequenced indices. This situation is reminiscent of the differences in complexity behavior between std::list and std::vector: in the case of random access indices, however, insertions and deletions never incur any element copying, so the actual performance of these operations can be acceptable, despite the theoretical disadvantage with respect to sequenced indices.

It's unclear to me whether that would be a deal killer for you or not, even if you can manage to synchronize the random index for inserted elements the way you'd like.