用 std::list + std::unordered_map 实现 LRU 是因二者互补：unordered_map 提供 O(1) 查找，list 支持 O(1) 头插与删除；list 存 key-value 对并按访问序排列，map 存 key 到 list 迭代器的映射，配合 splice 实现高效更新。
为什么用 std::list + std::unordered_map 实现 LRU
因为 LRU 的核心操作是「快速查找 + 快速移动到头部」，单靠一种容器无法兼顾：
— std::unordered_map 提供 O(1) 的 key 查找，但不维护顺序；
— std::list 支持 O(1) 的节点删除和头插，但查找是 O(n)。
两者结合，就能在平均 O(1) 时间内完成 get / put 操作。
std::list 存什么、std::unordered_map 存什么
关键不是存「值」，而是存「双向引用关系」：
— std::list 存 std::pair（key-value），按访问时间从头（最新）到尾（最旧）排列；
— std::unordered_map 存 int → std::list<:pair int>>::iterator，即每个 key 映射到 list 中对应节点的迭代器。
这样，get 时通过 map 找到 iterator，再用 splice() 把该节点移到 list 头部；put 时若已存在，同样 splice 更新位置；若不存在且超容，则先擦除 list 尾部节点，并用其 key 去 map 中 erase。
容易踩的坑：迭代器失效与 const 正确性
- 不要在
std::list上用erase(iterator)后还保留该 iterator —— 它已失效；正确做法是用splice()移动，或先保存 key 再 erase -
std::unordered_map::erase(key)比erase(iterator)更安全，避免迭代器悬空 - 所有涉及 list 节点访问的操作（如
front()、back()）前，必须检查list.empty()，否则 UB - 类成员函数如
get()应声明为const，但内部要修改 list 顺序 —— 这时需把 list 和 map 声明为mutable
一个可直接跑的最小实现（c++17）
#include #include class LRUCache { int capacity_; mutable std::list> cache_; mutable std::unordered_map>::iterator> map_; public: LRUCache(int capacity) : capacity_(capacity) {} int get(int key) const { auto it = map_.find(key); if (it == map_.end()) return -1; // 移到头部 cache_.splice(cache_.begin(), cache_, it->second); return it->second->second; } void put(int key, int value) { auto it = map_.find(key); if (it != map_.end()) { it->second->second = value; cache_.splice(cache_.begin(), cache_, it->second); return; } if (cache_.size() == static_cast(capacity_)) { auto& last = cache_.back(); map_.erase(last.first); cache_.pop_back(); } cache_.emplace_front(key, value); map_[key] = cache_.begin(); } };
注意 mutable 是关键：它允许在 const 成员函数中修改 cache_ 和 map_，否则 splice() 会编译失败。另外，emplace_front 比 push_front 更高效，避免临时 pair 构造。
立即学习“C++免费学习笔记（深入）”；