Comment by bluGill
3 hours ago
While this advice isn't wrong, it is misleading. In my benchmarks std::map beats vector after 9 elements. Less than that and linear search is better but branch prediction and cache loading is very good.
Run your own benchmarks on your own data of course. Also map is not considered the best key value store.
Because in your benchmark all std::map nodes were allocated in succession, most likely being placed in adjacent memory locations...
This likely won't be true in a real application with a non-trivial allocation pattern.
That might or might not be true in the real world. Often in my applications I'm creating at startup and then referencing later.
Still a custom map that allocated a bunch of nodes would be a useful optimization.
Actually it really depends, because allocators can also be kind of smart (and you don't have to use the default allocator).
And then, on the other hand - I really doubt GP's map beats a vector, with all of those pointers bins and stuff, in a non-contrived benchmark with 10 elements.
Finally - it's not either-or: There are better hash maps whose memory is sequentially allocated and/or are otherwise cache-aware. And there are data structures geared towards parallel execution on multiple threads; and towards SIMD; etc. etc.