前言

LRU（least recently used，最近最少使用）缓存的规则很简单：容量满了以后，淘汰最久没有被访问过的条目。难的是让get和put都做到 O(1)——既要能在常数时间内找到键对应的值，又要在常数时间内把某个条目移动到「最新」的位置，还要在常数时间内找到「最旧」的条目。

常见的错误实现有两类。一类用std::vector保存条目，每次命中都把元素挪到前面，单次操作退化成 O(n)；另一类只用哈希表记录「最后一次访问时间」，淘汰时扫描所有条目找最小值，同样是 O(n)。这两类写法在数据量小时看不出问题，压力一大就会成为瓶颈。

正确的组合是哈希表加双向链表：哈希表负责 O(1) 定位节点，链表负责 O(1) 调整顺序和摘除尾部。std::list的splice可以在不搬动元素、不使迭代器失效的前提下把节点移到任意位置，正好满足需求。本文实现一个泛型版本，并说明几个容易写错的边界。示例以 C++17 为准。

一、数据结构的分工

链表按访问时间排序：头部是最近使用的，尾部是最久未使用的。每个节点保存键值对。哈希表把键映射到链表节点的迭代器，这样拿到键就能直接找到节点，不需要遍历链表。

为什么链表节点要同时保存键？因为淘汰尾部节点时，需要知道它的键，才能把哈希表里对应的记录删掉。如果节点只存值，删完链表就不知道要删哪个哈希项了。

为什么用std::list而不是std::vector或std::deque？因为std::list的插入、删除、splice都不会使其他节点的迭代器失效，哈希表里保存的迭代器可以长期有效。std::vector一旦扩容，所有迭代器失效；即使不扩容，中间插入也要搬移元素。std::deque的中间插入同样是线性代价。

二、get 与 put 的流程

get(key)分两种情况。命中时，通过哈希表拿到节点迭代器，用splice把该节点移到链表头部，然后返回它的值。未命中时返回空。

put(key, value)也分两种情况。键已存在时，更新节点的值，并把它移到头部——这一步常被漏掉，导致「更新」没有刷新访问顺序，缓存会提前淘汰刚刚写过的条目。键不存在时，在头部插入新节点，在哈希表里登记迭代器；如果此时链表长度超过容量，就删除尾部节点，并从哈希表中删掉它的键。

哈希表里保存的迭代器在splice之后仍然有效，这是整个设计能成立的前提。splice只改变节点之间的链接关系，不重新分配节点，也不改变节点地址，所以迭代器继续指向同一个元素。

容量为 0 的缓存没有意义：任何put都会立刻触发淘汰，get永远不命中。构造函数应当拒绝这种参数，或者把容量 0 定义为「不缓存任何东西」并让put直接返回。本文选择抛异常，让调用方尽早发现配置错误。

三、完整示例

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <iterator>
#include <list>
#include <optional>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>

template <typename Key, typename Value>
class LruCache {
public:
explicit LruCache(std::size_t capacity) : capacity_(capacity) {
if (capacity == 0) {
throw std::invalid_argument("capacity must be greater than zero");
}
}

std::optional<Value> get(const Key& key) {
auto it = index_.find(key);
if (it == index_.end()) {
return std::nullopt;
}
// 命中：移到链表头部，表示最近使用
items_.splice(items_.begin(), items_, it->second);
return it->second->second;
}

void put(const Key& key, const Value& value) {
auto it = index_.find(key);
if (it != index_.end()) {
it->second->second = value;
items_.splice(items_.begin(), items_, it->second);
return;
}

items_.emplace_front(key, value);
index_[key] = items_.begin();

if (items_.size() > capacity_) {
auto last = std::prev(items_.end());
index_.erase(last->first); // 先按键删哈希项
items_.pop_back(); // 再摘除链表节点
}
}

std::size_t size() const noexcept { return items_.size(); }
std::size_t capacity() const noexcept { return capacity_; }

private:
std::size_t capacity_;
std::list<std::pair<Key, Value>> items_;
std::unordered_map<Key,
typename std::list<std::pair<Key, Value>>::iterator> index_;
};

