Deletion from vector took less time than deletion from list. Why?

Question

In C++ manual I found next:

Vectors are relatively efficient adding or removing elements from its end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references than lists and forward_lists.

Also, in 'complexity' of 'erase' method of vector I found next:

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

In 'complexity' of 'erase' method of list next:

Linear in the number of elements erased (destructions).

But when I tested it in the 30 millions elements in each container (I deleted from 24357 element to 2746591 element), I got that deleting from vector took 5 ms, but from list 8857 ms. Difference is huge and confusing...

Here is my code:

#include "stdafx.h"
#include <vector>
#include <list>
#include <iostream>
#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    const long int x = 30000000;
    vector<char> v;
    vector<char>::iterator itv1, itv2;
    list<char> l;
    list<char>::iterator itl1, itl2;
    unsigned start, end;

    long int first, last;

    cout << "Please enter first position: \n";
    cin >> first;
    cout << "Please enter last position: \n";
    cin >> last;

    for (long int i = 0; i < x; ++i)    {
        char c;
        c = (rand() % 26) + 'a';
        v.push_back(c);
        l.push_back(c);
    }

    cout << "Starting deletion\n";
    start = clock();
    itv1 = v.begin() + first;
    itv2 = v.begin() + last;
    v.erase(itv1, itv2);
    end = clock();
    cout << "End " << end-start << "\n";

    start = clock();
    itl1 = itl2 = l.begin();
    advance(itl1, first);
    advance(itl2, last);
    l.erase(itl1, itl2);
    end = clock();
    cout << "End " << end-start << "\n";
    return 0;
}

Could you explain - what causes such difference? My opinion - moving iterators in list much slower than in vectors - but I don't sure.

Many thanks!

Answer 1

In your case, likely because you're not measure the erase time, you're measuring the time taken for two advance calls and the erase call.

But more generally: because O() complexity only tells you about the algorithmic complexity not the actual time taken. O(1) can have a huge constant time value. Worse, the complexity is theoretical; it does not consider the realities of how hardware works.

In fact because the vector delete accesses memory in a linear fashion it can be efficiently cached and predicted whilst the list delete operates in a random access fashion. This can mean that vector delete is faster in practice than list delete when you have a small vector.