QVector vs QList

У меня есть список целых чисел, которые мне нужно перебрать, но массив неадекватен. Каковы различия между векторами и списками и есть ли что-нибудь, что мне нужно знать, прежде чем я выберу тип?

Чтобы быть ясным, я прочитал документы QT, но это степень того, что я знаю:

QList, QLinkedList и QVector обеспечивают аналогичную функциональность. Вот обзор:

Для большинства целей QList является подходящим классом. Его API на основе индексов более удобен, чем API-интерфейс, основанный на итераторе QLinkedList, и он обычно быстрее, чем QVector, из-за того, как он хранит свои элементы в памяти. Он также расширяется до меньшего количества кода в вашем исполняемом файле.

Если вам нужен настоящий связанный список, с гарантией постоянных вставок времени в середине списка и итераторов на элементы, а не на индексы, используйте QLinkedList.

Если вы хотите, чтобы элементы занимали смежные позиции памяти, используйте QVector.

Ответ 1

QVector в основном аналогичен std::vector, как вы можете догадаться из названия. QList ближе к boost::ptr_deque, несмотря на кажущуюся связь с std::list. Он не хранит объекты напрямую, а вместо них хранит указатели на них. Вы получаете все преимущества быстрых вставок с обоих концов, а перераспределение включает в себя перетаскивание указателей вместо конструкторов копий, но теряют пространственную локальность фактического std::deque или std::vector и получают много распределений кучи. У него есть некоторые решения, чтобы избежать выделения кучи для небольших объектов, восстанавливая пространственную локальность, но из того, что я понимаю, это применимо только к вещам, меньшим, чем int.

QLinkedList аналогичен std::list и имеет все его недостатки. Вообще говоря, это должен быть ваш последний выбор контейнера.

Библиотека QT в значительной степени способствует использованию объектов QList, поэтому предпочтение от них в вашем собственном коде иногда может избежать некоторых излишних скуки. Дополнительное использование кучи и случайное позиционирование фактических данных теоретически могут пострадать в некоторых случаях, но часто это незаметно. Поэтому я предлагаю использовать QList, пока профилирование не предложит изменить на QVector. Если вы ожидаете, что смежное распределение будет важно [читайте: вы взаимодействуете с кодом, который ожидает T[] вместо QList<T>], что также может быть причиной для начала с QVector с места в карьер.

Если вы спрашиваете о контейнерах в целом и просто использовали документы QT в качестве ссылки, то приведенная выше информация менее полезна.

An std::vector - это массив, размер которого можно изменить. Все элементы хранятся рядом друг с другом, и вы можете быстро получить доступ к отдельным элементам. Недостатком является то, что вставки эффективны только с одного конца. Если вы помещаете что-то посередине или в начале, вам нужно скопировать другие объекты, чтобы освободить место. В примечаниях с большими охами вставка в конце - O (1), вставка где-либо еще - O (N), а произвольный доступ - O (1).

An std::deque аналогичен, но объекты guarentee не хранятся рядом друг с другом и позволяют вставлять с обоих концов O (1). Это также требует выделения меньших фрагментов памяти за раз, что иногда может быть важным. Случайным доступом является O (1), а вставка в середине - O (N), такая же, как для a vector. Местная местность хуже, чем std::vector, но объекты, как правило, группируются, поэтому вы получаете некоторые преимущества.

An std::list - связанный список. Это требует большого объема памяти из трех стандартных последовательных контейнеров, но предлагает быструю вставку в любом месте... если вы знаете заранее, где вам нужно вставить. Он не предлагает произвольный доступ к отдельным элементам, поэтому вам нужно итерации в O (N). Но как только там, фактическая вставка - O (1). Самое большое преимущество std::list заключается в том, что вы можете быстро их объединить... если вы перемещаете весь диапазон значений в другой std::list, вся операция O (1). Кроме того, гораздо сложнее сделать недействительными ссылки в списке, что иногда может быть важно.

Как правило, я предпочитаю std::deque - std::vector, если мне не нужно передавать данные в библиотеку, ожидающую необработанный массив. std::vector гарантируется непрерывным, поэтому &v[0] работает для этой цели. Я не помню, как в прошлый раз, когда я использовал std::list, но это было почти наверняка, потому что мне нужен был более сильный guaretee относительно оставшихся ссылок.

Ответ 2

В QVector похож на std::vector. QLinkedList похож на std::list. QList - вектор на основе индекса, но позиция памяти не гарантируется (например, std::deque).

Ответ 3

Все изменилось

Теперь мы находимся в Qt 5.8, и все изменилось, поэтому документация. Это дает ясный и другой ответ на этот вопрос:

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

См. "За и против использования QList" для объяснение. Однако QList используется во всех API Qt для прохождения параметры и возвращаемые значения. Используйте QList для взаимодействия с этими API-интерфейсы.

Ответ 4

Из документа QtList:

QList используется в большинстве случаев. Для структур с тысячей элементов позволяет эффективную установку в середине и обеспечивает индексированный доступ. prepend() и append() очень быстро, так как память предварительно распределена на обоих концах внутреннего массива. QList<T> - это массив указателя типа T. Если T имеет указательный или Qt-общий тип указателя, объект хранится непосредственно в массиве
QVector является предпочтительным в случае большого количества append() или insert() новых элементов с размером, большим, чем указатель, поскольку QVector выделяет память для своих элементов в одном распределении кучи. Для QList для вставки добавления нового элемента требуется выделение памяти нового элемента в куче. Короче говоря, если вы хотите, чтобы элементы занимали смежные позиции памяти, или если ваши элементы больше, чем указатель, и вы хотите избежать накладных расходов, выделяя их в куче индивидуально во время вставки, используйте QVector.

Ответ 5

QVector похож на массив, который может изменять размер (увеличивать или уменьшать), но он связан с большими транзакциями и вычислениями и временем.

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

Однако QLinkedList работает с указателями. Поэтому, когда создается новый элемент, выделяется только новое пространство памяти и привязывается к единственному фрагменту памяти. Поскольку он работает с указателями, он работает быстрее и эффективнее.

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