导读：缓存系统有一个绕不开的灵魂问题：容量满了，淘汰谁？LRU（Least Recently Used，最近最少使用）的答案是——淘汰最久没被访问的那个。听起来简单，但要在 O(1) 时间内完成"访问即更新""淘汰最旧"两个操作，需要精心设计数据结构。MiniKV 的 Store 类给出了教科书式的答案：std::list记录访问顺序、std::unordered_map存键值、Entry 内嵌 list 迭代器，三个结构协作实现 O(1) 的查询、插入与淘汰。本文逐行拆解这个经典组合，并回答一个关键问题：为什么必须是 list + map，vector 不行吗？

一、LRU 要解决什么问题

假设我们有一个容量为 2 的缓存，依次执行：

SET cold 1 → 缓存: [cold] SET hot 2 → 缓存: [hot, cold] （hot 最近，cold 次近） GET cold → 缓存: [cold, hot] （访问 cold，它变成最近！） SET new 3 → 容量满了！淘汰谁？ → 淘汰 hot（最久未用）

关键洞察：GET cold让 cold 从"次近"变成了"最近"——每一次访问都必须更新访问顺序。如果这个"更新"是 O(n) 的，那缓存越大越慢，性能无从谈起。所以 LRU 的实现核心是：

两个 O(1) 操作：访问时 O(1) 移到最前，淘汰时 O(1) 找到并删掉最旧。

二、数据结构：为什么是 list + map 组合

MiniKV 的 Store 类用三个结构协作：

// store.hclassStore{conststd::size_t capacity_;std::list<std::string>lru_;// ① 访问顺序链表std::unordered_map<std::string,Entry>entries_;// ② 键值哈希表structEntry{std::string value;std::optional<Clock::time_point>expires_at;// TTL（第 3 篇展开）std::list<std::string>::iterator lru_position;// ③ ⭐ 链表迭代器};};

三个结构的职责分工：

lru_position是整个设计的点睛之笔。它让"通过 key 找到 Entry"和"通过 Entry 找到链表位置"两个方向都变成 O(1)——不需要为了找链表位置而 O(n) 遍历链表。

三、O(1) 访问更新：splice 的妙用

每次 get/set 命中，都要把该 key 移到链表头部。MiniKV 的实现：

voidStore::touch_locked(Entry&entry){lru_.splice(lru_.begin(),lru_,entry.lru_position);entry.lru_position=lru_.begin();}

std::list::splice的语义是：把节点从当前链表剪切到目标位置——不复制、不移动数据，纯指针操作，O(1)。

为什么选splice而不是"删掉再插入"？因为 splice 有两个关键性质：

1. O(1)：直接操作节点指针，不遍历
2. 迭代器不失效：splice 保持元素的"身份"，entry.lru_position在剪切后仍然有效（指向同一个节点，只是位置变了）

这两点恰好是 LRU 频繁移动节点的刚需。

四、O(1) 淘汰：evict_if_needed_locked

容量超限时的淘汰逻辑：

