Контейнер для удаления из любого места по значению с быстрыми итерациями

Question

Я пытаюсь сделать игру Tower Defense, я реализую игровую карту для быстрого поиска объектов в точном радиусе. Я сделал так, чтобы он работал с std :: list (для быстрого указателя сущности push_back и не плохого удаления из любой точки списка), но я обнаружил, что перебор 1500 элементов списка очень длинный. Я не могу набрать даже 10 FPS в моей игре. Я покажу, что MSVS показывает в профилировщике:

после вызова getEntitiesInRadius следующий оператор! =, Который сравнивается с концом списка. Далее идет == вызов оператора. Он работает в режиме отладки. Но я думаю, что даже для отладки итерации 1500 элементов это слишком долго. Может я не прав с этим утверждением?

Answer 1

Я предполагаю, что ваша карта имеет фиксированный размер на протяжении всей игры?std::list совсем не хороший выбор, если вы хотите «самый быстрый», я бы начал с vector, и только если этого недостаточно, я бы посмотрел на другие решения.

Выскажем, вы используете список для «быстрого push_back», но если размер вектора не изменяется (чего можно избежать, используя reserve, конечно, на объектах фиксированного размера (как будет с игровой картой)), push_back для вектора будетнамного быстрееУдаление может быть медленнее (но это не дано).

Кроме того, тестирование производительности на отладочной версии вообще не имеет смысла, сначала убедитесь, что существует проблема, прежде чем пытаться ее решить!