title: C++ map<std::string> vs map<char *> performance (I know, "again?")
body: <p>I was using a map with a <code>std::string</code> key and while everything was working fine I wasn't getting the performance I expected.  I searched for places to optimize and improved things only a little and that's when a colleague said, "that string key is going to be slow."</p>
  
  <p>I read dozens of questions and they consistently say:</p>
  
  <blockquote>
    <p>"don't use a <code>char *</code> as a key" <br>
    "<code>std::string</code> keys are never your bottleneck"<br>
    "the performance difference between a <code>char *</code> and a
    <code>std::string</code> is a myth."</p>
  </blockquote>
  
  <p>I reluctantly tried a <code>char *</code> key and there was a difference, a big difference.   </p>
  
  <p>I boiled the problem down to a simple example:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;map&gt;
  
  #ifdef USE_STRING
  
  #include &lt;string&gt;
  typedef std::map&lt;std::string, int&gt; Map;
  
  #else
  
  #include &lt;string.h&gt;
  struct char_cmp { 
      bool operator () (const char *a,const char *b) const 
      {
          return strcmp(a,b)&lt;0;
      } 
  };
  typedef std::map&lt;const char *, int, char_cmp&gt; Map;
  
  #endif
  
  Map m;
  
  bool test(const char *s)
  {
      Map::iterator it = m.find(s);
      return it != m.end();
  }
  
  int main(int argc, char *argv[])
  {
      m.insert( Map::value_type("hello", 42) );
  
      const int lcount = atoi(argv[1]);
      for (int i=0 ; i&lt;lcount ; i++) test("hello");
  }
  </code></pre>
  
  <p>First the std::string version:</p>
  
  <pre><code>$ g++ -O3 -o test test.cpp -DUSE_STRING
  $ time ./test 20000000
  real    0m1.893s
  </code></pre>
  
  <p>Next the 'char *' version:</p>
  
  <pre><code>g++ -O3 -o test test.cpp             
  $ time ./test 20000000
  real    0m0.465s
  </code></pre>
  
  <p>That's a pretty big performance difference and about the same difference I see in my larger program.</p>
  
  <p>Using a <code>char *</code> key is a pain to handle freeing the key and just doesn't feel right. C++ experts what am I missing?  Any thoughts or suggestions?</p>