必须用双向链表+哈希表组合：双向链表支持O(1)节点移动与删除，哈希表提供key到节点迭代器的O(1)索引；单独list无法O(1)定位，单独unordered_map无法维护时序。
为什么必须用双向链表 + 哈希表组合
单靠 std::list 无法在 O(1) 时间定位某个 key 对应的节点位置；单靠 std::unordered_map 又无法维护访问时序。LRU 的核心操作——“访问即置顶”和“淘汰尾部”——要求：查找快（O(1)）、移动快（O(1)）、删除快（O(1)）。只有双向链表支持任意节点的常数时间摘除与插入，而哈希表提供 key 到链表节点指针的直接映射。
如何设计节点与容器结构
不能直接存 std::list<:pair v>>，因为 erase() 需要迭代器，而哈希表里得存这个迭代器。正确做法是：哈希表值类型为 std::list，Node 为自定义结构体，含 key 和 value。这样每次访问 key 时，能用哈希表 O(1) 拿到对应节点的迭代器，再用 splice() 把它移到链表头部。
-
std::list存储所有活跃项，头为最近使用，尾为最久未用 -
std::unordered_map提供 key → 节点位置的直连索引::iterator> - 每次
get()或put()都要调用私有函数moveToHead(iterator)，用splice(head_iter, list, it)实现零拷贝移动
put() 中淘汰逻辑怎么写才不漏判
淘汰只发生在 put() 且容量超限时，但要注意两种情况都得处理：key 已存在（更新 value 并刷新位置），key 不存在（插入新节点并可能淘汰）。容易出错的是：先 insert 再检查 size，导致实际 size 超过 capacity + 1 才删——这会让缓存短暂溢出。
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
cache[key]->value = value;
moveToHead(cache[key]);
return;
}
Node node{key, value};
lru_list.push_front(node);
cache[key] = lru_list.begin(); // 迭代器有效
if (cache.size() > capacity) {
int tail_key = lru_list.back().key;
lru_list.pop_back();
cache.erase(tail_key); // 必须先删链表再删 map，否则迭代器失效
}
}
迭代器失效是最大陷阱
std::list 的迭代器只有在对应节点被 erase() 时才失效；push_front()、splice()、pop_back() 都不使其他迭代器失效。但一旦你对某个节点调用了 erase()，所有指向它的迭代器立刻变悬垂指针。所以 cache.erase(tail_key) 必须在 lru_list.pop_back() 之后——否则你拿着一个刚被删节点的迭代器还试图从 map 里删它，行为未定义。
立即学习“C++免费学习笔记（深入）”；
另一个常见错误：用 auto it = lru_list.begin(); lru_list.erase(it); 后继续用 it ——哪怕只是打印，也属于未定义行为。所有涉及 erase 的地方，务必确认后续不再使用该迭代器。
