找到最低的未使用数字

Question

我已经设置了一个std地图来映射一些数字,此时我知道我从一个数字映射到的数字,例如:

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