Vector vs Deque Insertion Time

Question

I read this nice experiment comparing, in particular, the performance of calling insert() on both a vector and a deque container. The result from that particular experiment (Experiment 4) was that deque is vastly superior for this operation.

I implemented my own test using a short sorting function I wrote, which I should note uses the [] operator along with other member functions, and found vastly different results. For example, for inserting 100,000 elements, vector took 24.88 seconds, while deque took 374.35 seconds.

How can I explain this? I imagine it has something to do with my sorting function, but would like the details!

I'm using g++ 4.6 with no optimizations.

Here's the program:

#include <iostream>
#include <vector>
#include <deque>
#include <cstdlib>
#include <ctime>

using namespace std;

size_t InsertionIndex(vector<double>& vec, double toInsert) {
  for (size_t i = 0; i < vec.size(); ++i)
    if (toInsert < vec[i])
      return i;
  return vec.size();  // return last index+1 if toInsert is largest yet                                                                          
}

size_t InsertionIndex(deque<double>& deq, double toInsert) {
  for (size_t i = 0; i < deq.size(); ++i)
    if (toInsert < deq[i])
      return i;
  return deq.size();  // return last index+1 if toInsert is largest yet                                                                          
}

int main() {
  vector<double> vec;
  deque<double> deq;

  size_t N = 100000;

  clock_t tic = clock();
  for(int i = 0; i < N; ++i) {
    double val = rand();
        vec.insert(vec.begin() + InsertionIndex(vec, val), val);
    //        deq.insert(deq.begin() + InsertionIndex(deq, val), val);                                                                           
  }

  float total = (float)(clock() - tic) / CLOCKS_PER_SEC;
  cout << total << endl;
}

Answer 1

The special case where deque can be much faster than vector is when you're inserting at the front of the container. In your case you're inserting at random locations, which will actually give the advantage to vector.

Also unless you're using an optimized build, it's quite possible that there are bounds checks in the library implementation. Those checks can add significantly to the time. To do a proper benchmark comparison you must run with all normal optimizations turned on and debug turned off.

Answer 2

Your code is performing an insertion sort, which is O(n^2). Iterating over a deque is slower than iterating over a vector.

I suspect the reason you are not seeing the same result as the posted link is because the run-time of your program is dominated by the loop in InsertionIndex not the call to deque::insert (or vector::insert.