不能单独用 std::map 实现 LRU，因其不维护访问顺序、无法 O(1) 移动节点；必须组合 std::unordered_map（O(1) 查找）与 std::list（迭代器稳定、O(1) 插删），并通过 key_to_iter 映射快速定位并更新 list 中节点位置。
为什么不用 std::map 单独实现 LRU？
因为 std::map 本身不记录访问顺序，插入和查找是 O(log n)，但“把最近访问的项提到最前面”这个操作它做不到——没有指针或迭代器稳定性保障，也不能在常数时间内移动节点位置。
常见错误现象：map::erase 后再 insert 模拟“更新时间”，看似可行，实则每次操作都是两次 O(log n)，且 key 重复插入会改变迭代器有效性，list 里对应的节点可能已失效。
- 真正需要的是：查找快（
O(1)）、删头/插尾快（O(1)）、还能通过 key 快速定位到 list 中任意节点（用于“访问即置顶”） - 所以必须配对：
std::unordered_map<Key, std::list<Node>::iterator>+std::list -
std::list迭代器稳定：只要节点没被erase，迭代器永远有效；这正是 map 值能安全存它的前提
std::list 存什么？怎么让 unordered_map 找到它？
不能只存 value，否则 get 时无法返回 value 且无法更新 list 顺序。必须存完整键值对，否则 map 里存的 iterator 解引用后拿不到 key，就没法在 list 里做 erase+push_front。
典型结构：
立即学习“C++免费学习笔记（深入）”；
struct Node {
int key;
int value;
};
std::list<Node> cache;
std::unordered_map<int, std::list<Node>::iterator> key_to_iter;
使用场景：每次 get(key) 时，先查 map 得到对应 list 迭代器 → 解引用拿到 Node → 记录 value 返回 → 再把该节点从 list 原位置移除并 push_front。
- 注意：
list::erase(iterator)不会使其他迭代器失效，但必须确保该 iterator 确实合法（map 查不到就别 erase） -
key_to_iter[key] = cache.begin();这句必须在push_front之后赋值，否则cache.begin()指向的是旧首节点 - 如果用
std::list::splice可避免拷贝，更高效：cache.splice(cache.begin(), cache, it);
容量超限时，删谁？怎么同步清理 map？
删的是 cache.back()，不是 cache.front() —— 因为 front 是最新访问的，back 才是最久未用（LRU 的“least recently”体现在 list 尾部）。
容易踩的坑：cache.pop_back() 之后，忘了从 key_to_iter 中 erase 对应 key，导致 map 中残留野指针（实际是已销毁节点的 iterator），后续访问直接 UB。
- 正确顺序：先取
cache.back().key→ 用它去 erasekey_to_iter→ 再cache.pop_back() - 千万别反过来：pop_back 后
back().key已不可访问 - 如果 Node 是自定义类型且含非 trivial 析构函数，确保 move 构造/赋值安全（一般 int 成员没问题）
要不要用 std::shared_ptr 或裸指针替代迭代器？
不要。用 shared_ptr<Node> 增加引用计数开销，且无法解决“快速移动节点位置”的问题；用裸指针更危险——list 重分配时指针全失效，而迭代器在 list 中是稳定的。
性能影响：迭代器本质是封装好的指针+节点链接信息，std::list::iterator 解引用、自增、赋值都是 O(1)，无额外间接跳转。
- 兼容性没问题：C++11 起
std::list::iterator稳定性就是标准保证的 - 唯一复杂点：所有对 list 的修改（
push_front、erase、splice）都必须同步更新 map 中的 iterator 值 - 最容易被忽略的地方：
put时 key 已存在，要先用老 iterator 删除 list 节点，再 push_front 新节点，并更新 map 中该 key 对应的 iterator —— 这里漏一步，缓存逻辑就错乱了
