Getting Unique Numbers and Knowing When They're Freed

Question

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 the World how 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?

Answer 1

You could maintain a "free" list of unused IDs as a singly linked list inside your master World object.

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:

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.

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::deque container could also be used to maintain the "free" list. This container also supports the push_front, pop_front operations with O(1) complexity .

Hope this helps.