in reply to Perl and C++/STL

`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.

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.

**Update:**

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[3];`), 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.

In Section
Meditations