QList vs QVector пересматривается

Ответ 1

Qt рекламирует QList как "домкрат всех профессий", но другая половина этого высказывания - "хозяин ни одного". Я бы сказал, что QList является хорошим кандидатом, если вы планируете добавлять к обоим концам списка, и они не больше, чем указатель, поскольку QList резервирует пространство до и после. Что касается этого, я имею в виду, насколько подходят причины использовать QList.

QList будет автоматически хранить "большие" объекты в качестве указателя и выделять объекты в куче, что может считаться хорошей вещью, если вы ребенок, который не знает, как объявить QVector<T*> и использовать динамическое распределение. Это не всегда хорошо, и в некоторых случаях это только раздувает использование памяти и добавляет дополнительную косвенность. ИМО всегда является хорошей идеей быть явным о том, что вы хотите, будь то указатели или экземпляры. Даже если вы хотите распределить кучу, всегда лучше выделять ее самостоятельно и просто добавлять указатель в список, чем строить объект один раз, а затем иметь копию, которая находится в куче.

Qt вернет вам QList во многих местах, где он приходит с накладными расходами, например, при получении детей QObject или вы ищете детей. В этом случае нет смысла использовать контейнер, который выделяет пространство перед первым элементом, так как это список объектов, которые уже есть, а не то, что вы, вероятно, предпочтете. Мне также не нравится отсутствие метода resize().

Представьте ситуацию, когда у вас есть объект размером 9 байт и байт в 64-битной системе. Это "слишком много" для QList, поэтому вместо этого будет использовать 8-байтовый указатель + накладные расходы ЦП для распределения медленной кучи + накладные расходы памяти для распределения кучи. Он будет использовать в два раза больше памяти и с дополнительным косвенным доступом для доступа вряд ли будет предлагать преимущества производительности, как рекламируется.

В связи с тем, что QVector не может внезапно стать контейнером "по умолчанию" - вы не меняете лошадей в середине гонки - это унаследованная вещь, Qt - такая старая структура, и хотя много вещей было устаревший, внесение изменений в широко используемые значения по умолчанию не всегда возможно, не нарушая большого количества кода или не создавая нежелательного поведения. Хорошо или плохо, QList, скорее всего, по-прежнему будет использоваться по умолчанию во всем Qt 5 и, вероятно, в следующем крупном выпуске. По той же причине Qt будет продолжать использовать "тупые" указатели, на протяжении многих лет после того, как умные указатели стали обязательными, и все плачут о том, насколько плохи простые указатели и как их нельзя использовать когда-либо.

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

Кроме того, и это только мое личное мнение, но я нахожу много дизайнерских решений в Qt, которые не имеют смысла, будь то эффективность или эффективность использования памяти или простота использования, и в целом есть aa множество фреймворков и языков, которые любят продвигать свои способы делать что-то не потому, что это лучший способ сделать это, а потому, что это их способ сделать это.

И последнее, но не менее важное:

Для большинства целей QList является подходящим классом.

Это действительно сводится к тому, как вы это понимаете. ИМО в этом контексте, "право" не означает "лучший" или "оптимальный", но "достаточно хорошо", как в "он будет делать, даже если не самый лучший". Особенно, если вы ничего не знаете о разных классах контейнеров и о том, как они работают.

Для большинства целей QList будет делать.

Подводя итог:

QList PROs

• вы намерены добавлять объекты не более, чем размер указателя, поскольку он резервирует некоторое пространство в передней части
• вы намерены вставлять середину объектов списка (по существу) больше, чем указатель (и я здесь щедрый, так как вы можете легко использовать QVector с явным указателем для достижения того же и более дешевого - никакой дополнительной копии), так как при изменении размера списка объекты не будут перемещены, только указатели

QList CONs

• не имеет метода resize(), reserve() является тонкой ловушкой, поскольку он не увеличит допустимый размер списка, даже если доступ к индексу работает, он попадает в категорию UB, также вы не сможете переименуйте этот список
• добавляет дополнительную копию и кучу, когда объект больше, чем указатель, что также может быть проблемой, если значение идентификатора объекта
• использует дополнительную косвенность для доступа к объектам, большим, чем указатель
• имеет накладные расходы на процессор и время использования памяти из-за последних двух, а также меньше кэширования
• поставляется с дополнительными накладными расходами при использовании в качестве возвращаемого значения "поиск", поскольку вы вряд ли добавите или даже добавите к этому
• имеет смысл только в том случае, если доступ к индексу является обязательным, для обеспечения оптимальной производительности предварительного и вставки связанный список может быть лучшим вариантом.

