如何使用STL实现LFU缓存？

Question

我正在尝试使用纯STL（不想使用Boost！）实现LFU（最近最少使用）缓存。

要求如下：

• 使用类似于std::map的Key进行关联访问任何元素。
• 能够释放具有最低优先级（使用其UsesCount属性）的项目。
• 能够更新任何项目的优先级（UsesCount）。

问题如下：

• 如果我将std::vector用作项目（Key，Value，UsesCount）的容器，将std::map用作指向向量的迭代器的容器以进行关联访问，并将std::make_heap，std::push_heap和std::pop_heap用作向量内的优先级队列实现，则堆操作后地图中的迭代器无效。
• 如果在上述配置中使用std::list（或std::map）而不是std::vector，则由于它们的迭代器不支持算术运算，无法编译std::make_heap等操作。
• 如果我想使用std::priority_queue，则无法更新项目优先级。

问题如下：

• 我是否忽略了解决此问题的明显方法？
• 您能指向一些满足前面要求的LFU缓存的纯C++/STL实现作为示例吗？

感谢您的见解。

- Blackhex

---

在堆操作之后，映射中的迭代器将无效 - 通过反过来做 - 将数据放入map中，在即使插入/删除其他元素时也不会被移动。然后将映射迭代器放入您的向量中并构建一个堆。您可能仍然缺少高效更新项目优先级的能力，因此这不是一个答案。 - Steve Jessop

谢谢你提供了另一个我没有想到的想法。但是，如果我有一个std::vector的std::map迭代器，我该如何定义它们的比较运算符，以便在插入项目或更新UsesCount后查看指针对象内部的UsesCount属性，以便能够使用std::make_heap修复堆？ - Blackhex

使用类似以下的比较函数对象：bool operator()(MapIter a, MapIterB) { return a->second.UseCount < b->second.UseCount; } - Useless

只是有点追求严谨，你确定你不是指“最常用”（MFU）/“最近最少使用”（LRU）吗？为什么要缓存最不常用的东西呢？ - FrankH.

引用维基百科的话，“LFU计算一个项目被需要的频率。使用最少的项目首先被丢弃。”，这意味着这正是我想要的。 - Blackhex

@FrankH：LRU/MRU/LFU这些术语是指哪些项目被丢弃，而不是哪些项目被保留。LRU缓存会保留最新的项目并丢弃最旧的项目。 - Steve Jessop

Answer 1

你使用*_heap函数和向量实现看起来很合适，但会导致更新缓慢。你遇到的迭代器失效问题对于使用向量作为底层数据结构的每个容器都是正常的。这也是boost::heap::priority_queue采用的方法，但它不提供可变接口，原因如上所述。其他boost::heap data-structures提供了更新堆的能力。

有一些看起来有点奇怪的地方：即使你能使用std::priority_queue，你仍然会面临迭代器失效的问题。

直接回答你的问题：你没有错过任何明显的东西。std::priority_queue并不像它应该的那样有用。最好的方法是编写自己的堆实现以支持更新。要使其完全符合STL（特别是分配器感知）相当棘手，不是简单的任务。此外，实现LFU缓存。

首先，查看Boost实现以了解工作量。我不知道第二个步骤是否有任何参考实现。

为了解决迭代器失效的问题，您可以选择间接引用到另一个容器中，尽管您应该尽量避免这样做，因为它会增加额外的成本并且可能会变得非常混乱。

- pmr

---

你如何使用 *_heap 更新优先级？我认为这不仅仅是 priority_queue 无法完成此任务：标准堆函数也无法完成。因此，提问者需要一个不同的堆实现。但我可能是错的。 - Steve Jessop

@SteveJessop 可能我说错了，但是在更新优先级后再次调用make_heap应该可以修复堆。虽然这可能远非最优解。 - pmr

同意。这将恢复堆不变量，但它是O(n)的。其他堆实现可以在O(log n)中增加/减少/更新。 - Steve Jessop

@SteveJessop 我把这个添加到答案里，希望能够稍微改善一下。 - pmr

请注意，make_heap 只能在需要删除项目之前调用，而不能在每次更新/插入项目时调用。 - Blackhex

@Blackhex：make_heap 可以在每次更新时调用。它所做的只是重新排列您给定范围内的元素。没有必要在插入时调用它，因为 push_heap 可以有效地处理插入操作。 - Steve Jessop

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是适合您的缓存策略的原因，我对它的更改可能是错误的策略，或者仍然可以接受。

- Steve Jessop

---

@DeadMG：说得好，而且提问者指定了STL，所以肯定有一个可用的。在C++03中没有（没有Boost或TR1）。 - Steve Jessop