Get first available key in map

Question

I have a map that stores pointers to an object by their ID.

typedef std::map<unsigned int, Entity*> entityMap;
entityMap entitymap;

To assign an ID to Entity I could just take the newest value in entitymap and increase it by 1.

Entity *entity = new Entity;
entity->id = /*newest entity+1*/;
entitymap.insert(std::pair<unsigned int,Entity*>(entity->id,entity));

But the number could become unnecessarily big because every now and then an Entity is deleted and removed from the map.

std::map<unsigned int,Entity*>::iterator it;
it = entitymap.find(EntityID);
if(it != entitymap.end())
{
    Entity *entity= it->second;
    entitymap.erase(it);
}
delete entity;

So I could have a map that holds these values;

1,2,4,8,10

In which case I'd like the next Entity to claim the ID 3.

Answer 1

Since the IDs are ordered numerically, you could walk through the entire map until you find a "hole":

unsigned int i = 1; // or whatever your smallest admissable key value is

for (auto it = m.cbegin(), end = m.cend();
                           it != end && i == it->first; ++it, ++i)
{ }

// now i is the next free index

This may take long if the map is large and the first hole is near the end. You could check first if the largest key value (given by m.crbegin()->first) is significantly larger than m.size() before embarking on this exploration.