Какой контейнер следует использовать для часто создаваемых и удаляемых игровых объектов?

Если вы не уверены что ты делаешь. Только когда вы знаете, что это не сработает для вас, вы должны выбрать что-то другое.

Тем не менее, если вы регулярно добавляете содержимое в заднюю часть контейнера и удаляете его в начало, вам, вероятно, понадобится std::deque. [Изменить] Но, похоже, это не то, чем вы занимаетесь.

Я думаю, вам может понадобиться два контейнера: один для поддержания порядка вставки и один для дерева квадрантов. В Интернете есть множество реализаций дерева квадрантов, поэтому я сосредоточусь на другой. Использование std::list, как вы предлагаете, сделает операцию удаления самой быстрее, чем vector или deque. Это также имеет то преимущество, что позволяет хранить итераторы, потому что list не делает недействительными другие итераторы при удалении элемента. Ваши объекты в дереве квадрантов могут поддерживать итератор в списке порядка вставки. Когда вы удаляете элемент из дерева квадрантов, вы можете удалить его и из списка за время O(1).

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

Я думаю, boost::stable_vector соответствует вашим потребностям в удалении\итерации.

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

К счастью, есть 4 контейнера, которые достаточно легко справятся с этой задачей: std::vector, std::list, std::deque и std::set. Если вы используете стандартные идиомы контейнеров (например, begin, end, erase, insert и, в меньшей степени, push_front, pop_back, front, back), вы можете использовать любой контейнер, который вам нравится. С этими 8 операциями вы можете переключаться между std::vector, std::list и std::deque, а только с первыми 4 вы также можете использовать std::set. Напишите свой код, а затем вы сможете легко переключаться между различными типами контейнеров и выполнять небольшое профилирование, чтобы сравнить производительность и накладные расходы памяти или что-то еще.

Интуитивно можно предположить, что std::list будет хорошей ставкой, и, возможно, std::set тоже сработает. Но вместо того, чтобы делать предположения, просто используйте общие инструменты, которые предоставляет вам библиотека шаблонов, и профилируйте и оптимизируйте вещи позже, когда у вас будут значимые данные о производительности для работы.