Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
I have an Object Pool and I will be using it to create Objects. I want to generate an unique id for each object. id should be an integer starting from 0. Ids should be continuous. When an object is deleted that id should be reusable. So that next object created can reuse that id instead of a new id.
And also if there are too many objects deleted this can result in too many reusable ids. For example we created 10 objects. with id 1 to 9. Lets say object with id 2 and object with id 4 are deleted. So ids 2 and 4 are now reusable. And it would be nice if it was possible to shift ids such that object with id 3 will use id 2. and object with id 5 will use id 3 like that. So in the end last id will be 7.
Is there any algorithm which makes it possible to do this efficiently. Id generation in O(1) and id shifting in O(n)