[STL] Vector successive insertion much faster than list

I always thought that because of the reallocation vectors need to do as they grow in size, successively adding elements to one would be slower than doing the same to a list. But apparently that’s far from true. Successively adding elements to a vector takes much less time than doing the same to a list:

   1: //vec.cpp

   2: #include <vector>

   3: using namespace std;

   4:

   5: int main()

   6: {

   7:   vector<int> vec;

   8:   for(int i = 0;i < 100000000;++i)

   9:     vec.push_back(i);

  10:   return 0;

  11: }

   1: //lst.cpp

   2: #include <list>

   3: using namespace std;

   4:

   5: int main()

   6: {

   7:   list<int> lst;

   8:   for(int i = 0;i < 100000000;++i)

   9:     lst.push_back(i);

  10:   return 0;

  11: }

The list code runs in around 19 seconds. The vector code? Less than 3 seconds - over 6 times faster. I suppose that’s because batch allocation of ints runs much faster than allocating linked list nodes one by one by one.

Note: of course, because we know ahead of time exactly how many elements we need, the vector code can be optimized even further to allocate the right number of elements to begin with:

   1: #include <vector>

   2: using namespace std;

   3:

   4: int main()

   5: {

   6:   vector<int> vec(100000000);

   7:   for(int i = 0;i < vec.size();++i)

   8:     vec[i] = i;

   9:   return 0;

  10: }

…which runs in less than 1.5 seconds.

Note: it was brought to my attention that for larger data structures (ie, things larger than ints), the vector’s advantage will begin to degrade as the reallocation and copying begin to take more time.