CON незначительно перевешивает PROs, а это означает, что, хотя в "случайном" использовании QList может быть приемлемым, вы определенно не хотите использовать его в ситуациях, когда время процессора и/или использование памяти являются критическим фактором. В целом, QList лучше всего подходит для ленивого и небрежного использования, когда вы не хотите рассматривать оптимальный контейнер хранения для прецедента, который обычно представляет собой QVector<T>, a QVector<T*> или QLinkedList (и я исключаю контейнеры "STL", так как мы говорим здесь Qt, контейнеры Qt столь же портативны, иногда быстрее и, безусловно, проще и чище использовать, тогда как контейнеры std бесполезно многословны).

Ответ 2

В Qt 5.7 документация была изменена в связи с обсуждаемой здесь темой. В QVector говорится:

QVector должен быть вашим первым выбором по умолчанию. QVector<T> обычно дает лучшую производительность, чем QList<T>, потому что QVector<T> всегда сохраняет свои элементы последовательно в памяти, где QList<T> будет выделять свои элементы в куче, если sizeof(T) <= sizeof(void*) и T было объявлено как Q_MOVABLE_TYPE или Q_PRIMITIVE_TYPE с помощью Q_DECLARE_TYPEINFO.

Они ссылаются на эту статью от Марка Мутца.

Таким образом, официальная точка зрения изменилась.

Ответ 3

Если размер элемента элемента QList больше, чем указатель размер QList работает лучше, чем QVector, потому что он не сохраняет объекты последовательно, но сохраняет последовательно указатели на копии кучи.

Я бы сказал наоборот. Когда будет проходить через предметы, будет намного хуже. Если он хранит его в качестве указателей на куче, QList будет намного хуже, чем QVector? Причина, по которой последовательное хранилище (QVector все время) настолько хороша, так это то, что это кэширование, когда вы храните указатели, вы теряете локальность данных, начинаете получать промахи в кэше, и это ужасно для производительности.

Контейнер IMHO по умолчанию должен быть QVector (или std::vector), если вас беспокоит много перераспределения, затем предварительно распределите разумную сумму, заплатите разовую стоимость, и вы выиграете в долгосрочной перспективе.

Используйте * Вектор по умолчанию, если при необходимости возникают проблемы с производительностью, профиль и изменения.

Ответ 4

QList - это массив void*.

В своей нормальной работе он new содержит элементы в куче и сохраняет указатель на них в массиве void*. Как связанный список, это означает, что ссылки (но, в отличие от связанных списков, а не итераторы!) С элементами, содержащимися в списке, остаются действительными при всех модификациях контейнеров, пока элемент не будет удален из контейнера. Таким образом, имя "список". Эта структура данных называется массивом-списком и используется во многих языках программирования, где каждый объект имеет ссылочный тип (например, Java). Это очень нечеткая структура данных, похожая на все node.

Но изменение размера списка массивов может быть учтено в вспомогательном классе, не зависящем от типа (QListData), который должен сохранить некоторый размер исполняемого кода. В моих экспериментах практически невозможно предсказать, какой из QList, QVector или std::vector создает наименее исполняемый код.

Это был бы хороший тип данных для многих ссылочных типов Qt, таких как QString, QByteArray и т.д., которые состоят не более, чем указатель на pimpl. Для этих типов QList была получена важная оптимизация: когда тип не больше указателя (и обратите внимание, что это определение зависит от размера указателя платформы - 32 или 64 бит), вместо объектов, выделяющих кучи, объекты хранятся в слотах void*.

Это возможно, однако, если тип тривиально перемещается. Это означает, что он может быть перемещен в памяти с помощью memcpy. Перемещение здесь означает, что я беру объект, memcpy его на другой адрес и - в решающей степени - не запускаю деструктор старого объекта.

И тут все пошло не так. Потому что, в отличие от Java, в С++ ссылка на объект является его адресом. И хотя в исходном QList ссылки были стабильными до тех пор, пока объект не был удален из коллекции, помещая их в массив void*, это свойство больше не выполняется. Это больше не "список" для всех целей и целей.

