QVector против QList

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

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

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

  • для большинства целей QList является правильным классом для использования. Свой API на основе индексов более удобен, чем API на основе итераторов QLinkedList, и обычно он быстрее, чем QVector, из-за того, как он хранит свои элементы в памяти. Он также расширяется до меньшего количества кода в исполняемом файле.
  • Если вам нужен реальный связанный список, с гарантиями постоянных временных вставок в середине списка и итераторов к элементам, а не индексам, используйте QLinkedList.
  • если вы хотите, чтобы элементы занимали соседние позиции памяти, используйте QVector.
5 64
c++ list qt vector

5 ответов:

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 - это массив, который можно изменить. Все элементы хранятся рядом друг с другом, и вы можете быстро получить доступ к отдельным элементам. Недостатком является то, что вставки эффективны только на одном конце. Если вы положили что-то в середине или в начале, вы должны скопировать другие объекты, чтобы освободить место. В нотации big-oh вставка в конце - O(1), вставка в любом другом месте-O(N), а произвольный доступ-O(1).

An std::deque аналогично, но не гарантирует, что объекты хранятся рядом друг с другом, и позволяет вставке на обоих концах быть 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, но это было почти наверняка, потому что мне нужна была более сильная гарантия ссылки остаются действительными.

108

что изменилось

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

QVector должен быть вашим первым выбором по умолчанию. QVector обычно дайте лучшую производительность, чем QList, потому что QVector всегда сохраняет свои элементы последовательно в памяти, где QList будет выделять его элементы в куче, если sizeof (T)

см. плюсы и минусы использования QList для объяснение. Однако, QList используется на протяжении интервала QT API для прохождения параметры и для возвращаемых значений. Используйте QList для взаимодействия с ними Апис.

29

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

10

из qtlist doc:

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

  • QVector предпочитает в дело много append() или insert() новых элементов с размером больше указателя, так как QVector выделяет память для своих элементов в одной куче. Ибо QList, вставка добавления нового элемента требует выделения памяти нового элемента в куче. Короче говоря, если вы хотите, чтобы элементы занимали соседние позиции памяти, или если ваши элементы больше указателя, и вы хотите избежать накладных расходов на выделение их в куче по отдельности во время вставки, то используйте QVector.

2

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

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

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

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

-2