Didn't read entire thread so pardon me if it was mentioned before.

You could use a vector, and do sth like this

int xxxManager::create ()
{
if (freeIDs.size()
{
take item from freeID's list/prio-queue/whatever structure you use
create new item on objects[id];
return id;
}
else
{ objects.push_back();
return objects.size()-1;
}
}

void xxxManager::destroy (int id)
{
// validity checks ...
delete objects[id];
freeIDs.push_back (id);
}

So need for re-organising id's, the few 'holes' which appear
are filled up quickly and holes only take 4 bytes (1 ptr)

Regards
Roger