Существует ли структура данных типа QList в STL или Boost?

Question

просто краткое введение в QList, QList похож на QVector и вектор STL, но, кроме того, он также резервирует некоторое пространство в начале;(и в конце тоже) Я ищу что-то похожее в STL, если не по крайней мере Boost

Резервирование места в начале улучшает добавление или удаление первого элемента (постоянное время), потому что буфер может расти в обратном направлении.Вставка улучшается в зависимости от позиции вставки.Так кто-нибудь знает подобную структуру данных в STL / C ++ ??Спасибо.

Answer 1

std::deque обеспечивает постоянное удаление передней и задней вставки, если это то, что вы ищете.

Answer 2

Если вы хотите эффективную вставку и удаление в начале и конце последовательности, используйте std::deque.

Answer 3

Если вы знаете верхний предел размера контейнера и не планируете вставки в середине контейнера, вы можете использовать boost :: round_buffer .

Если вы выполняете много операций вставки в середине контейнера, deque будет лучшим выбором, чем vector, поскольку он (как правило) группирует элементы в блоки фиксированного размера, а не в один непрерывный блок памяти..

Примечание - QList фактически утверждает, что он использует массив указателей на объекты, если они нетривиальны.Чтобы смоделировать это в C ++, вы должны использовать deque<MyClass*> или (лучше) некоторую интеллектуальную оболочку указателя на MyClass, такую ​​как unique_ptr или shared_ptr, чтобы предотвратить чрезмерное копирование MyClass в ведении хозяйства.*

Внутренне, QList представлен как массив указателей на элементы типа T. Если T сам является указателем или базовым типом, который не больше указателя, или если T является одним из общих классов Qt, тоQList хранит элементы непосредственно в массиве указателей.Для списков менее тысячи элементов это представление массива обеспечивает очень быструю вставку в середину и обеспечивает доступ на основе индекса.