Find the lowest unused number

Question

I've setup a std map to map some numbers, at this point I know what numbers I'm mapping from an to, eg:

std::map<int, int> myMap;

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

Later however, I want to map some numbers to the lowest number possilbe that is not in the map, eg:

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

Any easy way of doing this?

I considered building an ordered list of numbers as I added them to the map so I could just look for 1, not find it, use it, add it etc.

Answer 1

I'd use a bidirectional map class for this problem. That way you can simply check if value 1 exists etc.

Edit

The benefits of using a bimap is that there already exist robust implementations of it and even if searching for the next free number is O(n) it is only an issue if n is large (or possibly if n is moderate and this is called very frequently). Overall making for a simple implementation that is unlikely to be error prone and easily maintainable.

If n is large or this operation is performed very frequently than investing the effort of implementing a more advanced solution is merited. IMHO.

Answer 2

Something like

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

If your map is quite big but sparse, this will work like o(log(N)), where N is the number of items in the map - in most cases you won't have to iterate through the set, or just make a few steps. Otherwise, if there are few gaps in the map, then you would better have a set of free items in the range [1..maxValueInTheMap].