Реализация QList

[Alp]

В Ассистанте на тему работу QList'а указано следующее:
===
If T is itself a pointer type or a basic type that is no larger than a pointer, or if T is one of Qt's shared classes, then QList<T> stores the items directly in the pointer array. For lists under a thousand items, this array representation allows for very fast insertions in the middle, and it allows index-based access.
===
Внутри QList'а (точнее QListData) вставка не в начало или конец реализуется как вызов memmove и заполнение освободившегося места. Никак не могу понять за счет чего достигается "very fast insertions"? Для QLinekdList это понятно, четыре указателя перевести, но для листа, чья внутренняя структура так похожа на обычный вектор - непонятно.

Поясните, пожалуйста в чем разница реализации QVector и QList и почему же для интегральных и QT-related типов второй оказывается быстрее первого?

[voronElf]

Шлее пишет, что QVector - просто массив элементов, а QList - это массив указателей на элементы. Эта разница в общем-то дает поле для маневра. Глубже не копал, сказать точно не могу. Просто верю Бланшету, который говорит что QList хоть и тратит больше памяти чем вектор, но работает побыстрее и его использовать предпочтительнее.

Ну и раз так копнул в реализацию, вапрос: QList точно выстраивает элементы в порядке индексации (как вектор), или только указатели на элементы в порядке индексации выстроены (а сами элементы где-угодно как и в LinkedList) ?

[BRE]

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 ()

Поэтому, если вы знаете заранее количество данных, то лучше сразу установить размер вектора, что бы при вставке не происходила переаллокация памяти + перемещение данных. Так же это уменьшит дефрагментацию памяти, это особенно важно при работе с очень большими кусками памяти.

[Igors]

Небольшое добавление к сказанному BRE

Вставка указателя в массив (с помощью memmove, как делает QList), вообще говоря, не есть "very fast insertion". Но это НАМНОГО быстрее вставки в QVector который memmove использовать не может, а должен вызывать конструктор копирования для всех последующих элементов начиная со вставляемого. Эта деталь часто бывает важной.