Getting unique numbers and knowing when they are released

Question

I have a physical simulation (using Box2D) where bodies with identical integer identifiers do not collide, for example, bodies that belong to the same symbol. I have a problem, though, in that I need to be able to get a unique number for each possible object, so that no two characters accidentally get the same identifier. There are a finite number of bodies, but they are created and destroyed as the simulation dictates, so it is necessary to release unique identifiers as soon as the body to which they belong has disappeared.

The World class is responsible for creating and destroying all bodies, as well as for the organization that controls the unique generation of numbers, and something else related to physical modeling.

I was thinking of two methods, but I'm not sure if it would be better if any of them at all:

• Save vector<short> , the data will be the number of links floating around, and the position in the vector is the identifier itself. This method has the disadvantage of creating unnecessary complexity when coding entities that manipulate group identifiers, as they will need to ensure that they tell World how many links they take out.

• Save vector<bool> when the data will be, if this identifier is free or not, and the position in the vector, which is the identifier itself. The vector will grow with each new call for a unique identifier, if there are no free slots. The disadvantage is that as soon as the vector reaches a certain size, it is necessary to audit the entire simulation, but it has the advantage that entities can capture unique numbers without helping to control the reference count.

What do you think is the best way?

Answer 1

You can save the “free” list of unused identifiers as a separate list inside your main World object.

When an object is destroyed by World (its identifier is not used), you can click this identifier on the head of the free list.

When you create a new object, you can 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 current value. 

While you can still use identifiers (if you simultaneously had more objects than the maximum value of your counter), this strategy will allow you to process identifiers and do everything with O(1) execution complexity.

EDIT: according to @Matthieu's comments below, the std::deque container can also be used to support a “free” list. This container also supports push_front, pop_front with O(1) complexity.

Hope this helps.

Answer 2

How many bodies are there? Is it realistic that you will ever finish the integers unless you reassign them? The simplest solution is to have only one integer storing the next identifier - you must increment this integer when you assign a new identifier to the body.