title: Fast C++ container like the C# HashSet<T> and Dictionary<K,V>?
body: <p>I've used HashSet and Dictionary a lot in C#, and found them very fast... </p>
  
  <p>I've tried using std::map and std::hash_map and am finding them very slow in comparision.  Does this sound like expected behaviour? Is there something I might be doing wrong in my use of std::hash_map?</p>
  
  <p>Or, is there a better C++ Hash container out there?</p>
  
  <p>I'm hashing int32s, usually around 100,000 of them.</p>
  
  <p>Update: I created a repro in C# and C++.  It runs two trials, they take 19ms and 13ms in C#, and about 11,000ms in C++.  There must be something really wrong with my C++ code :)</p>
  
  <p>(Both were run as Release builds, both are Console apps)</p>
  
  <p>C# Output:</p>
  
  <pre><code>Found 511 values in the intersection, in 19 ms
  Found 508 values in the intersection, in 13 ms
  </code></pre>
  
  <p>C++ Output:</p>
  
  <pre><code>Found 308 values in the intersection, in 11764.7ms
  Found 316 values in the intersection, in 11742.8ms
  </code></pre>
  
  <p>C++ Output (using stdext::hash_map instead of std::map)</p>
  
  <pre><code>Found 300 values in the intersection, in 383.552ms
  Found 306 values in the intersection, in 2277.02ms
  </code></pre>
  
  <p>C++ Output (using stdext::hash_map, a release x64 build)</p>
  
  <pre><code>Found 292 values in the intersection, in 1037.67ms
  Found 302 values in the intersection, in 3663.71ms
  </code></pre>
  
  <p>Notes:</p>
  
  <ul>
  <li>Set2 is not getting populated quite as I wanted in C++, I was expecting it to have a 50% intersection with Set1 (as it does in C#), but I had to multiply my random number by 10 for some reason to even get them to partially not intersect</li>
  </ul>
  
  <p>C#:</p>
  
  <pre><code>    static void Main(string[] args)
      {
          int start = DateTime.Now.Millisecond;
          int intersectionSize = runIntersectionTest();
          int duration = DateTime.Now.Millisecond - start;
  
          Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration));
  
          start = DateTime.Now.Millisecond;
          intersectionSize = runIntersectionTest();
          duration = DateTime.Now.Millisecond - start;
  
          Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration));
  
          Console.ReadKey();
      }
  
      static int runIntersectionTest()
      {
          Random random = new Random(DateTime.Now.Millisecond);
  
          Dictionary&lt;int,int&gt; theMap = new Dictionary&lt;int,int&gt;();
  
          List&lt;int&gt; set1 = new List&lt;int&gt;();
          List&lt;int&gt; set2 = new List&lt;int&gt;();
  
          // Create 100,000 values for set1
          for ( int i = 0; i &lt; 100000; i++ )
          {
              int value = 1000000000 + i;
              set1.Add(value);
          }
  
          // Create 1,000 values for set2
          for ( int i = 0; i &lt; 1000; i++ )
          {
              int value = 1000000000 + (random.Next() % 200000 + 1);
              set2.Add(value);
          }
  
          // Now intersect the two sets by populating the map
          foreach( int value in set1 )
          {
              theMap[value] = 1;
          }
  
          int intersectionSize = 0;
  
          foreach ( int value in set2 )
          {
              int count;
              if ( theMap.TryGetValue(value, out count ) )
              {
                  intersectionSize++;
                  theMap[value] = 2;
              }
          }
  
          return intersectionSize;
      }
  </code></pre>
  
  <p>C++:</p>
  
  <pre><code>int runIntersectionTest()
  {
      std::map&lt;int,int&gt; theMap;
  
      vector&lt;int&gt; set1;
      vector&lt;int&gt; set2;
  
      // Create 100,000 values for set1
      for ( int i = 0; i &lt; 100000; i++ )
      {
          int value = 1000000000 + i;
          set1.push_back(value);
      }
  
      // Create 1,000 values for set2
      for ( int i = 0; i &lt; 1000; i++ )
      {
          int random = rand() % 200000 + 1;
          random *= 10;
  
          int value = 1000000000 + random;
          set2.push_back(value);
      }
  
      // Now intersect the two sets by populating the map
      for ( vector&lt;int&gt;::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
      {
          int value = *iterator;
  
          theMap[value] = 1;
      }
  
      int intersectionSize = 0;
  
      for ( vector&lt;int&gt;::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
      {
          int value = *iterator;
  
          map&lt;int,int&gt;::iterator foundValue = theMap.find(value);
  
          if ( foundValue != theMap.end() )
          {
              theMap[value] = 2;
  
              intersectionSize++;
          }
      }
  
      return intersectionSize;
  
  }
  
  int _tmain(int argc, _TCHAR* argv[])
  {
      srand ( time(NULL) );
  
      Timer timer;
      int intersectionSize = runIntersectionTest();
      timer.Stop();
  
      cout &lt;&lt; "Found " &lt;&lt; intersectionSize &lt;&lt; " values in the intersection, in " &lt;&lt; timer.GetMilliseconds() &lt;&lt; "ms" &lt;&lt; endl;
  
      timer.Reset();
      intersectionSize = runIntersectionTest();
      timer.Stop();
  
      cout &lt;&lt; "Found " &lt;&lt; intersectionSize &lt;&lt; " values in the intersection, in " &lt;&lt; timer.GetMilliseconds() &lt;&lt; "ms" &lt;&lt; endl;
  
      getchar();
  
      return 0;
  }
  </code></pre>