note
athomason
<code>std::map</code> 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 <code>n</code> 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 [http://www.sgi.com/tech/stl/hash_map.html|a non-standard hash_map template]; that would be a more appropriate comparison.
<p>
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.
<p>
<strong>Update:</strong>
<p>
As for your pre-allocation concerns with <code>std::vector</code>, there's good news. You will indeed get segfaults using the square-bracket notation for entries that don't exist (<code>vector<int> a(1); cout << a[3];</code>), but the <code>.at()</code> 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 <code>.resize()</code> method does just that for whatever size you need.
438468
438468