在C++中存储大量短寿命游戏对象

Question

我应该如何存储大量不断变化的对象（例如子弹之类），并按其索引删除它们？听说vector::erase不太高效。

- kapesu8

---

使用std::lists？或者甚至是std::unordered_map和std::list的组合，其中映射的键是发射子弹的实体或列表中拥有对象的实体。 - Vite Falcon

你想将每个子弹存储为单独的对象吗？为什么不将它们存储为带有数量的类型呢？你可以拥有多少种不同类型的弹药？ - KRyan

重复使用对象。将“死亡”的对象放在数组末尾（简单交换），并跟踪最后一个“活着”的子弹索引。 - Cameron

不管你听说过什么，你真的尝试过使用向量吗？搭建一个非常简单的基准测试只需要几分钟，你可以将vector与list和unordered_set进行比较。 - Rook

相关但离题：如果您将要分配和释放大量子弹，您可能需要查看Boost.Pool。 - slartibartfast

Answer 1

使用std::map（或C++11的std::unordered_map），这些容器在插入和删除操作的平均运行时间复杂度方面更好。 std::list也是一个选择（它是显而易见的选择，但我先提到了其他容器，因为它们还允许快速查找/搜索，在许多游戏场景中甚至更加重要）。

在更高层次上，您应该确实了解C++容器以及一般情况下什么是运行时复杂度。明智地选择容器结构对于良好的性能至关重要。

- Alexander Gessler

---

如果您需要频繁插入和删除对象，那么使用unordered_map可能更合适。因为它的插入和删除时间复杂度为O（Log N），这会累积起来。 - Rook

Answer 2

unordered_set<Bullet*> 就可以了。然后你可以简单地在任何地方使用 Bullet*，并忘记索引。最好从对象池或类似的地方分配。

或者，由于标准友好地搞砸了接口，你可能需要使用 std::unordered_map<Bullet*, std::unique_ptr<Bullet>> 来获得更好的异常安全性等。

- Puppy

Answer 3

著名的Alexandrescu认为，短寿命动态小对象的主要问题在于新/释放操作速度慢，建议使用自定义分配器。std::map将使用大量这样的对象（它在内部使用红黑树），因此最好使用预分配对象池或带有自定义分配器的std::map（可能是从Alexandresu的Loki库中获取的）。

- permeakra

Answer 4

从我极其有限的游戏引擎编程二手知识来看，尽可能避免动态内存分配。因此，“大量”频繁删除的情况下，unordered_set或list都是不可取的。

编辑：在阅读了@James Kanze的答案后，我意识到@Cameron的建议将已删除的子弹与最后一个元素交换不起作用，因为它会改变活着的子弹的索引。我想你得使用James的建议，或者可能使用位向量来标记死亡的子弹。

将子弹保持紧凑排列在数组中也非常适合缓存性能。哈希表比std::map的红黑树更好地缓存，但如果您已经按索引引用子弹，为什么要承担哈希的开销呢？

- japreiss

Answer 5

如果您通过向量中的索引来识别子弹，则erase不是一个好主意；它会改变所有后续元素的索引。事实上，子弹是通过其索引进行标识，这在某种程度上限制了您的选择。在这种情况下，最好的解决方案可能是将条目标记为无效，并稍后重用它，可以通过在std::vector中保留无效索引列表（很容易完成），或者仅通过每次想要创建新子弹时扫描向量来完成。如果您有不同类型的子弹（随着游戏的发展，您可能会有），则无论如何都需要动态分配子弹，将指针保存在向量中；空指针对于无效是一个不错的选择。

- James Kanze

Answer 6

vector::erase 不是很高效，因为它需要移动所有后续元素以填充空间以保持顺序。但是，听起来您不需要保留顺序，在这种情况下，您可以通过用末尾的元素替换它，然后删除最后一个元素来更快地删除元素：

std::swap(bullets[index_to_remove], bullets.back());
bullets.pop_back();

- Mike Seymour