哪些數據結構可以用來實現一個整數池？

這些整數可以是IP地址（DHCP）或會話ID或隧道ID（例如在L2TP中）。每個整數都可以是自由的或使用的。我們需要它有效地找到免費的。哪些數據結構可以用來實現一個整數池？

還有最小和最大定義。

2011-06-14 Plumenator

此問題與內存分配非常相似。您可能會在該問題域中找到一些答案。 – 2011-06-15 12:21:56

我明白你的意思了。如果我使用malloc，則每個字節的內存將對應於我的問題中的一個整數。對？ – Plumenator 2011-06-15 12:26:31

是的，確切地說。（如果你實現了「沒有人」的答案，你需要解決類似於內存碎片的問題） – 2011-06-15 12:28:57

好吧，你有一個最大和最小的我有以下想法：你動態地保持這個最大值或最小值和有一個免費整數列表。起初你從一個空的列表和全部範圍開始。當某人租用一個整數時，如果列表爲空，如果不是我們從列表中取出，則該範圍的大小會減少一個。如果他釋放他的整數有兩種可能性：

這應該讓您有可能以低成本維持高和低自由整數。當然，您也可以嘗試保存幾個範圍，將整數集中在一起，但這需要更復雜的操作。

2011-06-15 07:34:42 Nobody

我喜歡這一點。我的另一個想法是從一個範圍開始，一旦使用了整個範圍，就回到基於列表的機制。這只是最小化啓動成本。 – Plumenator 2011-06-15 10:58:22

對於多個範圍，我聽說這些範圍樹和間隔樹是好的嗎？我記得看到一個IP地址池的實現，他們使用了一些範圍的概念，但它絕對不是一棵樹（或是它？） – Plumenator 2011-06-15 10:59:34

抱歉，但我不知道那些樹。我的想法只是一些新鮮想法，我相信已經有一些解決方案，因爲DHCP服務器應該有效地進行編程（至少我希望如此）並解決同樣的問題。也許你也應該去看看，因爲我的想法不是「精心製作」 – Nobody 2011-06-15 21:02:11

你期望有更多的免費或更多使用的整數？你是否想要保存IP，SessIds和TunIds在同一時間或每個排除其他？

對我來說，最平衡的就是一棵樹，但正如你所知的最大尺寸，如果沒有頻繁的變化，一個數組就足夠了。

當你不關心某些命令，那麼動態列表將是最好的。

2011-06-14 11:23:23 Nobody

假設我只需要存儲一種'id'以簡化操作。我給出的各種例子都是假設的。如果您仍然好奇，我的使用案例是GTP隧道ID。我不能說我們是否會在特定時間有更多的免費或使用ID，但我們應該爲最壞的情況做好準備，這是全部使用。 – Plumenator 2011-06-14 15:40:00

我會保留一個空閒列表和一個使用的列表。分配一個數字意味着將它從空閒列表移動到使用的列表中，並且反向分配。

有將保持列出了成本，但找到一個免費電話號碼是快

2011-06-14 11:27:49 Alftheo

這就是我目前所做的。但是我最終在發佈時在列表中創建了2^24個節點。所以，內存使用情況是不變的，實際上是最糟糕的情況。 – Plumenator 2011-06-14 15:40:38

回答