我正在尝试使用 C++ 实现 LRU 缓存。我想知道实现它们的最佳设计是什么。我知道 LRU 应该提供 find()，添加一个元素和删除一个元素。 remove 应该移除 LRU 元素。什么是最好的 ADT 来实现这个 例如:如果我使用一个以元素作为值和时间计数器作为键的映射，我可以在 O(logn) 时间内搜索，插入是 O(n)，删除是 O(logn)。
最佳答案
LRU 缓存的一个主要问题是几乎没有“常量”操作，大多数操作会更改底层表示(如果仅仅是因为它们会影响访问的元素)。
这当然很不方便，因为这意味着它不是传统的 STL 容器，因此展示迭代器的任何想法都非常复杂:当迭代器被取消引用时，这是一个访问，它应该修改我们正在迭代的列表...哦，天哪。
还有性能方面的考虑，包括速度和内存消耗。
不幸的是，您需要某种方式在队列 (LRU) 中组织数据(可以从中间移除元素)，这意味着您的元素必须相互独立。 std::list当然适合，但超出您的需要。单链表在这里就足够了，因为您不需要向后迭代列表(毕竟您只需要一个队列)。
然而，这些的一个主要缺点是它们的引用位置很差，如果您需要更快的速度，您需要为节点提供自己的自定义(池？)分配器，以便它们尽可能靠近。这也将在一定程度上减轻堆碎片。
接下来，您显然需要一个索引结构(用于缓存位)。最自然的是转向 HashMap 。 std::tr1::unordered_map , std::unordered_map或 boost::unordered_map通常都是高质量的实现，有些应该可供您使用。他们还为哈希冲突处理分配了额外的节点，您可能更喜欢其他类型的 HashMap ，查看 Wikipedia's article了解该主题并了解各种实现技术的特点。
继续，有(明显的)线程支持。如果您不需要线程支持，那很好，但是如果您需要，那就有点复杂了:
- 正如我所说，很少有
const在这样的结构上操作，因此您实际上不需要区分读/写访问 - 内部锁定很好，但您可能会发现它不适合您的使用。内部锁定的问题在于它不支持“事务”的概念，因为它放弃了每次调用之间的锁定。如果是这种情况，请将您的对象转换为互斥锁并提供
std::unique_ptr<Lock> lock()方法(在调试中，你可以断言锁是在每个方法的入口点获取的) - 存在(在锁定策略中)重入问题，即从同一线程内“重新锁定”互斥量的能力，查看 Boost.Thread 以获取有关可用的各种锁和互斥量的更多信息
最后是报错问题。由于预计缓存可能无法检索您放入的数据，因此我会考虑使用异常“品味不佳”。考虑指针 ( Value* ) 或 Boost.Optional (boost::optional<Value&>)。我更喜欢 Boost.Optional，因为它的语义很清楚。
关于c++ - 使用 C++ 的最近最少使用缓存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3639744/