Странная (огромная) разница в производительности между std :: vector, QList и std :: list

При написании программы, которая обрабатывает относительно большое количество элементов (~ 100k), я заметил странную разницу между std :: list и QList. Сначала я использовал std :: vector, который хорошо работает. Но поскольку программе часто требуется вставлять элементы в случайную позицию в векторе, я переключился на std :: list, у которого было постоянное время для вставки, когда итератор находится в нужной позиции.

Проблема в том, что std :: list работает хуже, чем std :: vector как с методом insert (), так и с методом push_back (). Измерено для добавления 100 последовательных элементов в список из 100 тыс. Элементов, которые я получил:

• ~ 25 мс для std :: vector (худший случай при добавлении в начале)
• более 600 мс (!) для std :: list (любая позиция, даже с push_back () или insert (list.begin ()).

Обратите внимание, что время вставки элементов не включает время достижения позиции с итератором.

Я знаю о проблемах с производительностью списков из-за того, что список не попадает в кеш-память, но, похоже, это выходит за рамки ограничений для кеш-промаха. Также время для вставки элемента (простой структуры с 5 переменными постоянной длины) увеличивается с размером списка. Даже операция по получению размера списка занимает больше времени. Это полностью контрастирует с временной сложностью, гарантированной для обеих операций для списка: constant.

См. здесь

Просто из любопытства изменено с std :: list на QList и альт: время вставки постоянно и составляет от 0 мс до 1 мс.

Вот код, используемый для измерения времени вставки.

Никакие другие операции не выполняются между двумя точками времени: НЕПРАВИЛЬНО: использовался метод size ()

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";

Результат: прошло: 662 мс

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";

Результат: прошло: 1 мс

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";

Результат: прошло: 27 мс

Итак, почему существует такая огромная разница между QList и std :: list? Или лучше: почему производительность, если std :: list такая катастрофическая?

В качестве дополнительной информации: я использую QtEditor с gcc под Linux (Mint) с флагами, установленными на c ++ 11

РЕДАКТИРОВАТЬ:

Типы данных и объявления:

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;