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