Какой контейнер STL я должен использовать? Переполнение стека

Question

Какой контейнер STL я должен использовать? Переполнение стека

У меня есть «список» объектов, из которого я хочу взять объект в произвольном положении и выдвинуть его перед этим списком. Только такая операция будет выполнена. Поэтому мне не нужен быстрый доступ к концу списка, только к его переднему и среднему доступу к любому другому месту.

Какой контейнер будет лучшим для этого? Я думал о std::vector, но я прочитал это insert операция не эффективна. Потом я придумал std::deque из-за его быстрого доступа к фронту, но как насчет эффективности его erase на конкретный метод позиции?

Заранее спасибо за помощь.

4

c++containers deque stl vector

Решение

Другие решения

На основании этого ответа: https://stackoverflow.com/a/471481/1284631 (а также на этом: https://stackoverflow.com/a/471461/1284631) Я бы пошел за списком. Дешево добавлять, повторять, вставлять и удалять.

PS: Это зависит, если случайная позиция основана на индексе или нет (то есть, если вы знаете, численно какая позиция или объект, который нужно переместить в начало, приводит к итерации по списку и проверке его свойств).

Итак: если позиция известна без повторения списка, то перейдите к вектору.
если позиция требует итерации по коллекции, перейдите к списку.

2

Источник

Accepted Answer

Мы можем дать вам рекомендации, но не дать однозначного ответа — вам нужно сравнить их самостоятельно, потому что это в решающей степени зависит от вашей коллекции и размера объекта:

Для небольших предметов и / или относительно небольшой коллекции, std::vector будет быстрее, потому что даже если вам нужно скопировать больше данных, лучшее время произвольного доступа (O (1) против O (n) для std::list) и локальность кэша будет доминировать.
Для больших объектов и / или большой коллекции, std::list будет быстрее, потому что хотя вам нужно O (n), чтобы выбрать случайный объект, вставка будет намного быстрее, так как копирование многих крупных объектов происходит очень медленно.

Но в чем именно заключается разрыв между этими двумя сценариями, я не могу сказать.

Кроме того, если вы можете сойти с рук обменивать элементы вместо вставки, это не просто: всегда используйте std::vector,

7