c++ - C++ 中的 LRU 缓存

Question

可能重复：
LRU 缓存设计

我在一次编程面试中得到了这个问题。随意考虑如何回答它。

您将如何在 C++ 中实现 LRU（最近最少更新）缓存？基本上，缓存可以容纳N项目。如果插入了一个新项目并且缓存中的项目数小于N，则它只是插入。但是如果插入了一个新项目并且缓存中的项目数已经是N，那么最近最少使用的项目应该从缓存中删除。

考虑一下您的每项操作需要多少运行时间。

Answer 1

我将拥有存储上次访问时间的缓存元素的成员。当元素被访问（成员函数被调用）时，访问时间成员被更新。当缓存变满时，访问时间最短的元素将被删除。

其他选择是在intrusive list中有缓存元素。当某些东西被访问并且不在列表顶部时，它会出现在列表顶部。当缓存已满时，列表的底部元素被擦除。每次访问都需要做更多的工作，但可以更快地找到受害者。

基本思想是不要为此类任务提供典型的地图和列表，这些会分散你的记忆。我的算法将缓存始终保持在一个地方。