title: C++: Performance of std::vector vs std::list
body: <p>I have the following code to profile std::vector performance vs std::list for various N.</p>
  
  <pre><code>void vectorPerf(size_t n)
  {
     std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
     std::vector&lt;size_t&gt; cache;
     for (size_t i = 0; i &lt; n; i++) {
        cache.push_back(i);
     }
     std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
  
     auto duration = std::chrono::duration_cast&lt;std::chrono::microseconds&gt;(t2-t1).count();
  
     std::cout &lt;&lt; duration &lt;&lt; " us." &lt;&lt; "\n";
  
     return;
  }
  
  void listPerf(size_t n)
  {
     std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
     std::list&lt;size_t&gt; cache;
     for (size_t i = 0; i &lt; n; i++) {
        cache.push_back(i);
     }
     std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
  
     auto duration = std::chrono::duration_cast&lt;std::chrono::microseconds&gt;(t2-t1).count();
  
     std::cout &lt;&lt; duration &lt;&lt; " us." &lt;&lt; "\n";
  
     return;
  }
  
  int main(int argc, char** argv)
  {
  
     if (argc != 2) {
        return -1;
     }
     std::stringstream ss(argv[1]);
     size_t n;
     ss &gt;&gt; n;
     vectorPerf(n);
     std::cout &lt;&lt; "\n";
     listPerf(n);
     std::cout &lt;&lt; "\n";
  }
  </code></pre>
  
  <p>For multiple runs of the same set of N, I get results where the results are consistently of the same order as the numbers below:</p>
  
  <pre><code>N       std::vector  std::list
  1000    46           116
  2000    85           217
  5000    196          575
  10000   420          1215
  100000  3188         10497
  1000000 34489        114330
  </code></pre>
  
  <p>What I am wondering is how come the performance of std::list is consistently worse then std::vector. For std::vector I would have expected the performance to be amortized O(N), because the internal object underpinning std::vector would need to be resized time to time. Since all I am doing is inserting an element to the end of the list I would have expected std::list to be O(1). So that would suggest that std::list would do better than std::vector but the opposite seems to be true. </p>
  
  <p>I would appreciate if someone can shed some light on why this is happening. I am compiling on MacOS 10.12.6 using g++ on a 2015 MBP.</p>
  
  <p>Thanks. </p>
  
  <p>EDIT: I now understand that std::vector::push_back() is amortized O(1). However, what is not clear to me is why does std::list::push_back() perform consistently worse than std::vector::push_back()?</p>