Nah. It's all about understanding cache memory. For some reason, std::map is implemented using linked lists (it's actually a binary tree but the thing's that each node is allocated separatelly). That means that every jump from a node to another, both when searching and when iterating has a very high chance of being a cache miss. If we take into account that a querying data from the RAM takes more or less 100 times more than from the cache, the std::map wastes a huge amount of time just waiting for data. My implementation just makes a better use of cache memory, by making all the sorting and searching algorithms happen in a chunk of contiguous memory. You can take a look at the code here if you're interested: https://bitbucket.org/Lugruf/cache_friendly_map
Dragon?