Get the first available key on the map

Question

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

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

To assign an identifier to an object, I could just take the newest value in the entitymap file and increment 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 can become unnecessarily large, because from time to time the Essence is deleted and removed from the card.

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 containing these values;

1,2,4,8,10

In this case, I would like the next Entity to request an identifier 3.

Answer 1

Since the identifiers are numerically ordered, you can go 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

, , . , ( m.crbegin()->first) , m.size(), .

Answer 2

, , , . , , , Kerrek SB.

class {
...
    static int g_smallest_free_id; // init to 1
...
};

void delete_id()
{
    if(m_id < g_smallest_free_id) {
        m_id = g_smallest_free_id;
    }
}

void new_id()
{
    int id = g_smallest_free_id;
    // the -1 is because it looks like you start your ids at 1
    // since we skip all the known identifiers before id,
    // the loop is reduced from the current id to the next only
    for(interator it = list.begin() + id - 1;
                  it != list.end(); ++it) {
         // find next available id
    }
}

, , ( .)

, . , . , ... (, , .)

Answer 3

Heap . , , , , , . - O (log n). , node .

, , , .

Answer 4

, , , :

typedef std::map<Key, Value> Table;

std::optional<Key> findFirstFreeSlot(const Key& start, const Key& end, const Table& table)
{
  for (Key i = start; i <= end; i++) {
    if (table.find(i) == table.end()) {
        return i;
    }
  }
  return std::none;
}