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 reply to Re: Perl and C++/STL by athomason
in thread Perl and C++/STL by rg0now

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.