I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that

I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that if you think you need sorted keys, double-check. I program an awful lot of things without sorted keys, and I am quite aware of the issues around sorting, and I suspect without proof that a lot of people swearing by sorted maps are imposing false ordering requirements on their code more often than they realize. The ideal solution is not need order at all. (I am especially suspicious of extensive use of maps where the keys are sorted by insertion order. That smells... antipatternish to me.)