Strange (huge) performance difference between std::vector, QList and std::list

Question

While writing a program which handles a relativly large number of elements (~100k) i noticed a strange difference between std::list and QList. At first i used a std::vector, which performs well. But because the programm often needs to insert elements in a random position in the vector, i switched to std::list, which had a constant time for insertion, when the iterator is at the wanted position.

The problem is, std::list performed way worse than the std::vector with both the insert() and the push_back() method. Measured for adding 100 consequtive elements to a list with 100k elements i got:

• ~25ms for the std::vector (worst case when adding at the beginning)
• over 600ms(!) for std::list (any position, even with push_back() or insert(list.begin()).

Please note, that the time to insert the elements does not include the time to reach the position with the iterator.

I know of the performance problems of lists because of the cache-misses a list causes but this seems to be way off the limits for a cache-miss. Also the time to insert an element(a simple struct with 5 constant length variables) increases with the size of the list. Even the operation to get the size of the list takes more time. This stands in total contrast to the time complexity guaranteed for both operations for the list: constant.

See: Here

Just out of curiosity a changed from std::list to QList and viola: Insertion time is constant and at between 0ms and 1ms.

Here's the code used to measure the time for insertion.

No other operations are performed between the two timepoints: WRONG: used the size() method

std::List:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        listData.insert(listIterator, newElement); 
    }        
    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 662ms

QList:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        QListData.insert(iteratorPos, newElement);
        position++;
    } 

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 1ms

std::vector:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        vectorData.insert(vectorIterator, newElement);

        /*update of the iterator when it was 
        invalidated due to resize of the vector*/
    }    

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 27ms

So, why is there such a huge difference between between QList and std::list? Or better: Why is the performance if std::list so disastrous?

As a side information: Im using the QtEditor with gcc under Linux (Mint) with flags set to c++11

EDIT:

Datatypes and declarations:

typedef struct TOKELEMENT {
    unsigned int column;
    unsigned int lenght;
    unsigned int tType;
    std::string value;
} tokElement;

// the three lists
std::vector<okElement> vectorData;
std::list<tokElement> listData;
QList<tokElement> QListData;

tokElement newElement;

unsigned int iteratorPos;
std::vector<std::vector<tokElement> >::iterator vectorIterator;
std::list<std::vector<tokElement> >::iterator listIterator;

//lineChange is an unsigned int, given as function parameter
unsigned int lineChange;

Answer 1

In contrast to what i mentionend in the question (shame on me), i had another check for the size of the std::list in the for-loop to determine whether to use insert() or push_back() on the list. Since this function doesn't have the time complexity of O(1) but O(n) this slowed down the whole insertion a lot. Thanks to Leeor for pointing this out.

After moving this check out of the for-loop the std::list performed as expetected and even faster than the QList.