前言LRUleast recently used最近最少使用缓存的规则很简单容量满了以后淘汰最久没有被访问过的条目。难的是让get和put都做到 O(1)——既要能在常数时间内找到键对应的值又要在常数时间内把某个条目移动到「最新」的位置还要在常数时间内找到「最旧」的条目。常见的错误实现有两类。一类用std::vector保存条目每次命中都把元素挪到前面单次操作退化成 O(n)另一类只用哈希表记录「最后一次访问时间」淘汰时扫描所有条目找最小值同样是 O(n)。这两类写法在数据量小时看不出问题压力一大就会成为瓶颈。正确的组合是哈希表加双向链表哈希表负责 O(1) 定位节点链表负责 O(1) 调整顺序和摘除尾部。std::list的splice可以在不搬动元素、不使迭代器失效的前提下把节点移到任意位置正好满足需求。本文实现一个泛型版本并说明几个容易写错的边界。示例以 C17 为准。一、数据结构的分工链表按访问时间排序头部是最近使用的尾部是最久未使用的。每个节点保存键值对。哈希表把键映射到链表节点的迭代器这样拿到键就能直接找到节点不需要遍历链表。为什么链表节点要同时保存键因为淘汰尾部节点时需要知道它的键才能把哈希表里对应的记录删掉。如果节点只存值删完链表就不知道要删哪个哈希项了。为什么用std::list而不是std::vector或std::deque因为std::list的插入、删除、splice都不会使其他节点的迭代器失效哈希表里保存的迭代器可以长期有效。std::vector一旦扩容所有迭代器失效即使不扩容中间插入也要搬移元素。std::deque的中间插入同样是线性代价。结构作用关键操作复杂度std::list维护访问顺序splice移到头部、pop_back淘汰O(1)std::unordered_map键到节点的映射find、erase、下标插入平均 O(1)节点中的键淘汰时反查哈希表读取firstO(1)二、get 与 put 的流程get(key)分两种情况。命中时通过哈希表拿到节点迭代器用splice把该节点移到链表头部然后返回它的值。未命中时返回空。put(key, value)也分两种情况。键已存在时更新节点的值并把它移到头部——这一步常被漏掉导致「更新」没有刷新访问顺序缓存会提前淘汰刚刚写过的条目。键不存在时在头部插入新节点在哈希表里登记迭代器如果此时链表长度超过容量就删除尾部节点并从哈希表中删掉它的键。哈希表里保存的迭代器在splice之后仍然有效这是整个设计能成立的前提。splice只改变节点之间的链接关系不重新分配节点也不改变节点地址所以迭代器继续指向同一个元素。容量为 0 的缓存没有意义任何put都会立刻触发淘汰get永远不命中。构造函数应当拒绝这种参数或者把容量 0 定义为「不缓存任何东西」并让put直接返回。本文选择抛异常让调用方尽早发现配置错误。三、完整示例// 适用于 C17#include cstddef#include iostream#include iterator#include list#include optional#include stdexcept#include string#include unordered_map#include utilitytemplate typename Key, typename Valueclass LruCache {public:explicit LruCache(std::size_t capacity) : capacity_(capacity) {if (capacity 0) {throw std::invalid_argument(capacity must be greater than zero);}}std::optionalValue 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::liststd::pairKey, Value items_;std::unordered_mapKey,typename std::liststd::pairKey, Value::iterator index_;};int main() {LruCacheint, 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::optionalValue值是按拷贝返回的。如果Value很大可以考虑返回const Value*或std::optionalstd::reference_wrapperconst 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::optionalValue get(const Key) const;内部却要splice修改链表编译失败。✅get不声明 const或者把链表和哈希表声明为mutable并说明这是逻辑只读。坑点八多线程直接共享同一个缓存。❌ 两个线程同时调用put链表指针和哈希表同时被改数据竞争。✅ 用std::mutex保护所有公开操作或按桶分片并处理全局容量。总结操作步骤复杂度get命中查表、splice到头部、返回值平均 O(1)get未命中查表失败、返回空平均 O(1)put已有键更新值、splice到头部平均 O(1)put新键头部插入、登记迭代器、必要时淘汰尾部平均 O(1)淘汰取尾部键、删哈希项、pop_back平均 O(1)LRU 的实现只有两个关键点用链表维护顺序、用哈希表定位节点并且让哈希表保存的迭代器在顺序调整后仍然有效。把「命中要提前」「淘汰要同步删表」「更新不等于插入」这三处处理对剩下就是模板和边界条件的工作。 
长河君 · 2026/11/2 11:21:54 · 阅读 1.2k C++实现LRU缓存的操作方法
前言LRUleast recently used最近最少使用缓存的规则很简单容量满了以后淘汰最久没有被访问过的条目。难的是让get和put都做到 O(1)——既要能在常数时间内找到键对应的值又要在常数时间内把某个条目移动到「最新」的位置还要在常数时间内找到「最旧」的条目。常见的错误实现有两类。一类用std::vector保存条目每次命中都把元素挪到前面单次操作退化成 O(n)另一类只用哈希表记录「最后一次访问时间」淘汰时扫描所有条目找最小值同样是 O(n)。这两类写法在数据量小时看不出问题压力一大就会成为瓶颈。正确的组合是哈希表加双向链表哈希表负责 O(1) 定位节点链表负责 O(1) 调整顺序和摘除尾部。std::list的splice可以在不搬动元素、不使迭代器失效的前提下把节点移到任意位置正好满足需求。本文实现一个泛型版本并说明几个容易写错的边界。示例以 C17 为准。一、数据结构的分工链表按访问时间排序头部是最近使用的尾部是最久未使用的。每个节点保存键值对。哈希表把键映射到链表节点的迭代器这样拿到键就能直接找到节点不需要遍历链表。为什么链表节点要同时保存键因为淘汰尾部节点时需要知道它的键才能把哈希表里对应的记录删掉。如果节点只存值删完链表就不知道要删哪个哈希项了。为什么用std::list而不是std::vector或std::deque因为std::list的插入、删除、splice都不会使其他节点的迭代器失效哈希表里保存的迭代器可以长期有效。std::vector一旦扩容所有迭代器失效即使不扩容中间插入也要搬移元素。std::deque的中间插入同样是线性代价。结构作用关键操作复杂度std::list维护访问顺序splice移到头部、pop_back淘汰O(1)std::unordered_map键到节点的映射find、erase、下标插入平均 O(1)节点中的键淘汰时反查哈希表读取firstO(1)二、get 与 put 的流程get(key)分两种情况。命中时通过哈希表拿到节点迭代器用splice把该节点移到链表头部然后返回它的值。未命中时返回空。put(key, value)也分两种情况。键已存在时更新节点的值并把它移到头部——这一步常被漏掉导致「更新」没有刷新访问顺序缓存会提前淘汰刚刚写过的条目。键不存在时在头部插入新节点在哈希表里登记迭代器如果此时链表长度超过容量就删除尾部节点并从哈希表中删掉它的键。哈希表里保存的迭代器在splice之后仍然有效这是整个设计能成立的前提。splice只改变节点之间的链接关系不重新分配节点也不改变节点地址所以迭代器继续指向同一个元素。容量为 0 的缓存没有意义任何put都会立刻触发淘汰get永远不命中。构造函数应当拒绝这种参数或者把容量 0 定义为「不缓存任何东西」并让put直接返回。本文选择抛异常让调用方尽早发现配置错误。三、完整示例// 适用于 C17#include cstddef#include iostream#include iterator#include list#include optional#include stdexcept#include string#include unordered_map#include utilitytemplate typename Key, typename Valueclass LruCache {public:explicit LruCache(std::size_t capacity) : capacity_(capacity) {if (capacity 0) {throw std::invalid_argument(capacity must be greater than zero);}}std::optionalValue 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::liststd::pairKey, Value items_;std::unordered_mapKey,typename std::liststd::pairKey, Value::iterator index_;};int main() {LruCacheint, 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::optionalValue值是按拷贝返回的。如果Value很大可以考虑返回const Value*或std::optionalstd::reference_wrapperconst 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::optionalValue get(const Key) const;内部却要splice修改链表编译失败。✅get不声明 const或者把链表和哈希表声明为mutable并说明这是逻辑只读。坑点八多线程直接共享同一个缓存。❌ 两个线程同时调用put链表指针和哈希表同时被改数据竞争。✅ 用std::mutex保护所有公开操作或按桶分片并处理全局容量。总结操作步骤复杂度get命中查表、splice到头部、返回值平均 O(1)get未命中查表失败、返回空平均 O(1)put已有键更新值、splice到头部平均 O(1)put新键头部插入、登记迭代器、必要时淘汰尾部平均 O(1)淘汰取尾部键、删哈希项、pop_back平均 O(1)LRU 的实现只有两个关键点用链表维护顺序、用哈希表定位节点并且让哈希表保存的迭代器在顺序调整后仍然有效。把「命中要提前」「淘汰要同步删表」「更新不等于插入」这三处处理对剩下就是模板和边界条件的工作。