LRU缓存在C++

Question

可能重复：
LRU cache design

我在编程这个问题采访。随时考虑如何回答它。

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

想想你的每项操作需要多少运行时间。

Answer 1

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

其他选项是在intrusive list中有缓存元素。当某些东西被访问并且不在列表的顶部时，它将列在最上面。缓存满时，列表的底部元素将被删除。每次访问都有更多的工作，但受害者更快找到。

基本的想法是不要有这样的任务典型的地图和列表，这些会碎片你的记忆。我的算法一直在一个地方保持缓存。