Поиск недостающих ключей в QMap

Question

У меня есть qmap из <int , Myclass*>

Ключ имеет диапазон от 1 до n_max.

Когда я вставляю в карту, мне нужно знать наименьший из доступных неиспользованных ключей.

Например, если карта содержит

<1, obj1>

<3, obj3>

Когда я вставляю свой следующий элемент в карту, я бы хотел, чтобы ключ был 2

Какой самый эффективный способ сделать это

Привет

Answer 1

Возможно, вы захотите сделать несколько вещей, чтобы оптимизировать поиск.

Сначала проверьте count() на предмет чего-то вроде предыдущей записи map.end () (т. Е. -). Если они одинаковые, вы знаете, что они заполнены и могут быть добавлены в конце.

Если это не так (значение конечного итератора больше, чем count()), то вы знаете, что вам нужно искать дыру. При поиске целого, вы, вероятно, захотите извлечь все uniqueKeys(), а затем начните поиск с середины, чтобы увидеть, соответствует ли средний ключ предыдущему count()/2 или около того. Если нет, то идите вниз еще на count()/4, иначе поднимитесь на count()/4. Повторяйте, пока не найдете то, что ищете.

Но на самом деле, я не уверен, что карта - это правильный контейнер. Похоже, вам нужен массив или связанный список или ... это зависит от ваших данных. Но если вам нужно выполнить вышеуказанную операцию с картой, я предлагаю вам, вероятно, найти правильный контейнер.

Answer 2

Поскольку QMap хранит элементы, отсортированные по ключу, вы можете использовать алгоритм adj_find из стандартной библиотеки c ++:

#include <QMap>
#include <algorithm>

bool missing (int i, int j) {
  return (i+1 < j);
}

int next_key(const QMap<int,int>& map) {
  if (!map.size()) 
    return 1; // or 0, if an acceptable key value

  QList<int>::iterator i = std::adjacent_find(map.keys().begin(), map.keys().end(), missing);

  if (i==map.keys().end()) // no missing values found
    --i; 

  return *i + 1;
}

Сложность ровно меньше (результат - первый) + 1 и (последний - первый) - 1 применения предиката («отсутствующая» функция), где результат - возвращаемое значение.