QVector против QList

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

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

QList<T>,, QLinkedList<T>и QVector<T>предоставляют аналогичные функции. Вот обзор:

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

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

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

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

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

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

Времена изменились

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

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

См. QListОбъяснения в разделе «За и против» использования . Тем не мение,QList он используется во всех API Qt для передачи параметров и для возврата значений. Используйте QListдля взаимодействия с этими API.

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

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

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

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

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

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

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

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