找到最小的未使用的数字

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

查找最低的未使用编号是 UNIX 内核中非常常见的操作，就像每个 open/socket/etc 一样。 系统调用应该绑定到最低的未使用的 FD 编号。

在 Linux 上，fs/file.c#alloc_fd 是：

• 跟踪 next_fd， 不一定 100% 准确
• 低水位线——每当释放 FD 时，
• ，next_fd = min(fd, next_fd)分配 FD，从 next_fd< 开始搜索位图/code> -- lib/find_next_bit.c#find_next_zero_bit 是线性的，但仍然非常快，因为它需要 BITS_PER_LONG< 一次跨步
• /code>分配 FD 后

，next_fd = fd + 1 FreeBSD 的 sys/kern/kern_descrip.c#fdalloc 遵循相同的想法：从 int fd_freefile 开始； /* 大约。 下一个空闲文件*/，并向上搜索位图。

---

然而，这些都是在以下假设下运行的：大多数进程只有很少的 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），

如果您的假设是已使用数字将是稀疏的，那么 Dmitry 的解决方案更有意义。

Answer 2

我会使用双向映射类来解决这个问题。 这样你就可以简单地检查值 1 是否存在等。

编辑

使用 bimap 的好处是已经存在它的强大实现，即使搜索下一个空闲号码的时间复杂度为 O(n)仅当 n 很大时（或者如果 n 适中且调用非常频繁），这才是问题。 总体而言，实现了一个简单的实现，不太容易出错且易于维护。

如果n很大或者此操作执行得非常频繁，那么投入精力实施更高级的解决方案是值得的。 恕我直言。

Answer 3

如果你的地图很大但稀疏，这

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] 范围内拥有一组免费项目。