int main() {
LruCache<int, std::string> cache(2);

cache.put(1, "one");
cache.put(2, "two");

std::cout << cache.get(1).value_or("miss") << '\n';
cache.put(3, "three");
std::cout << cache.get(2).value_or("miss") << '\n';

cache.put(1, "ONE");
std::cout << cache.get(1).value_or("miss") << '\n';
std::cout << cache.size() << '/' << cache.capacity() << '\n';
return 0;
}

按语义推演。容量为 2，先放入 1 和 2，链表从新到旧是 2、1。get(1)命中，1 被移到头部，顺序变成 1、2。接着put(3)，链表变为 3、1、2，长度超过 2，淘汰尾部 2，哈希表里也删掉 2。此时get(2)未命中。随后put(1, "ONE")命中的是已有键，更新值并把 1 移到头部，链表为 1、3，长度仍为 2。最终size()为 2。

这里有一个值得注意的细节：get返回的是std::optional<Value>，值是按拷贝返回的。如果Value很大，可以考虑返回const Value*或std::optional<std::reference_wrapper<const Value>>，但要提醒调用方引用会在条目被淘汰后失效。本文选择拷贝，换取更简单的生命周期。

index_[key] = items_.begin();使用了unordered_map::operator[]，键不存在时会插入一个默认构造的迭代器再赋值。由于前面已经用find确认键不存在，这里不会覆盖有效记录。如果在意多一次默认构造，可以改用insert或emplace。

四、线程安全与扩展

上面的实现不是线程安全的。两个线程同时put会同时修改链表和哈希表，数据竞争属于未定义行为。要在多线程环境使用，最直接的办法是在get和put外面加一把std::mutex，用std::lock_guard保护整个操作。锁的粒度是「整个缓存」，并发度有限但实现简单。

如果要提高并发度，可以按哈希分桶，每个桶一把锁，代价是容量淘汰变成全局问题：某个桶满了不代表全局满了，需要额外的全局计数和跨桶协调。这类设计容易出错，除非确有性能需求，否则不建议一开始就做。

其他变体包括 LFU（最少使用频率）、LRU-K（参考最近 K 次访问）、ARC（自适应替换），它们的核心结构仍然是哈希表加某种顺序容器，只是「谁该被淘汰」的判定更复杂。实现时应先保证语义正确，再考虑替换策略。

常见坑点

坑点一：用std::vector保存条目。

❌ 每次get命中都用erase加insert把元素挪到头部，单次操作 O(n)。

✅ 用std::list配合splice，移动节点不搬移元素，O(1)。

坑点二：命中后忘记调整顺序。

❌get只查表返回，不移动节点，缓存退化成先进先出。

✅ 命中后items_.splice(items_.begin(), items_, it->second);。

坑点三：更新已有键时当作新插入。

❌ 不先find就emplace_front，同一个键在链表里出现两次，哈希表只指向其中一个。

✅ 先判断键是否存在，存在则更新值并移到头部。

坑点四：淘汰时只摘链表，不删哈希表。

❌items_.pop_back();之后哈希表里还留着指向已销毁节点的迭代器，后续get访问悬垂迭代器。

✅ 先取尾部节点的键，index_.erase(key)，再pop_back。

坑点五：在vector上保存迭代器。

❌ 哈希表里存std::vector<...>::iterator，扩容后全部失效。

✅ 用std::list，其迭代器在插入、删除其他元素时保持有效。

坑点六：容量为 0 时行为未定义。

❌ 构造LruCache(0)后直接put，插入后立刻淘汰，逻辑混乱。

✅ 构造函数拒绝 0，或明确规定容量 0 时put为空操作。

坑点七：把get声明为 const。

❌std::optional<Value> get(const Key&) const;内部却要splice修改链表，编译失败。

✅get不声明 const，或者把链表和哈希表声明为mutable并说明这是逻辑只读。

坑点八：多线程直接共享同一个缓存。

❌ 两个线程同时调用put，链表指针和哈希表同时被改，数据竞争。

✅ 用std::mutex保护所有公开操作，或按桶分片并处理全局容量。

总结

LRU 的实现只有两个关键点：用链表维护顺序、用哈希表定位节点，并且让哈希表保存的迭代器在顺序调整后仍然有效。把「命中要提前」「淘汰要同步删表」「更新不等于插入」这三处处理对，剩下就是模板和边界条件的工作。