title: Is std::deque faster than std::vector for inserting at the end?
body: <p>I started doing comparisons between:</p>
  
  <ul>
  <li>inserting at the front of list</li>
  <li>inserting at the back of a vector</li>
  <li>inserting at the front of a deque</li>
  </ul>
  
  <p>But then I noticed that even on <code>push_back()</code> the deque seemed to be faster. I must be doing <em>something</em> wrong, I can't believe a more general container would outperform a particular one.</p>
  
  <p>My code using google benchmark:</p>
  
  <pre><code>#include "benchmark/benchmark.h"
  #include &lt;deque&gt;
  #include &lt;vector&gt;
  
  #define NUM_INS 1000
  
  static void BM_InsertVector(benchmark::State&amp; state) {
      std::vector&lt;int&gt; v;
      v.reserve(NUM_INS);
      while (state.KeepRunning()) {
          state.PauseTiming();
          v.clear();
          state.ResumeTiming();
          for (size_t i = 0; i &lt; NUM_INS; i++)
              v.push_back(i);
      }
  }
  BENCHMARK(BM_InsertVector);
  
  static void BM_InsertDeque(benchmark::State&amp; state) {
      std::deque&lt;int&gt; v;
      while (state.KeepRunning()) {
          state.PauseTiming();
          v.clear();
          state.ResumeTiming();
          for (size_t i = 0; i &lt; NUM_INS; i++)
              v.push_back(i);
      }
  }
  BENCHMARK(BM_InsertDeque);
  
  BENCHMARK_MAIN();
  </code></pre>
  
  <p>Results:</p>
  
  <pre><code>Run on (1 X 2592 MHz CPU )
  2016-02-18 14:03:47
  Benchmark         Time(ns)    CPU(ns) Iterations
  ------------------------------------------------
  BM_InsertVector       2820       2470     312500                                 
  BM_InsertDeque        1872       1563     406977
  </code></pre>
  
  <p>I notice <em>some</em> differences when playing with the number of elements, but deque always outperforms vector.</p>
  
  <p>EDIT:
  compiler: <code>gcc version 5.2.1</code>
  compiling with: <code>g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread</code></p>
  
  <p>I think the <code>-O3</code> is actually instrumental; when I turn it off I get a slightly <em>worse</em> deque performance.</p>