获得独特的数字并了解他们何时被释放

Question

我有一个物理模拟(使用Box2D),其中具有相同整数ID的物体不会发生碰撞,例如,属于同一个角色的物体.我有一个问题,因为我需要能够为每个可能的实体获取一个唯一的编号,这样就不会有两个字符意外地获得相同的ID.存在有限数量的物体,但是它们是在模拟指示时创建和销毁的,因此一旦它们所属的物体消失,就必须释放唯一的ID.

类World负责创建和销毁所有实体,也是管理唯一数字生成的实体,以及物理模拟所涉及的任何其他实体.

到目前为止我想到了两种方法但是我不确定哪种方法会更好,如果它们中的任何一种方法:

• 保持a vector<short>,数据是浮动的引用数,向量中的位置是ID本身.这种方法的缺点是在编码操纵组ID的实体时会产生不必要的复杂性,因为他们需要确保它们告诉World他们取出的引用数量.

• vector<bool>如果该ID是空闲的,则保持a ,数据为,并且向量中的位置是ID本身.如果没有空闲插槽,则每次调用唯一ID时,向量都会增长.缺点是,一旦向量达到一定大小,就需要对整个模拟进行审计,但具有实体能够获取唯一数字而无需帮助管理引用计数的优点.

你们有什么想法,有更好的方法吗？

Answer 1

您可以将未使用的ID的"免费"列表维护为主World对象内的单个链接列表.

当一个对象被销毁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).

希望这可以帮助.