查找鏈接列表中的條目優於O（n）時間的索引

Question

我有一個場景，我正在將更改列表推送到另一個系統。每個列表包含零個或多個插入，更新或刪除的通知。

插入很容易;該通知包含目標索引和一個指向該項目的指針。更新很簡單;我傳遞一個指向該項目的指針。

刪除似乎很直接;我需要傳遞要刪除的項目的索引，但是如何知道索引？索引從零開始並且必須是連續的，但是我在插入時進行設置。所以我需要跟蹤每件商品的指數。

我可以做到這一點，例如，地圖：std::map<item*, int>，但是當我刪除一個項目時，我必須重新編號過去它的所有內容，這是O（N）。

這些項目列表將會大到O（N）迭代不可接受的程度。我確信這個問題已經解決，我只是不知道該解決方案將被稱爲什麼。搜索與「鏈表」相關的任何內容都會產生大量噪音。

一個可能的解決方案是跳過列表，其中子列表中的每個節點都知道它跳過的主列表中有多少個節點，並且由於搜索跳過列表是O（log N），所以我們可以繼續跟蹤找到O（log N）中的索引並刪除O（log N）中的項目。

然而，實施跳過列表似乎有點矯枉過正......有沒有更簡單的解決方案？

編輯：

感謝所有爲您的建議，但我想我已經說服自己跳躍列表是在這裏解決這個問題的正確方法。

Answer 1

跳躍列表是正確的解決方案。

Answer 2

參見Hinze和Paterson的Finger Trees: A Simple General-purpose Data Structure。

另請參見MarkCC的blog post on finger trees中的漂亮插圖。

Answer 3

編輯：我以前的解決方案有缺陷std :: vector :: erase（）在移動元素時是線性的。我的新建議將我先前的評論擴展到您的問題。

如果您只是使用列表中的指針，可以在對指針調用delete之後將指針設置爲0，並保持索引/鍵有效。那麼你應該可以使用越來越大的指數，直到下一個指數超過std::numeric_limits<int>::max()。 然後，當列表的大部分包含未使用的指針元素設置爲零時，執行通信通道兩側的零指針同步清除，然後重新計算索引。我不知道這個關於袖口的啓發式算法，但是您可以跟蹤零指針的數量，並將其與整個列表大小進行比較。

用較少的詞，因爲指數的計算是O（n），延遲它，直到你絕對必須。

Answer 4

當您在std::map<item*, int>中執行查找時，難道您不能保留刪除歷史並對此進行補償嗎？

我的意思是，在std::map該指數代表了項目的原始索引，然後你有一個輔助地圖std::map<int, int>存儲了多少次給定的指標已被刪除？

item* todelete; //from somewhere 
std::map<int, int> history; //stored somewhere 
std::map<item*, int> itemIndices; //stored somewhere 
const int originalIndex = itemIndices[todelete]; //index of item at insert time 
int index = originalIndex; 
for (std::map<int, int>::const_iterator it = history.begin(); it != history.end() && it->first < originalIndex; ++it) { 
    index -= it->second; 
} 
// index has now been compensated for previous deletes 
// ... send the delete request with 'index' 
// update the history with this delete request 
std::map<int, int>::iterator it = history.find(index); 
if (history.end() == it) { 
    history[index] = 1; 
} else { 
    ++it->second; 
} 

這當然的速度取決於歷史的大小。

/A.B。

Answer 5

多久會刪除發生？我想保持使用std::map<item*, int>您的解決方案，但不是更新後刪除該地圖用「NULL」代替鏈表的項目-Item以確保您的lookupmap指數仍然有效。這可能不是一個好的解決方案，如果你會看到經常刪除，並有可能會用完內存。此外，你可以做到這一點，並有一個reindex（） - 方法，從鏈表中刪除任何NULL項目，併爲所有項目分配新的索引。

旁註1： 你不能傳遞指針的項目，你在做更新被刪除？如果您這樣做並使用double-linked list，則可以在O（1）中輕鬆執行刪除操作。

旁註2： 考慮使用boost::unordered_map超過std::map。