应使用 std::list 而非手写双向链表：它提供o(1)插入删除、迭代器稳定、避免裸指针生命周期问题；配合unordered_map实现lru时，需用splice()移动节点、严格按“删map再删list”顺序清理、自定义key须特化hash。
为什么用 std::list 而不是手写双向链表
直接复用 std::list 是最稳妥的选择：它保证节点插入/删除 O(1)，迭代器不因其他操作失效，且避免裸指针管理生命周期的坑。手写链表在 C++ 里除非有极致内存控制需求（比如对象池+自定义 allocator），否则纯属增加崩溃概率——尤其当缓存项是临时构造、移动语义介入时，next/prev 指针极易悬空。
关键点：std::list 的迭代器可长期持有，正好用来作为 unordered_map 的 value，实现 O(1) 定位链表节点：
std::unordered_map<key std::list>::iterator> cache_map;</key>
get() 和 put() 必须统一处理“访问即置顶”逻辑
LRU 的核心不是“淘汰最老”，而是“每次命中就把节点移到链表头”。很多初版实现把 get() 做成只读，结果缓存项永远卡在尾部，刚放进去就可能被踢——这不是 LRU，是 FIFO。
实操建议：
-
get()查到后，用splice()把对应节点移到list开头，再返回值 -
put()若 key 已存在，同样先splice()到开头，再更新 value；若不存在，插入新节点前先检查容量，超限则删list尾部节点，并从unordered_map中 erase 对应 key - 别用
list::push_front() + list::erase()模拟移动——这会触发两次内存操作；splice()是零拷贝搬运
unordered_map 的 key 类型必须支持哈希和等价比较
如果用自定义类型（比如 struct Key { int a; std::string b; };）作 key，编译会直接报错，提示 missing std::hash<key></key> 或 operator==。不能靠“我重载了 == 就行”——unordered_map 内部需要显式哈希函数。
快速修复方式：
- 为结构体特化
std::hash，用std::hash<int>{}(a) ^ (std::hash<:string>{}(b) 混合（注意左移防碰撞）</:string></int> - 或改用
std::map（O(log n) 查找），适合 key 复杂但缓存规模小的场景 - 更推荐：把 key 转成
std::string或size_t再存，省去模板特化麻烦
容量变更时别漏掉 unordered_map 的清理
这是最容易被忽略的崩点：删 list 尾部节点后，如果忘记从 unordered_map 中 erase() 对应 key，下次 get() 会拿到已销毁节点的迭代器，解引用直接 UB（通常 crash）。
正确顺序只能是：
- 从
list尾部取节点 → 读出其 key →cache_map.erase(key)→ 再list.pop_back() - 千万别反过来：先
pop_back()，再试图从已被析构的节点里取 key - 如果节点 value 很大，考虑用
std::unique_ptr包一层，让释放时机更可控
边界情况要测：容量设为 0、重复 put 同一 key、空 cache 调用 get——这些地方一松懈，unordered_map::end() 迭代器就会被误用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
