C++ ordered map optimized with index access

Question

In short, my question is, how to maximize the performance of ordered map (e.g. implemented as std::map) with good support of index access?

Details:

We can of course use some code like std::advance(it, index) to achieve index access where it is an iterator of std::map. However, the performance becomes a severe issue when std::map is large, so traversing the std::map is very slow.

I hope the container map can support these:

• Basic Operations. Just behave like a normal std::map. For example, insertion, deletion, access values by keys. Complexity lower than O(N) is expected.
• Orderliness. We can access the i-th smallest (by keys) item by index access. Indices are not totally random, they are a bit similar (so my first thought is to use something like cache, but I have no idea). We may alter the map by insertion or deletion, so saving previously accessed iterators may not be fully feasible because they may point to wrong positions after modification to map.

What is the proper data structure or implementation to achieve this goal? Thank you!

Goal:

A good implementation of ordered map with good support of index access (perhaps with caching)? It is okay not to be fully stored in a sorted order for all items.