> 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.