voidStore::evict_if_needed_locked(){while(entries_.size()>capacity_){conststd::string victim=lru_.back();// 最久未用的 key（链表尾部）lru_.pop_back();entries_.erase(victim);++stats_.evictions;}}

• lru_.back()：链表尾部就是最久未用的 key——O(1) 拿到
• pop_back()+entries_.erase(victim)：链表和哈希表同步删除——都是 O(1)
• 注意是while而不是if：正常情况下每次 set 只多 1 个键，if就够；但极端情况（如构造后容量被调小）可能一次需要淘汰多个，while保证彻底清到容量内

五、set 与 get 的完整流程

set：三种情况

voidStore::set(std::string key,std::string value){std::lock_guard<std::mutex>lock(mutex_);// 线程安全（第4篇展开）remove_if_expired_locked(key);// TTL 惰性清理（第3篇）constautofound=entries_.find(key);if(found!=entries_.end()){// ① 已存在：更新found->second.value=std::move(value);found->second.expires_at.reset();// 重置 TTLtouch_locked(found->second);// 移到链表头return;}lru_.push_front(key);// ② 新 key：链表头插入entries_.emplace(std::move(key),Entry{std::move(value),std::nullopt,lru_.begin()});evict_if_needed_locked();// ③ 超容量：淘汰最旧}

注意entries_.emplace(..., lru_.begin())——新 Entry 的lru_position初始化为链表头迭代器（因为 push_front 刚把它放到了头部）。

get：命中即 touch

std::optional<std::string>Store::get(conststd::string&key){std::lock_guard<std::mutex>lock(mutex_);if(remove_if_expired_locked(key)){++stats_.misses;returnstd::nullopt;}constautofound=entries_.find(key);if(found==entries_.end()){++stats_.misses;returnstd::nullopt;}++stats_.hits;touch_locked(found->second);// ⭐ 访问即更新 LRU 位置returnfound->second.value;}

touch_locked在 get 里是关键——读取本身就会改变访问顺序，这正是 LRU 与 FIFO 的本质区别。

六、为什么是 list，不是 vector？

这是面试必考题，也是理解 LRU 实现的关键：

LRU 的核心操作是"把链表中间的节点移到头部"——如果lru_position存的是 vector 的迭代器（下标），每次移动后 vector 里其他元素的迭代器可能全部失效，lru_position就全错了。list 的迭代器稳定性 + splice 的 O(1) 剪切，是 LRU 选择 list 的根本原因。

七、测试验证：StoreEvictsLeastRecentlyUsed

MiniKV 自带的单元测试验证了完整逻辑（tests/store_test.cpp）：

TEST(StoreEvictsLeastRecentlyUsed){minikv::Storestore(2);// 容量 2store.set("cold","1");// lru: [cold]store.set("hot","2");// lru: [hot, cold]store.get("cold");// touch → lru: [cold, hot]（cold 变最近！）store.set("new","3");// 超容量 → 淘汰 hot（最久未用）EXPECT_TRUE(store.exists("cold"));// cold 存活（刚被访问过）✓EXPECT_FALSE(store.exists("hot"));// hot 被淘汰 ✓EXPECT_TRUE(store.exists("new"));// new 已加入 ✓EXPECT_EQ(store.stats().evictions,std::uint64_t{1});}

这个测试完美演示了 LRU 的核心语义：get("cold")改变了淘汰对象——如果淘汰规则是 FIFO，淘汰的会是 cold；但因为 LRU 记住了 cold 刚被访问，淘汰的是 hot。

小结

• LRU 的核心需求：访问时 O(1) 更新顺序，淘汰时 O(1) 找到最旧
• list + map 组合：list 记访问顺序（头=最近，尾=最旧），map 按 key O(1) 查 Entry
• lru_position点睛：Entry 内嵌 list 迭代器，让"key→链表位置"双向 O(1)
• splice 妙用：O(1) 剪切节点且迭代器不失效，是"移到头部"的正确工具
• while 而非 if：淘汰逻辑要考虑一次淘汰多个的极端情况
• list vs vector：迭代器稳定性 + splice，是 LRU 选 list 的根本原因

下一篇预告

《TTL 过期机制：惰性删除的取舍》——Entry 里那个expires_at时间戳，是 TTL（过期时间）的核心。MiniKV 采用"惰性删除"策略：不主动扫描过期键，而是在每次操作时顺手检查。这篇讲清楚惰性删除的原理、六条命令如何统一调用remove_if_expired_locked、以及它和 LRU 淘汰如何协作。

参考文献与引用

• cppreference - std::list::splice：en.cppreference.com/w/cpp/container/list/splice——splice 的 O(1) 剪切与迭代器不失效的权威说明
• cppreference - std::list：en.cppreference.com/w/cpp/container/list——list 迭代器稳定性保证

📥下载完整源码：如需整个工程的源码，请在下面的链接下载：
https://download.csdn.net/download/ganxin7932508/93241722

觉得有用？点个关注，持续获取 C++ 与系统编程技术干货。