必须用双向链表+哈希表：链表O(1)移动删除，哈希表O(1)定位；单用list无法O(1)查key，单用unordered_map无法维护时序。
为什么必须用双向链表 + 哈希表
单靠 std::list 无法 O(1) 查找某个 key 对应的节点位置；单靠 std::unordered_map 无法维护访问时序。双向链表支持 O(1) 删除和移动节点，哈希表提供 O(1) 定位——两者缺一不可。
常见错误是只用 map 存值、用 vector 或 list 手动遍历找 key，导致 get() 变成 O(n)，完全失去 LRU 意义。
- 链表节点必须存 key，否则删除尾节点时无法反查 map 中对应 entry
- map 的 value 必须是链表迭代器（
std::list），不是指针或索引::iterator - 插入/访问后要把对应节点移到链表头（最新使用），不能只改 map
如何正确设计 Node 和 LRUCache 类结构
Node 不需要额外封装类，直接用 struct 即可；重点是成员顺序和 const 正确性：
struct Node {
int key;
int value;
Node(int k, int v) : key(k), value(v) {}
};
LRUCache 内部需持有：
立即学习“C++免费学习笔记（深入）”；
-
std::unordered_map：key → 链表中该节点的迭代器::iterator> cache -
std::list：按访问时间从新到旧排列（头最新，尾最久未用）order -
int capacity：缓存上限，初始化后不变
注意：std::list::iterator 在 insert/erase 后仍有效（只要不删它自己），这是能安全用作 map value 的前提。
get() 和 put() 的关键操作步骤
get(key) 不只是查 map，还要触发“提升热度”：
- 若 key 不存在，返回 -1
- 若存在，用 map 查出对应
iter，用order.erase(iter)删除原位置，再order.push_front(*iter)插入头部 - 更新 map 中该 key 的 value 为新的头迭代器（
order.begin()）
put(key, value) 要处理三种情况：
- key 已存在：更新 value，再执行和
get()相同的“移到头部”逻辑 - key 不存在且 size push_front 新节点，map 插入 key→begin()
- key 不存在且已满：先删
order.back().key对应的 map entry，再pop_back()，再插入新节点
漏掉 map 和 list 的同步更新，就会出现“map 还指着已删节点”——迭代器失效，行为未定义。
容易被忽略的边界与性能点
构造函数里别忘了初始化 capacity，且所有成员变量应在初始化列表中完成构造，避免默认构造后再赋值。
实际编码中常见坑：
- 用
auto it = cache.find(key)后，误写it->second->value（错：it->second 是 iterator，不是指针） - 在
put()中删尾节点前，没先从 map erase，导致 map 持有悬空迭代器 - 把
order.push_front({key, value})写成order.emplace_front(key, value)—— 没问题，但要注意参数匹配构造函数 - 没考虑
capacity == 0的情况，此时所有 put 都应忽略，get 全返回 -1
真正难的不是写出来，而是让每次 get/put 都严格维持 map 和 list 的一致性——少一次 erase 或少一次 update，缓存就悄悄坏了。
