Fastest container or algorithm for unique reusable ids in C++
- by gman
I have a need for unique reusable ids. The user can choose his own ids or he can ask for a free one. The API is basically
class IdManager {
public:
int AllocateId(); // Allocates an id
void FreeId(int id); // Frees an id so it can be used again
bool MarkAsUsed(int id); // Let's the user register an id.
// returns false if the id was already used.
};
Assume ids happen to start at 1 and progress, 2, 3, etc. This is not a requirement, just to help illustrate.
IdManager mgr;
mgr.MarkAsUsed(3);
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
Would print
1
2
4
Because id 3 has already been declared used.
What's the best container / algorithm to both remember which ids are used AND find a free id?
If you want to know the a specific use case, OpenGL's glGenTextures, glBindTexture and glDeleteTextures are equivalent to AllocateId, MarkAsUsed and FreeId
