获取唯一的号码并知道它们何时被释放
我有一个物理模拟（使用 Box2D），其中具有相同整数 ID 的物体不会发生碰撞，例如，属于同一角色的物体。但我有一个问题，因为我需要能够为每个可能的实体获取唯一的编号，这样就不会有两个角色意外地获得相同的 ID。尸体的数量是有限的，但它们是根据模拟的指示创建和销毁的，因此一旦它们所属的尸体消失，就必须释放唯一的 ID。
类 World 负责创建和销毁所有物体，也是管理唯一数字生成以及物理模拟涉及的任何其他内容的实体。
到目前为止我想到了两种方法，但我不确定哪种方法更好，如果有的话：
保留一个
向量，数据是引用的数量浮动，向量中的位置就是 ID 本身。此方法的缺点是在对操作组 ID 的实体进行编码时会产生不必要的复杂性，因为它们需要确保告诉World他们要取出多少引用。保留一个
向量，数据是该ID是否空闲，向量中的位置是ID本身。如果不存在空闲槽，则向量将随着对唯一 ID 的每次新调用而增长。缺点是，一旦向量达到一定大小，就需要对整个模拟进行审核，但优点是实体能够获取唯一的数字，而无需帮助管理引用计数。
大家觉得怎么样，还有更好的办法吗？
I have a physics simulation (using Box2D) where bodies with identical integer IDs do not collide, for instance, bodies that belong to the same character. I have a problem though in that I need to be able to get a unique number for each possible entity, so that no two characters accidentally get the same ID. There's a finite number of bodies, but they are created and destroyed as the simulation dictates, so it's necessary to free unique IDs once the body they belonged to is gone.
A class World is responsible for creating and destroying all bodies, and is also the entity that manages the unique number generation, and anything else where physics simulation is concerned.
I thought of two methods so far but I'm not sure which would be better, if either of them at all:
Keep a
vector<short>, with the data being the number of references floating around, and the position in the vector being the ID itself. This method has the disadvantage of creating unneeded complexity when coding entities that manipulate group IDs, since they would need to ensure they tell theWorldhow many references they're taking out.Keep a
vector<bool>, with the data being if that ID is free or not, and the position in the vector being the ID itself. The vector would grow with every new call for a unique ID, if there exist no free slots. The disadvantage is that once the vector reaches a certain size, an audit of the entire simulation would need to be done, but has the advantage of entities being able to grab unique numbers without having to help manage reference counting.
What do you folks think, is there a better way?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以在主
World对象中将未使用 ID 的“空闲”列表作为单链表维护。当一个对象被
World销毁（使其 ID 未被使用）时，您可以将该 ID 推入空闲列表的头部。当您创建新对象时，您可以执行以下操作：
虽然您仍然可能用完 ID（如果您同时拥有的对象数量超过计数器的最大值），但此策略将允许您回收 ID，并执行所有操作运行时复杂度为 O(1)。
编辑：根据@Matthieu 下面的评论， std::deque 容器也可以用于维护“空闲”列表。此容器还支持复杂度为
O(1)的push_front、pop_front操作。希望这有帮助。
You could maintain a "free" list of unused IDs as a singly linked list inside your master
Worldobject.When an object is destroyed by
World(making its ID unused) you could push that ID onto the head of the free list.When you are creating a new object you could do the following:
While you could still run out of IDs (if you simultaneously had more objects than the max value of your counter), this strategy will allow you to recycle IDs, and to do everything with
O(1)runtime complexity.EDIT: As per @Matthieu's comments below, a
std::dequecontainer could also be used to maintain the "free" list. This container also supports thepush_front, pop_frontoperations withO(1)complexity .Hope this helps.
有多少尸体？如果不重新分配整数，是否会用完整数？最简单的解决方案是仅使用一个整数来存储下一个 ID——当您将新 ID 分配给主体时，您将增加该整数。
How many bodies are there? Is it realistic that you'd ever run out of integers if you didn't reassign them? The simplest solution is to just have one integer storing the next ID -- you would increment this integer when you assign a new ID to a body.