Trouver le plus petit numéro utilisé

Question

J'ai installé une carte std à la carte quelques chiffres, à ce stade, je sais ce que je suis chiffres d'une cartographie à, par exemple:

std::map<int, int> myMap; 

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

Plus tard cependant, je veux Mapper certains nombres au nombre le plus bas possilbe qui n'est pas dans la carte, par exemple:

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

Une manière simple de faire cela?

je considérais la construction d'une liste ordonnée des numéros que je les ai ajoutés à la carte pour que je puisse simplement chercher 1, trouver pas, utilisez-le, ajoutez etc.

Answer 1

j'utiliser une classe carte bidirectionnelle pour ce problème. De cette façon, vous pouvez simplement vérifier si la valeur 1 existe, etc.

Modifier

Les avantages de l'utilisation d'un bimap est qu'il existe déjà des implémentations robustes et de même si la recherche du prochain numéro gratuit est O (n) c'est seulement un problème si n est grand (ou peut-être si n est modéré et cela s'appelle très fréquemment). Fabrication globale pour une implémentation simple qui est peu susceptible d'être sujette aux erreurs et facilement maintenable.

Si n est grand ou cette opération est effectuée très fréquemment que d'investir l'effort de mettre en œuvre une solution plus avancée est méritée. A MON HUMBLE AVIS.

Answer 2

Quelque chose comme

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

Si votre carte est assez grande, mais rares, cela fonctionnera comme o (log (N)), où N est le nombre d'éléments dans la carte - dans la plupart des cas vous avez gagné Pas besoin de parcourir l'ensemble, ou juste faire quelques pas. Sinon, s'il y a quelques espaces dans la carte, alors vous devriez avoir un ensemble d'éléments libres dans la plage [1..maxValueInTheMap].

Answer 3

La recherche du numéro inutilisé le plus bas est une opération très courante dans les noyaux UNIX, comme tous les open/socket/etc. syscall est supposé se lier au plus bas numéro FD non utilisé.

Sous Linux, l'algorithme fs/file.c­#alloc_fd est:

• piste donjon next_fd, une laisse de basse mer - il est pas nécessairement précis à 100%
• chaque fois qu'un FD est libéré, next_fd = min(fd, next_fd)
• pour allouer un FD, commencer à chercher le bitmap à partir de next_fd - lib/find_next_bit.c­#find_next_zero_bit est linéaire mais toujours très rapide, car il faut BITS_PER_LONG pas à la fois
• après un FD est alloca ted, next_fd = fd + 1

sys/kern/kern_descrip.c­#fdalloc de FreeBSD suit la même idée: commencer par int fd_freefile; /* approx. next free file */ et rechercher le bitmap vers le haut.

---

Cependant, ceux-ci fonctionnent tous sous l'hypothèse que la plupart processus ont peu FDs ouverts, et très, très peu ont des milliers. Si les chiffres vont aller beaucoup plus haut, avec des trous rares, la solution commune (pour autant que je l'ai vu) est

#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>()); 
} 

(code non testé ... L'idée est: garder une marque d'eau élevée, essayez de voler de unused sous la barre des hautes eaux, ou la laisse de haute mer sinon, le retour libéré à unused)

et si votre hypothèse est que les utilisés numéros seront rares, alors la solution de Dmitry plus de sens.