如何使用STL實現LFU緩存？

Question

我正在嘗試使用純STL實現LFU（Least Frequently Used）緩存（我不想使用Boost！）。

要求是：

• 到任何元件關聯的訪問使用Key像std::map。
• 能夠釋放最低優先級項目（使用其UsesCount屬性）。
• 能夠更新任何項目的優先級（UsesCount）。

的問題是：

• 如果我使用std::vector作爲std::map項的容器（Key，Value，UsesCount），作爲迭代器的用於關聯存取和std::make_heap，std::push_heap和std::pop_heap該載體的容器作爲向量中的優先級隊列實現，映射中的迭代器在堆操作後無效。
• 如果我在前面的配置中使用std::list（或std::map）而不是std::vector，則std::make_heap等無法編譯，因爲它們的迭代器不支持aritmetic。
• 如果我想使用std::priority_queue，我無法更新項目優先級。

的問題是：

• 我失去了一些東西很明顯這個問題如何解決？
• 你能指點我一些滿足以前需求的LFU緩存的純C++/STL實現嗎？

謝謝你的見解。

Answer 1

使用*_heap函數和向量來製作實現似乎非常合適。儘管它會導致更新緩慢。對於使用向量作爲底層數據結構的每個容器，遇到的有關迭代器失效的問題都是正常的。這也是boost::heap::priority_queue採用的方法，但由於上述原因，它不提供可變接口。其他boost::heap data-structures提供更新堆的能力。

一些看起來有點奇怪的事情：即使你能夠使用std::priority_queue，你仍然會面臨迭代器失效問題。

直接回答你的問題：你不會錯過一些明顯的東西。 std::priority_queue不如它應該是有用的。最好的方法是編寫自己的支持更新的堆實現。爲了完全兼容STL（尤其是分配器感知）是相當棘手的，而不是一個簡單的任務。最重要的是，實現LFU緩存。

第一步，查看Boost實現以瞭解該工作。我不知道第二個參考實現。

要解決迭代器失效問題，您可以隨時選擇間接到另一個容器中，儘管您應該儘量避免它，因爲它會產生額外的成本，並且可能會變得非常混亂。

Answer 2

一個稍微簡單不是保持兩個數據結構的方法：

• 只是不停地在地圖上，您的鍵映射到自己的價值/使用計數對。
• 當緩存滿：
• • 創建迭代的向量到映射的元素（O(n)）
• • 使用std::nth_element找到最差的10％（O(n)）
• • 將它們全部從地圖中刪除（O(n log n)）

因此，增加了高速緩存中的新元素是常見的情況O(log n)，最壞的情況下O(n log n)和攤銷O(log n)。

在LFU緩存中去除最糟糕的10％可能有點激烈，因爲新條目必須達到最高90％，或者它們被削減。再次，如果你只刪除一個元素，那麼新的條目仍然需要在下一個新條目之前脫離底部，否則它們被切斷，並且他們沒有時間這樣做。所以，根據LFU爲什麼適合您的緩存策略，我對它的改變可能是錯誤的策略，或者它可能還是很好的。