QList разные данные хранит по разному.
Если sizeof( T ) <= sizeof( void* ), то все данные хранятся в непрерывном куске памяти. Соответственно вставка/удаление записи происходит перемещением куска памяти.
Если же sizeof( T ) больше размера указателя, то в непрерывном куске памяти хранятся только указатели на блоки с данными. Вставка/удаление указателя также происходит с помощью перемещения куска памяти.
Ускорение получается за счет преаллокации памяти (реально выделяется непрерывный кусок памяти для хранения большего числа данных/указателей), что позволяет минимизировать расходы на аллокацию памяти + снижает дефрагментацию.
При вставке каждого элемента не приходится выделять заново новый кусок памяти и перемещать туда данные (или указатели), а достаточно только их раздвинуть. Новый буфер будет захвачен, только когда текущий будет полностью заполнен. А чем больше элементов в коллекции, тем больше будет резервироваться памяти на будущее.
Вот цитата из asssisten по поводу стратегии для QString, но она же работает и для QList, QVector:
Growth Strategies
...
We build the string out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to the QString string. Then the following 18 reallocations (out of a possible 15000) occur when QString runs out of space: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. At the end, the QString has 16372 Unicode characters allocated, 15000 of which are occupied.
Для QVector есть даже специальные методы для управления его реальными размерами:
int QVector::capacity () const
void QVector::reserve ( int size )
void QVector::squeeze ()
Поэтому, если вы знаете заранее количество данных, то лучше сразу установить размер вектора, что бы при вставке не происходила переаллокация памяти + перемещение данных. Так же это уменьшит дефрагментацию памяти, это особенно важно при работе с очень большими кусками памяти.
