c++ - 频繁创建和删除的游戏对象应该使用什么容器？

Question

我正在做一个游戏，我经常创建对象并杀死它们。我必须能够线性循环对象列表，下一个对象总是比前一个对象新，因此对象的渲染将是正确的(它们将重叠)。我还需要能够将每个对象的指针存储到四叉树中，以便快速找到附近的对象。

我的第一个想法是使用 std::list，但我以前从未做过这样的事情，所以我正在寻找专家对此的想法。

我应该使用什么容器？

编辑:我不只是从前面删除:对象可以按任何顺序被杀死，但它们总是添加到列表的末尾，所以最后一项是最新的。

Answer 1

std::vector是您不确定自己在做什么时推荐使用的容器。只有当您知道这对您不起作用时，您才应该选择其他东西。

就是说，如果您经常在容器的后面添加并从前面删除，您可能需要 std::deque . [编辑]但看起来这不是您正在做的。

我想您可能需要两个容器，一个用于维护插入顺序，一个用于您的四叉树。 Internet 上有很多四叉树实现，所以我将重点介绍另一个。使用std::list正如您所建议的那样，删除操作本身 比 vector 或 deque 更快。它还具有让您存储迭代器的优点，因为在删除元素时列表不会使其他迭代器无效。四叉树中的对象可以在插入顺序列表中维护一个迭代器。当您从四叉树中删除一个元素时，您也可以在 O(1) 时间内将其从列表中删除。

一如既往，关于使用哪个容器的决定完全取决于权衡。列表伴随着 vector 的内存占用增加和连续内存布局的丢失。当您的数据集很大时，您可能会惊讶于缓存位置的重要性。唯一可以确定的方法是尝试各种容器，看看哪种容器最适合您的应用程序。