找到最低的未使用的編號

我設置一個std地圖的一些數字地圖，在這一點上，我知道我是什麼數字從映射，如：找到最低的未使用的編號

然而

std::map<int, int> myMap; 

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

後來，我想將一些數字映射到不在地圖中的最低數目possilbe，例如：

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

要做到這一點的簡單方法是什麼？

我認爲門牌的有序列表，我將它們添加到地圖中，所以我可以只找1，找不到它，使用它，它添加等

來源

2009-06-11 CodeBuddy

我希望最低值是INT_MIN和INT_MIN + 1？如果它是一個映射 MSalters 2009-06-11 14:52:19

我會使用一個雙向映射類對於這個問題。這樣，你可以簡單地檢查是否值1存在等

編輯

使用bimap的是已經存在的它健壯實現即使尋找下一個免費電話號碼是O的好處（ n）這只是一個問題，如果n很大（或者如果n是中等的並且這被稱爲非常頻繁的話）。總體而言，這是一個簡單的實現，不太容易出錯並且易於維護。

如果n很大或者該操作執行得非常頻繁，這比投資實施更高級解決方案的努力是值得的。恕我直言。

來源

2009-06-11 10:30:58 Kris

這隱藏了算法......這是Q.哪個算法用於搜索該類上的鍵控項目？ – jpinto3912 2009-06-11 11:39:12

檢查是否存在值n以找到像O（n）練習那樣的最低可用聲音 – 2009-06-11 11:45:54

喜歡的東西

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（日誌（N）），其中N是在地圖的項目數 - 在大多數情況下，你贏了不必遍歷集合，或者只需幾步。否則，如果地圖中沒有空白，則最好在[1..maxValueInTheMap]範圍內有一組免費項目。

來源

2009-06-11 11:06:47

這是一種比乍一看更好的算法。請注意，儘管對GetNewNumber（）的*調用可能需要很多步驟，但freeCounter的* total *次數會增加（因此GetNewNumber（）的總運行時間除以set操作的對數因子）在地圖中分配的項目數量（因爲如果您分配了N個數字，則freeCounter≤N + 1）。因此，如果您已經分配了映射[N]，那麼到目前爲止對GetNewNumber（）的所有調用將僅取得O（N log N）時間：GetNewNumber爲O（log N）攤銷。 http://en.wikipedia.org/wiki/Amortized_analysis – ShreevatsaR 2009-06-11 13:50:41

查找最低的未使用數字是UNIX內核中非常常見的操作，因爲每個open/socket/etc。系統調用應該綁定到最低的未使用的FD號碼。

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

跟蹤 next_fd，低水位

- 它不一定100％準確
每當FD被釋放，next_fd = min(fd, next_fd)
分配一個FD，開始搜索從next_fd開始搜索位圖 - lib/find_next_bit.c#find_next_zero_bit是線性的，但仍然非常快，因爲它需要BITS_PER_LONG步幅
FD後分配泰德，next_fd = fd + 1

FreeBSD的sys/kern/kern_descrip.c#fdalloc遵循同樣的想法：用int fd_freefile; /* approx. next free file */開始，向上搜索位圖。

然而，這些所有的假設最過程有幾個文件描述符開放下運行，而且非常，非常少的有幾千。如果數字會更高，有稀疏洞，常見的解決方案（只要我見過）是

#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）

，如果你的假設是使用數字將是稀疏的，那麼梅德解決方案更有意義。

來源

2009-06-11 16:18:58 ephemient

找到最低的未使用的編號

回答

相關問題