Find the lowest unused number

Question

I set the std card to display some numbers, at this point I know which numbers I map to, for example:

std::map<int, int> myMap;

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

Later, however, I want to match some numbers with the lowest number that is possibly not on the map, for example:

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 to do this?

I was thinking of creating an ordered list of numbers when I added them to the map so that I could just search for 1 and not find it, use it, add it, etc.

Answer 1

Sort of

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%
• , FD , 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 ..

Edit

, , - O (n), , n (, , n , ). , , .

n , . .