获取地图中的第一个可用密钥

Question

我有一个地图,通过他们的ID存储指向对象的指针.

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

要为实体分配ID,我可以在entitymap中获取最新值并将其增加1.

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

但是这个数字可能变得不必要地大,因为一个实体会被删除并从地图中删除.

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

所以我可以拥有一个包含这些值的地图;

1,2,4,8,10

在这种情况下,我希望下一个实体申请该ID 3.

Answer 1

由于 ID 是按数字排序的，因此您可以遍历整个地图，直到找到一个“洞”：

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()开始此探索之前。