我正在做一个游戏，我创建对象并经常杀死它们。我必须能够线性循环对象列表，下一个对象总是比上一个对象更新，因此对象的渲染将是正确的（它们将重叠）。我还需要能够将每个对象的指针存储到四叉树中，以便快速找到附近的对象。
我的第一个想法是使用std::list，但我以前从未做过这样的事情，所以我正在寻找专家对此的想法。
我应该使用什么容器？
编辑：我不只是从前面删除：对象可以按任何顺序被杀死，但它们总是被添加到列表的末尾，所以最后一项是最新的。
问问题
961 次
3 回答
2
当您不确定自己在做什么时，推荐使用std::vector容器。只有当您知道这对您不起作用时，您才应该选择其他东西。
也就是说，如果您经常添加到容器的后面并从前面删除，您可能需要std::deque。 [编辑]但看起来这不是你在做什么。
我想您可能需要两个容器，一个用于维护插入顺序，一个用于四叉树。Internet 上有很多四叉树的实现，所以我将重点介绍另一种。按照您的建议使用std::list将使删除操作本身比向量或双端队列更快。它还具有让您存储迭代器的优点，因为 list 在删除元素时不会使其他迭代器无效。四叉树中的对象可以在插入顺序列表中维护一个迭代器。当您从四叉树中删除一个元素时，您也可以在 O(1) 时间内将其从列表中删除。
与往常一样，关于使用哪个容器的决定完全取决于权衡。列表与向量相比会增加内存占用，并且会丢失连续的内存布局。当您的数据集很大时，您可能会惊讶于缓存位置的重要性。唯一确定的方法是尝试各种容器，看看哪个容器最适合您的应用程序。
于 2012-06-19T12:47:46.330 回答
1
我认为boost::stable_vector适合您删除\迭代的需求。
于 2012-06-19T12:41:43.697 回答
0
因此，您希望能够按照添加项目的顺序遍历您的容器，但您希望能够从容器中的任何点移除项目。一个简单的queue显然不会破解它。
令人高兴的是，有 4 个容器可以轻松完成这项工作std::vector，std::list和。如果您使用标准容器惯用语（例如, , , , 以及在较小程度上的 , , , ），您可以使用您喜欢的任何容器。通过这 8 个操作，您可以在 、 和 之间切换，并且仅使用前 4 个操作，您也可以使用。编写您的代码，然后您可以轻松地在不同的容器类型之间进行切换和更改，并进行一些分析以比较性能和内存开销等。std::dequestd::setbeginenderaseinsertpush_frontpop_backfrontbackstd::vectorstd::liststd::dequestd::set
直觉上，std::list这可能是一个不错的选择，也许std::set也可以。但与其做出假设，不如使用模板库为您提供的通用工具，稍后当您有一些有意义的性能数据可供使用时，对其进行分析和优化。
于 2012-06-19T13:02:58.560 回答