Когда следует использовать вектор / список?

Я могу понять, когда использовать списки, но не понимаю, когда лучше использовать векторы, чем использовать списки в видеоиграх: когда лучше иметь быстрый произвольный доступ?

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

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

Скорость, которую вы получите, поместив все свои элементы в свой контейнер в непрерывную память (и, следовательно, более дружественную к кешу), стоит возмещения дополнительных затрат на добавление / удаление / изменение размера вектора.

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

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

Вы также можете рассмотреть возможность использования Deque. Он имеет характеристики производительности, схожие с векторными, но не требует векторной смежной памяти и немного более гибок.

Ваш выбор должен отражать ваши потребности. Все элементы векторов непрерывны в памяти, и списки имеют указатели на следующие / предыдущие элементы, поэтому у каждого из них есть свои преимущества / недостатки:

Списки:

• Каждый элемент занимает 2 целых числа, чтобы указать на предыдущий и следующий элементы, поэтому чаще всего это 8 байт больше для каждого элемента в вашем списке
• Вставка линейна по времени: O (n)
• Удалить это постоянная операция: O (1)
• Доступ к элементу x является линейным по времени: O (n)

Векторы:

• Требуется меньше памяти (нет указателей на другие элементы, это простой математический алгоритм)
• Удалить линейно по времени: O (n)
• Доступ к элементу x постоянен: O (1) (это потому, что элементы постоянно находятся в памяти, поэтому это простая математическая операция vectorPtr + (x * bytesOfTheType))
• Вставка может выполняться за линейное время, но чаще всего это постоянная операция: O (1) (это потому, что вектор в массиве, но всегда резервирует в 2 раза больше своей емкости, когда массив заполнен, поэтому копирование массива происходит не часто)

Таким образом, список лучше, когда вашей программе нужно часто добавлять и удалять элементы, но никогда не получать (или редко обращаться) к определенному элементу без необходимости в других. Вектор должен использоваться для лучшего времени доступа, но он недостаточно эффективен, когда вам нужно удалить или добавить элементы.

Проверьте этот пост на stackoverflow, он представляет действительно хороший график с базовыми вопросами о ваших потребностях, который приводит вас к конкретному контейнеру в зависимости от ваших ответов:

/programming/366432/extending-stdlist

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

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

Мнение Tetrads может быть правдой, но это зависит от языка программирования, который используется. Я вижу, что вы пометили свой вопрос c++, но я попытался дать ответ, который не зависит от языка.

В консольных играх мы никогда не используем std :: list, потому что:

1. он выделяет память каждый раз, когда вы добавляете новый элемент. распределение памяти медленное.
2. он полон указателей. указатели плохие. указатель является пропуском кэша. промах кэша плох.

даже std :: vector теряет популярность на консолях, потому что:

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