Получить первый доступный ключ на карте

Question

У меня есть карта, в которой указатели на объект хранятся по их идентификатору.

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

Чтобы присвоить идентификатор сущности, я мог бы просто взять новейшее значение в 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

В таком случае я бы хотел, чтобы следующая организация потребовала идентификатор 3.

Answer 1

Поскольку идентификаторы упорядочены по номерам, вы можете пройти по всей карте, пока не найдете «дыру»:

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

Это потенциально медленно, в зависимости от плотности вашей карты, но довольно легко понять:

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;
}

Answer 3

Вы можете хранить кучу всех освобожденных ключей. Каждый раз, когда вы освобождаете ключ, вы добавляете его в кучу, и каждый раз, когда вы используете ключ, вы удаляете его из кучи. Обе эти операции являются O (log n). Вы должны создать кучу, чтобы корневой узел имел наименьший ключ.

Если куча пуста, вы просто выделяете новый ключ, увеличивая предыдущий наибольший ключ, как обычно.

Answer 4

Предполагая, что список не очень сильно увеличивается, вы можете сохранить хотя бы наименьший из выпущенных идентификаторов. Затем при повторном использовании найдите следующий доступный идентификатор, упомянутый 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
    }
}

Это псевдокод, показывающий, что наименьшим свободным идентификатором должна быть статическая переменная в вашем классе (общая для всех экземпляров).

Как уже упоминалось в комментарии, вы можете использовать вектор. Хотя это не будет отсортировано, вы все равно не будете увеличивать идентификаторы бесконечно. Единственным недостатком вектора является то, что вы используете немного памяти ... (много, если вы имеете дело со многими объектами, но также и с картой).