> std::map will often have better cache coherence

std::map is a red-black tree. It will have among the worst cache coherence of anything. Do you have any supporting benchmarks?

And if you have a small enough data set then std::vector will run circles around any map anyway.

> Also not sure what you mean when you say operator new never overflows. Can you elaborate?

    size_t mySize = ...;
    int* myptr = (int*) malloc(mySize * sizeof(int));
    int* myptr2 = new int[mySize];

What happens when mySize is >= 1073741824 on a 32-bit system?

Hint: the malloc version has a security bug, the new one doesn't.

If mySize is computed at runtime, that computation should most likely be checking for overflow. If it is a constant, declare it constexpr and get a compile-time warning for the overflow.

In any case, it's the multiplication that has a bug, not malloc (though I agree that the usage you mention is unfortunately common).

Yes it's the multiplication that has the bug, but malloc makes that error common as you said. An API whose usage commonly has trivial security bugs is not a good API. new just wholesale avoids that common category of bugs, so why would you avoid it in favor of malloc? They do the same thing, one just does it safer.

Boost, loki, and I'm sure others have a "flat" map which is just an array backed ordered map. Slower insertions than the red-black map but because of the cache locality it's much faster overall.