title: Time efficiency on std::tr1::unordered_map::operator[]
body: <p>I am optimizing a piece of code in Visual Studio 2008 SP1. Knowing that <code>unorder_map</code> is awesome with constant time insert/delete/find, so I optimized the code by using <code>unordered_map</code> as my primary data structure. Please take a look at the following code.</p>
  
  <pre><code>....
      typedef std::tr1::unordered_map &lt;__int64, int&gt; umap_id;
      const int text1_length = text1.GetLength();
      const int text2_length = text2.GetLength();
      const int max_d = text1_length + text2_length - 1;
      const bool doubleEnd = (64 &lt; max_d);
      vector&lt;set&lt;pair&lt;int, int&gt; &gt; &gt; v_map1;
      vector&lt;set&lt;pair&lt;int, int&gt; &gt; &gt; v_map2;
      vector&lt;int&gt; v1(2 *max_d, 0);
      vector&lt;int&gt; v2(2 *max_d, 0);
  
      int x, y;
      __int64 footstep;
      umap_id footsteps(max_d * 2);
      bool done = false;
      const bool forward = ((text1_length + text2_length) % 2 == 1);
  
      for (int d = 0; d &lt; max_d; ++d)
      {
          // Walk forward path one step
          v_map1.push_back(set&lt;pair&lt;int, int&gt; &gt;());
          for (int k = -d; k &lt;= d; k += 2)
          {
              if (k == -d || (k != d &amp;&amp; v1[k - 1 + max_d] &lt; v1[k + 1 + max_d]))
                  x = v1[k + 1 + max_d];
              else
                  x = v1[k - 1 + max_d] + 1;
              y = x - k;
  
              if (doubleEnd)
              {
                  footstep = (__int64) ((__int64)x &lt;&lt; 32 | y);
                  if (!forward)
                      footsteps[footstep] = d;
                  else if (footsteps.find(footstep) != footsteps.end())
                      done = true;
              }
              ....
          }
      }
  ....
  </code></pre>
  
  <p>But turns out it is still quite slow. Given my relatively small input (<code>max_d</code>=946), it runs for more than 20 seconds. </p>
  
  <p>I did a profiler analysis on the <strong>release</strong> build, and the profiler reveals that line: <code>footsteps[footstep] = d;</code> is the major culprit which was run 447931 times and took about 20 seconds. </p>
  
  <p>Note, there is another line of code in the same loop body: <code>else if (footsteps.find(footstep) != footsteps.end())</code> which executed the same number of times (i.e. 447931 times) but costed much fewer seconds.</p>
  
  <p>The <code>operator::[]</code> of <code>unordered_map</code> seems a black-box for me. I couldn't figure out why it takes so long. It's a <strong>32-bit</strong> application. Any help is appreciated.</p>