[ | | | | | | | [ | | | | | | | [ ...
[b|   padding   [b|   padding   [b...

Вместо того, чтобы устанавливать 64 байла в строку кэша, например QVector, QList управляет только 8.

Все пошло не так, как только docs начали называть QList хорошим контейнером по умолчанию. Не это. исходные состояния STL:

Vector является самым простым из классов контейнеров STL и во многих случаях наиболее эффективным.

Скотт Майер Эффективный STL имеет несколько элементов, которые начинаются с "Предпочитаю std::vector поверх...".

Что такое true, в общем, С++ не ошибается, потому что вы используете Qt.

Qt 6 исправит эту ошибку дизайна. Тем временем используйте QVector или std::vector.

Ответ 5

QList - наилучший возможный контейнер для использования, как правило, в документации. Если размер типа элементов равен <= размер указателя = машина и бит операционной системы = 4 или 8 байтов, то объекты сохраняются так же, как и QVector - последовательно в памяти. Если размер элемента элемента QList больше, чем размер указателя QList работает лучше, чем QVector, потому что он не сохраняет объекты последовательно, а сохраняет последовательно указатели на кучи копий. В 32-битном случае изображение выглядит следующим образом:

sizeof( T ) <= sizeof( void* )
=====
QList< T > = [1][1][1][1][1]
                   or
             [2][2][2][2][2]
                   or
             [3][3][3][3][3]
                   or
             [4][4][4][4][4] = new T[];

sizeof( T ) > sizeof( void* )
=====
QList< T > = [4][4][4][4][4] = new T*[]; // 4 = pointer size
              |   |  ...  |
           new T new T   new T

Если вы хотите, чтобы ваши объекты были выложены последовательно в памяти независимо от размера их элементов, как это обычно бывает при программировании OpenGL, тогда вы должны использовать QVector.

Вот описание подробного описания внутренних объектов QList.

Ответ 6

Представьте, что у нас есть класс DataType.

QVector - массив объектов, например:

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList - массив указателей на объекты, например:

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

Следовательно, прямой доступ по индексу будет быстрее для QVector:

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

Но swaping будет быстрее для QList, если sizeof (DataType) > sizeof (DataType *):

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object

// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

Итак, если вам нужен прямой доступ без операций обмена между элементами (например, сортировка, например) или sizeof (DataType) <= sizeof (DataType *), лучшим способом будет использование QVector. В другом случае используйте QList.

Ответ 7

QList ведет себя по-разному в зависимости от того, что внутри (см. исходный код struct MemoryLayout):

• если sizeof T == sizeof void* и T определены Q_MOVABLE_TYPE, тогда QList<T> ведет себя точно так же, как QVector, то есть данные хранятся смежно в памяти.

• Если sizeof T < sizeof void* и T определены Q_MOVABLE_TYPE, то QList<T> заполняет каждую запись до sizeof void* и теряет совместимость с QVector.

• во всех остальных случаях, QList<T> является связанным списком и поэтому замедляется до некоторой степени.

Это то, что делает QList<T> во многом всегда плохим выбором, потому что в зависимости от отличных деталей QList<T> является либо действительно списком, либо вектором. Это плохой дизайн API и склонны к ошибкам. (Например, вы столкнетесь с ошибками, если у вас есть библиотека с открытым интерфейсом, которая использует QList<MyType> внутренне и в своем открытом интерфейсе. sizeof MyType is < sizeof void*, но скажите, что вы забыли объявить MyType как Q_MOVABLE_TYPE. хочу добавить Q_MOVABLE_TYPE. Это двоичный несовместимый, что означает, что теперь вам нужно перекомпилировать весь код, который использует вашу библиотеку, поскольку макет памяти QList<MyType> изменен в общедоступном API. Если вы не будете осторожны, вы пропустите это и ввести ошибку. Это очень хорошо иллюстрирует, почему QList является плохим выбором здесь.)

Тем не менее, QList все еще не совсем плох: он, вероятно, будет делать то, что вы хотите в большинстве случаев, но, возможно, он будет выполнять работу за сценой по-другому, чем вы могли бы ожидать.

Правило большого пальца:

• Вместо QList используйте QVector<T> или QVector<T*>, так как он явно говорит, что вы хотите. Вы можете комбинировать это с std::unique_ptr.

• В С++ 11 и далее считается, что лучше всего использовать std::vector, так как он будет корректно вести себя в range- основанный на цикле. (QVector и QList могут отсоединиться и, следовательно, выполнить глубокую копию).

Вы можете найти все эти детали и многое другое в презентации от Marc Mutz и в видео Оливье Гоффарт.