LRU 缓存
LRU Cache
实现一个容量为 capacity 的 LRU 缓存，get / put 都要 O(1)，满了淘汰最久未使用的一项。
在力扣中练习题目描述
LRUCache 类：LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
解题思路
哈希表 + 手写双向链表
哈希表负责 O(1) 定位，双向链表负责维护「谁最久没被用」
只用哈希表能快速查值，却不知道哪项最久没用；数组能保存顺序，但每次移动中间元素要 O(n)。把哈希索引和双向链表组合起来：pos 按 key 定位节点，链表从左到右维护最近到最久的访问顺序。
自拟主例容量为 3：依次 put(4,40)、put(7,70)、put(2,20)、get(4)、put(7,75)、put(9,90)、get(2)、get(7)。读取依次返回 40、-1、75。
put(2,20)：新节点挂到表头。
put(2, 20)
4 → 节点 47 → 节点 72 → 节点 2get 命中和 put 更新都要提升原节点。更新 7 的值时不能再建一个 7，缓存大小仍是 3。
put(7,75)：更新原节点并移到表头，不新增节点。
命中已有 key 时，缓存大小不变；新 value 替换旧 value。
put(7, 75)
4 → 节点 47 → 节点 72 → 节点 2get(4) = 40插入 9 前，表尾 2 最久没用，先摘链、再清理 pos 并释放节点，最后插入 9。head、tail 是哨兵，不占容量；淘汰的是 tail 的前驱，不能误删 tail。
易错点
- 淘汰时只从链表删了节点，忘了 erase 哈希表，之后 get 会读到已释放的内存。
- get 命中后忘记挪到表头，导致它下次被当成最久未使用而误淘汰。
- put 更新已有 key 时又 new 了一个节点，旧节点没摘掉，链表里出现两份同一个 key。
STL list + splice
用 list::splice 在链表内部搬节点，不拷贝、不失效迭代器
同样满足平均 O(1) 的正确实现，使用 STL list 代替手写指针；splice 会移动原节点而不复制。
手写双向链表要维护四个指针，容易漏。C++ 的 std::list 已经提供了需要的一切，再配一个迭代器哈希表就行：
list<pair<int, int>> lru：每个元素是{key, value}，表头最近使用；unordered_map<int, list<...>::iterator> pos：key 直接映射到它在 list 里的位置。
命中之后不需要 erase 再 insert，用 lru.splice(lru.begin(), lru, it->second) 就能把节点原地摘下来挂到表头：不拷贝元素，指向它的迭代器也不会失效，这正是这里最需要的行为。
淘汰时 lru.back() 就是最久未使用的元素，先 pos.erase(lru.back().first)，再 pop_back()。顺序同样重要：先拿到 key 再删节点。
这份代码比手写版短很多，代价是要熟悉 splice 的语义；能手写指针，通常更能说明你理解链表。
- 1用 list 保存 {key, value}，表头最近使用。
- 2pos 记录 key 到 list 迭代器的映射。
- 3get 命中：splice 到表头，返回 value。
- 4put 已存在：改值 + splice 到表头。
- 5put 不存在且满了：先 erase pos，再 pop_back。
易错点
- 先 pop_back 再取 back().first，节点已经没了，访问的是无效元素。
- 用 vector 存缓存内容，挪动元素是 O(n)，达不到要求。
- 把迭代器存进哈希表后又在别处 erase 了元素，迭代器失效。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
capacity = 3；put(4,40), put(7,70), put(2,20), get(4), put(7,75), put(9,90), get(2), get(7)容量为 3：head 与 tail 相连，索引为空。
创建空缓存
空查看 C++ 代码
延伸阅读
- LRU 的两条要求（O(1) 查找 + O(1) 调整顺序）刚好对应哈希表 + 双向链表，这是「组合数据结构」最经典的范例。
- 同类设计题还有 LFU 缓存（460，按频率淘汰）、全 O(1) 的数据结构（432），骨架都是「索引 + 有序容器」。
- 工程里的缓存还要考虑并发、过期时间、内存上限；但核心的淘汰顺序，仍然是这一条双向链表。