可能重复: LRU缓存设计
我在一次节目面试中问到了这个问题。你可以自由地想一想你会怎么回答。
如何在C++中实现LRU (最近更新最少的)缓存?基本上,缓存可以支持N项。如果插入了一个新项,并且缓存中的项数小于N,那么它就是插入的。但是,如果插入了一个新项,并且缓存中的项目数已经是N,那么最近使用最少的项应该从缓存中删除。
考虑一下每一次操作所需的运行时间。
发布于 2012-10-27 23:10:30
我会有一个缓存元素的成员来存储最后的访问时间。当访问元素时(调用成员函数),则更新访问时间成员。当缓存满时,访问时间最小的元素将被擦除。
其他选项是在侵入列表中有缓存元素。当某些东西被访问而不是在列表的顶部时,它就出现在列表的顶端。当缓存已满时,列表的底部元素将被删除。每次访问都要做更多的工作,但受害者更快找到。
基本的想法是不要有典型的地图和清单来完成这样的任务,这些都会使你的记忆分崩离析。我的算法总是把缓存放在一个地方。
https://stackoverflow.com/questions/13104951
复制相似问题