std::map is required by the ANSI C++ standard to be implemented as a red-black tree, which has logarithmic lookup time. Hash tables have roughly constant lookup time, so it's not surprising that for largish n the hash will outperform the tree. Unfortunately, the STL in the current standard doesn't provide for a hash-based associative container type, so you can't really compare apples to apples here. The SGI STL implementation does contain a non-standard hash_map template; that would be a more appropriate comparison.
in reply to Perl and C++/STL
The moral of the story is that once your problem becomes large enough, asymptotic algorithm performance dominates the constant factors separating a "slow" language from a "fast" one.
As for your pre-allocation concerns with std::vector, there's good news. You will indeed get segfaults using the square-bracket notation for entries that don't exist (vector<int> a(1); cout << a;), but the .at() accessor performs the equivalent function after doing a bounds check (it throws an exception if you violate the bounds instead of segfaulting). And if you find yourself needing to increase the size of the vector, the .resize() method does just that for whatever size you need.