获取唯一数字及其释放时间的方法

Question

我有一个使用Box2D的物理模拟，在其中具有相同整数ID的实体不会发生碰撞，例如属于同一角色的实体。但是我有一个问题，我需要能够为每个可能的实体获得唯一的编号，以便没有两个角色意外地获得相同的ID。有限数量的实体被创建和销毁，因此必须在它们属于的实体消失后释放唯一的ID。

一个名为World的类负责创建和销毁所有实体，并且也是管理唯一编号生成和物理模拟相关任何其他事项的实体。

迄今为止，我想到了两种方法，但是我不确定哪种方法更好，或者两种方法是否都适用：

- 保持一个vector<short>，数据是浮动参考数的数量，而向量中的位置则是ID本身。这种方法的缺点在于在编写操作组ID的实体时会创建不必要的复杂性，因为它们需要确保告诉World他们拿走了多少个参考。 - 使用vector<bool>，数据表示该ID是否可用，而向量中的位置则是ID本身。如果不存在空闲插槽，则向量将随着每次新的唯一ID调用而增长。缺点是一旦向量达到一定大小，就需要对整个模拟进行审核，但它的优点是实体能够获取唯一编号，而无需帮助管理引用计数。

你们认为有更好的方法吗？

- Anne Quinn

---

每个主体只有一个对象吗？如果是这样，您可以比较对象的地址。 - Mankarse

每个物体都附有一个或多个“形状”基元，它们具有自己的过滤器ID，因此一个物体可能有多个。我喜欢使用地址的想法，但是过滤器数据存储为负的“short”（实际上，正的ID意味着完全不同的东西，即始终与具有相似ID的形状碰撞）。 - Anne Quinn

Answer 1

你可以在主 World 对象中维护一个未使用 ID 的“空闲”列表，作为一个单向链表。

当一个对象被 World 销毁时（使其 ID 未使用），你可以将该 ID 推入空闲列表的头部。

当你创建一个新对象时，你可以执行以下操作：

If the free list is non-empty: pop the head item and take that ID.
Else increment a global ID counter and assign it's current value.

虽然如果您同时拥有的对象数超过计数器的最大值，仍然可能会用尽ID，但这种策略将允许您循环使用ID，并在O(1)运行时复杂度下完成所有操作。

编辑：根据@Matthieu在下面的评论中的建议，也可以使用std::deque容器来维护“free”列表。该容器还支持使用O(1)复杂度进行的push_front, pop_front操作。

希望这可以帮助您。

- Darren Engwirda

---

你也需要某种引用计数机制吗？你如何知道一个ID何时变为未使用状态？ - Miguel Grinberg

@Clairvoire, Darren：不想打击你的兴致，但是...你正在使用链表作为堆栈。而且堆栈最好使用deque进行实现，以获得更好的内存需求，这可能会导致更好的缓存行为。 - Matthieu M.

@Matthieu：同意 - 你可以使用std::deque代替列表。优点是，对于单向链表来说，pop_front操作非常简单（而且快速），缺点是每个列表节点额外的指针空间是一个（很大的）负面因素。我会进行基准测试并在实践中选择最好的容器... - Darren Engwirda

@Clairvoire：为了使意图更加清晰，您可以通过切换到std::stack并使用容器适配器stack覆盖deque（实际上是默认值）来实现。如果您正在使用*_front操作，则必须将它们更改为*_back。 - Matthieu M.

@Darren：实际上，在deque上，弹出和推入元素可能会更快，因为需要处理的簿记较少。我赞同基准测试的想法，但我认为在OP的情况下速度差异不会很大-->在碰撞检测面前这相当微不足道。 - Matthieu M.

Answer 2

有多少个身体？如果您不重新分配它们，您是否会耗尽整数的可能性是现实的吗？最简单的解决方案是只有一个整数存储下一个ID - 当您为一个物体分配一个新的ID时，您将增加此整数。

- mwd

---

我同意这是最好的选择，只要@Clairvoire不希望使用超过“unsigned”最大值的值。即使如此，使用“long long”也可以解决问题。 - ssell

@ssell：使用float或double会使情况变得更糟。坚持使用整数。如果需要超过2^32，使用long long或者你的环境中对应的64位整数数据类型。 - wallyk

@wallyk 是的，我正要编辑我的评论使用 long long。但很高兴你提到了它！ - ssell

如果您每秒钟使用一个ID超过30次，那么要溢出31位整数需要超过2年的时间。 - Mark Ransom

这些ID本身存储为“short”。我的主要担忧是，随着模拟的进行，它可能会导致我们正在递增的整数溢出回到0，并且如果仍然存在具有低ID的非常旧的对象，则可能会找到另一个最近创建的具有相同ID的对象，因此无法与其发生碰撞。 - Anne Quinn