用 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<int, int>（key-value），按访问时间从头（最新）到尾（最旧）排列；
— std::unordered_map 存 int → std::list<std::pair<int, 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 <unordered_map>
#include <list>
class LRUCache {
int capacity_;
mutable std::list<std::pair<int, int>> cache_;
mutable std::unordered_map<int, std::list<std::pair<int, int>>::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<size_t>(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++免费学习笔记（深入）”；
