使用C++的最近最少使用的缓存

Question

我正在尝试使用C++实现LRU Cache.我想知道实现它们的最佳设计是什么.我知道LRU应该提供find(),添加一个元素并删除一个元素.删除应删除LRU元素.实现此目的的最佳ADT是什么？例如:如果我使用带有元素的映射作为值和时间计数器作为键我可以在O(logn)时间内搜索,Inserting是O(n),删除是O(logn).

Answer 1

LRU缓存的一个主要问题是几乎没有"const"操作,大多数会改变底层表示(如果只是因为它们碰撞了访问的元素).

这当然非常不方便,因为它意味着它不是传统的STL容器,因此任何展示迭代器的想法都非常复杂:当迭代器被解除引用时,这是一个访问,它应该修改我们正在迭代的列表...天啊.

在速度和内存消耗方面都有性能考虑因素.

不幸的是,你需要一些方法来组织队列中的数据(LRU)(可以从中间删除元素),这意味着你的元素必须彼此独立.一std::list配合,当然,但它比你更需要.这里有一个单链表就足够了,因为你不需要向后迭代列表(毕竟你只想要一个队列).

然而,这些的一个主要缺点是它们的引用局部性较差,如果你需要更高的速度,你需要为节点提供自己的自定义(池？)分配器,以便它们尽可能保持紧密.这也将在一定程度上缓解堆碎片.

接下来,您显然需要一个索引结构(用于缓存位).最自然的是转向哈希映射.std::tr1::unordered_map,std::unordered_map或者boost::unordered_map通常是高质量的实施,有些应该可供您使用.他们还为哈希冲突处理分配额外的节点,您可能更喜欢其他类型的哈希映射,查看维基百科关于该主题的文章,并阅读各种实现技术的特征.

继续,有(明显的)线程支持.如果你不需要线程支持,那么没关系,如果你这样做,它会更复杂一些:

• 正如我所说,const这种结构几乎没有操作,因此您不需要区分读/写访问
• 内部锁定没问题,但您可能会发现它对您的使用不起作用.内部锁定的问题在于它不支持"事务"的概念,因为它放弃了每次调用之间的锁定.如果是这种情况,请将对象转换为互斥锁并提供std::unique_ptr<Lock> lock()方法(在调试中,您可以断言,而不是在每个方法的入口点处进行锁定)
• (在锁定策略中)存在重入问题,即从同一个线程中"重新锁定"互斥锁的能力,请查看Boost.Thread以获取有关各种锁和互斥锁的更多信息

最后,还有错误报告的问题.由于预计缓存可能无法检索您输入的数据,因此我会考虑使用"不良品味"的例外情况.考虑指针(Value*)或Boost.Optional(boost::optional<Value&>).我更喜欢Boost.Optional,因为它的语义清晰.

Answer 2

实现LRU的最佳方法是使用std :: list和stdext :: hash_map的组合(只想使用std然后std :: map).

• 将数据存储在列表中,以便最后使用最少的数据并使用地图指向列表项.
• 对于"get",使用map获取列表addr并检索数据并将当前节点移动到第
  一个节点(因为现在使用它)并更新地图.
• 对于"insert",从列表中删除最后一个元素,并将新数据添加到前面并更新地图.

这是你能得到的最快的,如果你使用的是hash_map,你几乎应该在O(1)中完成所有的操作.如果使用std :: map,它应该在所有情况下都需要O(logn).

这里有一个非常好的实现

Answer 3

这个文章描述了一种对夫妇C++ LRU缓存实现(使用一个STL,一个使用boost::bimap).