Путь не является допустимым виртуальным трактом

map - красно-черное дерево, O(log(n)) время доступа. hash_map (что не является стандартным, однако unordered_map станет стандартным) использует (концептуально) хэш ключа в качестве индекса в массиве связанных списков, и, следовательно, имеет наилучшее время доступа O(1) наихудший случай O(n).

См. http://en.wikipedia.org/wiki/Red-black_tree

.