title: std::vector faster than plain array?
body: <p>I have just tried to benchmark <code>std::sort</code> on both <code>std::vector&lt;std::pair&lt;float, unsigned int&gt;&gt;</code> (filled with push_back operation) and plain <code>std::pair&lt;float, unsigned int&gt;&gt; *</code> array (allocated using new and then filled one by one). The compare function just compared the float parts of the pairs.</p>
  
  <p>Surprisingly, when used on 16M values, on std::vector it took only about 1940 ms but on the array it was about 2190 ms. Can anybody explain how can be the vector faster? Is it due to cacheing, or is just array version of std::sort poorly implemented?</p>
  
  <p><code>gcc (GCC) 4.4.5 20110214 (Red Hat 4.4.5-6)</code></p>
  
  <p><code>Intel(R) Core(TM) i7 CPU 870  @ 2.93GHz - cache size 8192 KB</code> (the computer has two quad-core CPUs but I assume the sort is only single-threaded)</p>
  
  <p><strong>EDIT:</strong> Now you can call me dumbass, but when I tried to reproduce the code I used for the measurements (I have already deleted the original one) I cannot reproduce the results - now the array version takes about 1915 +- 5ms (measured on 32 runs). I can only swear I have run the test on 10 measurements three times (manually) with similar results, but this is not a rigorous proof.</p>
  
  <p>There was probably some bug in the original code, background process seems unprobable because I have alternated measurements of vector and array versions and the vector results hold and no user was logged in.</p>
  
  <p>Please, consider this question as <strong>closed</strong>. Thanks for your efforts.</p>