0

我在我的基于 box2d 的游戏中实现了一个简单的池系统来生成/消失/预池所有对象。所讨论的对象都是在设定半径处创建的所有圆。例如，当我预池化时，我创建了 10 x 2m、5 x 5m、5 x 10m 的圆圈。

现在我正在使用一个简单的链表来存储池对象，所以当我需要获取一个半径为 x 的对象时，可能需要到列表的末尾才能找到具有正确半径的主体，或者找不到它一点也不。这显然很麻烦，而且当我汇集更多对象时只会变得更糟。

我正在考虑使用哈希表，因此我可以使用半径作为哈希键并快速访问正确的对象，但我担心半径值会因值和使用它们的对象数量而有很大差异。例如，我可能在 2m 处有 50 个散列，在 100m 处有 5 个散列，这会造成大量空间浪费，对吧？

我没有使用数据结构的经验，我想了解更多信息，那么什么类型的数据结构最适合有效地处理这样的系统，为什么？

谢谢！

4

2 回答 2

0

使用std::multimap半径作为键和对象作为值。它会给你log N搜索、插入和删除的复杂性。http://www.cplusplus.com/reference/map/multimap/

于 2013-05-07T11:12:32.707 回答
0

哈希表是此类问题的完美解决方案。您想要的是作为键的直径和作为值的圆向量。当具有新键的新项目添加到表中时，应构造一个新向量来保存该值以及任何其他值。如果要向表中添加新项目，但它没有唯一键，则获取该键的现有向量并将新项目添加到向量中。

这不会浪费空间。每个半径值都链接到一个包含具有该半径的项目的向量。关于“例如，我可能在 2m 处有 50 个散列，在 100m 处有 5 个散列，这会造成大量空间浪费，对吧？” 我不明白为什么这会是个问题。如果您对此主题感兴趣，请查看通过链接解决冲突的散列。

于 2013-05-07T06:21:30.990 回答