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

LRU缓存的一个主要问题是几乎没有“const”操作，大多数会改变底层表示（如果只是因为它们碰撞了访问的元素）。 这当然非常不方便，因为它意味着它不是传统的STL容器，因此任何展示迭代器的想法都非常复杂：当解除引用迭代器时，这是一个访问，它应该修改我们正在迭代的列表...天啊。 在速度和内存消耗方面都有性能考虑因素。 不幸的是，你需要一些方法来组织队列中的数据（LRU）（可以从中间删除元素），这意味着你的元素必须彼此独立。当然，Aѭ0适合，但它超出了你的需要。这里有一个单链表就足够了，因为你不需要向后迭代列表（毕竟你只想要一个队列）。 然而，这些的一个主要缺点是它们的引用局部性较差，如果你需要更高的速度，你需要为节点提供自己的自定义（池？）分配器，以便它们尽可能保持紧密。这也将在一定程度上缓解堆碎片。 接下来，您显然需要一个索引结构（用于缓存位）。最自然的是转向哈希映射。

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，因为它的语义清晰。     

实现LRU的最佳方法是使用std :: list和stdext :: hash_map的组合（只想使用std然后std :: map）。 将数据存储在列表中以便这样做 最近最少使用的 最后并使用地图指向 列出项目。 对于“获取”使用地图获取 列出addr并检索数据 并将当前节点移动到 首先（因为现在使用）并更新地图。 对于“插入”删除最后一个元素 从列表中添加新数据 到前面并更新地图。 这是你能得到的最快的，如果你使用的是hash_map，你几乎应该在O（1）中完成所有的操作。如果使用std :: map，它应该在所有情况下都需要O（logn）。 这里有一个非常好的实现     

本文介绍了几个C ++ LRU缓存实现（一个使用STL，一个使用

boost::bimap

）。     

当你说优先级时，我认为“堆”自然会导致增加键和删除最小值。     

如果我可以避免它，我根本不会让缓存对外界可见。我只有一个集合（无论如何）并且无形地处理缓存，根据需要添加和删除项目，但外部接口将完全是底层集合的接口。 就实现而言，堆可能是最明显的。它具有与地图大致相似的复杂性，但它不是从链接节点构建树，而是在数组中排列项，而“链接”是基于数组索引隐式的。这样可以提高缓存的存储密度，并改善“实际”（物理）处理器缓存中的位置。     

我建议一堆，也许是斐波纳契堆     

我会使用C ++中的普通堆。 使用std :: make_heap（标准保证为O（n）），std :: pop_heap和#include中的std :: push_heap，实现它绝对是蛋糕。你只需要担心增加密钥。