我将如何存储大量对象（例如子弹或不断变化的此类对象），然后通过它们的索引将它们删除？我听说 vector::erase 效率不高。
问问题
852 次
6 回答
2
使用std::map（或 C++11s std::unordered_map），这些容器对于插入和擦除操作具有更好的分摊运行时复杂性。std::list也是一个选项（这是显而易见的选项，但我首先提到了其他选项，因为它们还允许快速查找/搜索，这在许多游戏场景中更为重要）。
在更高的层次上，您绝对应该阅读 C++ 容器以及一般的运行时复杂性。容器结构的明智选择对于良好的性能至关重要。
于 2012-07-10T15:51:07.670 回答
1
unordered_set<Bullet*>会做得很好。然后，您可以简单地在Bullet*任何地方使用 a 并忘记索引。最好从对象池或类似的东西中分配。
或者，由于标准友好地搞砸了界面，您可能需要std::unordered_map<Bullet*, std::unique_ptr<Bullet>>更好的异常安全性等。
于 2012-07-10T15:53:52.843 回答
1
(in)著名的 Alexandrescu 考虑了短期动态小对象缓慢的 new/free 运算符的主要问题，并建议使用自定义分配器。std::map 将使用很多这样的对象（它在内部使用红黑树），因此最好使用预分配对象池或带有自定义分配器的 std::map（可能取自 Alexandresu 的 Loki 库） )
于 2012-07-10T19:28:22.970 回答
0
vector::erase效率不是很高，因为它需要移动所有以下元素以填充空间以保持顺序。但是，听起来您不需要保留顺序，在这种情况下，您可以通过将元素替换为末尾的元素来更快地删除元素，然后删除最后一个元素：
std::swap(bullets[index_to_remove], bullets.back());
bullets.pop_back();
于 2012-07-10T17:39:44.640 回答
0
根据我对游戏引擎编程的极其有限的二手知识，尽可能避免动态内存分配。因此，对于频繁删除的“大量”，unordered_set或将是一个主要的否决。list
编辑：阅读@James Kanze 的回答后，我意识到@Cameron 建议将已删除的子弹与最后一个元素交换是行不通的，因为它会改变实弹的索引。我想你必须使用詹姆斯的建议，或者可能是一个位向量来标记死子弹。
将子弹压缩在一个数组中对缓存性能也很有好处。哈希表的缓存比std::map的红黑树更好，但是如果您已经按索引引用了项目符号，为什么还要产生哈希开销呢？
于 2012-07-10T16:08:42.900 回答
0
如果您通过它们在向量中的索引来识别子弹，那么erase这不是一个好主意；它将更改以下所有元素的索引。项目符号由其索引标识这一事实在一定程度上限制了您的选择。在这种情况下，最好的解决方案可能是简单地将条目标记为无效，并在以后重用它，或者通过保留无效索引列表（很容易在std::vector一个子弹。如果您有不同类型的子弹（随着游戏的发展，您可能会这样做），无论如何您都需要动态分配子弹，并在向量中保留一个指针；空指针是无效的一个不错的选择。
于 2012-07-10T16:23:58.840 回答