如何使用STL实现LFU缓存？

Question

我正在尝试使用纯STL实现LFU(最不常用)缓存(我不想使用Boost!).

要求是:

• 使用Key类似的关联访问任何元素std::map.
• 能够释放最低优先级的项目(使用其UsesCount属性).
• 能够更新UsesCount任何项目的priority().

问题是:

• 如果我使用std::vector的物品(集装箱Key,Value,UsesCount),std::map迭代器来为关联访问和向量的容器std::make_heap,std::push_heap并std::pop_heap为载体中的优先级队列的实现,在地图的itertors不是堆操作才有效.
• 如果我使用std::list(或std::map)代替std::vector以前的配置,std::make_heap则无法编译等因为它们的迭代器不支持aritmetic.
• 如果我想使用std::priority_queue,我没有能力更新项目优先级.

问题是:

• 我错过了一些明显可以解决这个问题的方法吗？
• 您能否指出一些符合以前要求的LFU缓存的纯C++/STL实现？

感谢您的见解.

Answer 1

您使用函数和向量的 make 实现*_heap似乎很合适。尽管这会导致更新缓慢。对于使用向量作为底层数据结构的每个容器来说，您遇到的迭代器失效问题是很常见的。boost::heap::priority_queue也采用了这种方法，但由于上述原因，它没有提供可变接口。其他boost::heap 数据结构提供了更新堆的能力。

看起来有点奇怪的事情：即使您能够使用，std::priority_queue您仍然会面临迭代器失效问题。

直接回答你的问题：你并没有错过一些明显的事情。std::priority_queue没有应有的有用。最好的方法是编写您自己的支持更新的堆实现。要使其完全兼容 STL（尤其是分配器感知）是相当棘手的，而且不是一个简单的任务。最重要的是，实现 LFU 缓存。

第一步，查看 Boost 实现以了解工作量。我不知道第二个的任何参考实现。

要解决迭代器失效问题，您始终可以选择间接进入另一个容器，尽管您应该尽量避免它，因为它会产生额外的成本并且可能会变得非常混乱。