Найти самый низкий неиспользованный номер

Question

Я настроил стандартную карту для отображения некоторых чисел, на данный момент я знаю, какие числа я сопоставляю с, например:

std::map<int, int> myMap;

map[1] = 2;
map[2] = 4;
map[3] = 6;

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

map[4] = getLowestFreeNumberToMapTo(map); // I'd like this to return 1
map[5] = getLowestFreeNumberToMapTo(map); // I'd like this to return 3

Есть ли простой способ сделать это?

Я подумал о создании упорядоченного списка чисел, когда добавил их на карту, чтобы я мог просто найти 1, не найти его, использовать, добавить и т. Д.

Answer 1

Что-то вроде

typedef std::set<int> SetType;
SetType used;           // The already used numbers
int freeCounter = 1;    // The first available free number

void AddToMap(int i)
{
    used.insert(i);
    // Actually add the value to map
}

void GetNewNumber()
{
    SetType::iterator iter = used.lower_bound(freeCounter);
    while (iter != used.end() && *iter == freeCounter)
    {
        ++iter;
        ++freeCounter;
    }
    return freeCounter++;
}

Если ваша карта довольно большая, но разреженная, она будет работать как o (log (N)), где N - количество элементов на карте - в большинстве случаев вам не придется перебирать набор, или просто сделайте несколько шагов. В противном случае, если на карте мало гапсов, вам лучше иметь набор бесплатных элементов в диапазоне [1..maxValueInTheMap].

Answer 2

Поиск наименьшего неиспользуемого числа является очень распространенной операцией в ядрах UNIX, как и каждое open / socket / etc. Предполагается, что syscall связывается с самым низким неиспользуемым номером FD.

В Linux алгоритм в fs/file.c & shy; # alloc_fd:

• отслеживайте next_fd, низкий уровень воды - это не обязательно 100% точность
• всякий раз, когда освобождается ФД, next_fd = min(fd, next_fd)
• чтобы выделить FD, начните поиск растрового изображения, начиная с next_fd - lib/find_next_bit.c & shy; # find_next_zero_bit линейно, но все еще очень быстро, потому что требуется BITS_PER_LONG шагов по время
• после выделения FD, next_fd = fd + 1

FreeBSD sys/kern/kern_descrip.c & shy; # fdalloc следует той же идее: начните с int fd_freefile; /* approx. next free file */ и ищите растровое изображение вверх.

---

Однако все они работают в предположении, что в большинстве процессов открыто мало FD, а в очень, очень немногих - тысячи. Если числа будут намного выше, с редкими дырками, общее решение (насколько я видел) будет

#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

int high_water_mark = 0;
vector<int> unused_numbers = vector<int>();

int get_new_number() {
    if (used_numbers.empty())
        return high_water_mark++;
    pop_heap(unused_numbers.begin(), unused_numbers.end(), greater<int>());
    return unused_numbers.pop_back();
}

void recycle_number(int number) {
    unused_numbers.push_back(number);
    push_heap(unused_numbers.begin(), unused_numbers.end(), greater<int>());
}

(непроверенный код ... идея такова: удерживайте отметку уровня воды; попытайтесь украсть отметку unused ниже отметки уровня воды или иным способом - отметку уровня воды выше; верните значение unused)

и если вы предполагаете, что используемые числа будут редкими, то решение Дмитрия имеет больше смысла.

Answer 3

Я бы использовал класс двунаправленной карты для этой задачи. Таким образом, вы можете просто проверить, существует ли значение 1 и т. Д.

Редактировать

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

Если n велико или эта операция выполняется очень часто, чем стоит затратить усилия на внедрение более продвинутого решения. ИМХО.