C語言創建一個基於時間的地圖

Question

所以我必須從關鍵地圖 - >結構

我的重點將是設備的IP地址和值（結構）將舉行一個設備的IP地址和之後的時間這段時間已過，將使鍵值對過期並因此從地圖中刪除。

我對此很新，所以想知道什麼是一個好辦法。

我用Google搜索周圍，似乎找到了在基於Java的時間地圖很多隻

編輯

跨越this來後，我想我可能要創建一個有項目地圖，然後與每個元素的引用並行使用一個deque。然後定期打電話清理，如果它已經在那裏超過x時間刪除它。

這是否正確嗎？任何人都可以提出一個更優化的方法嗎？

Answer 1

我已經使用了三種方法來解決這樣的問題。

1. 使用週期性定時器。每次使用一次，獲得所有即將到期的元素並使其到期。將元素保留在計時器輪子中，請參閱scheme 7 in this paper for ideas.這裏的開銷是週期性計時器在無所事事時會啓動並且存儲桶具有恆定的內存開銷，但如果您添加和刪除內容，則這是最有效的事情從地圖上往往比你過期元素更多。

2. 檢查所有元素的最短過期時間。安排一個計時器在這段時間之後啓動。在計時器中，移除過期的元素並安排下一個計時器。如果過期時間短於當前計劃的計時器，則每次添加新元素時都重新計劃計時器。將元素保存在堆中，以便快速查找需要先到期的人員。這具有相當大的插入和刪除開銷，但在從地圖最常見的刪除到期時非常有效。

3. 每次訪問地圖時，檢查您訪問的元素是否已過期。如果是這樣，就把它扔掉，假裝它不在那裏。這可能是非常低效的，因爲所有調用都會檢查每個訪問的時間戳，並且如果需要在到期時執行某些操作，則不起作用。