我有一个物理模拟(使用Box2D)，其中具有相同整数id的物体不会碰撞，例如，属于相同字符的物体。我有一个问题，虽然在我需要能够得到一个唯一的数字为每个可能的实体，所以没有两个字符意外获得相同的ID。身体的数量是有限的，但它们会按照模拟的指令被创建和销毁，所以一旦它们所属的身体消失，就有必要释放唯一的id。
类World负责创建和销毁所有物体，也是管理唯一数字生成的实体，以及涉及物理模拟的任何其他内容。
到目前为止，我想到了两种方法，但我不确定哪一种更好，如果他们中的任何一个:
-
保持
vector<short>，其中数据为浮动的引用数，向量中的位置为ID本身。这种方法的缺点是在编码操纵组id的实体时产生不必要的复杂性，因为它们需要确保它们告诉World它们取出了多少引用。 -
保持
vector<bool>，数据是该ID是否空闲，并且向量中的位置是ID本身。如果没有空闲槽，向量将随着每次对唯一ID的新调用而增长。缺点是，一旦向量达到一定大小，就需要对整个模拟进行审计，但优点是实体能够获取唯一的数字，而无需帮助管理引用计数。
你们怎么想，有没有更好的办法?
您可以在主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容器也可以用来维护"免费"列表。该容器还支持push_front, pop_front操作，但复杂度为O(1)。
有多少个主体?如果不重新赋值，是否可能用完整数?最简单的解决方案是只用一个整数来存储下一个ID——当您将新ID分配给body时，您将增加这个整数。