因为std::unordered_map无法维护访问顺序，不能实现LRU缓存所需的O(1)按时间排序、删头、插尾及节点挪动；必须结合std::list双向链表与哈希表映射迭代器协同工作。
为什么不能只用 std::unordered_map
因为 std::unordered_map 能做到 O(1) 查找和插入，但无法维护访问顺序——它不记录“最近谁被用了”，也就没法在缓存满时快速踢掉最久未用的项。LRU 的核心难点不在查，而在「按访问时间排序 + 快速删头/插尾 + 快速挪动某节点到尾部」。单靠哈希表做不到这三点同时 O(1)。
必须搭配双向链表：std::list + std::unordered_map
标准库里 std::list 是双向链表，支持 O(1) 头删、尾插、以及通过迭代器 O(1) 搬移节点（splice）。关键在于：用 std::unordered_map<Key, std::list<Node>::iterator> 把键映射到链表节点的迭代器，这样每次访问就能立刻把对应节点挪到链表尾（最新），而链表头永远是最久未用的。
实操建议：
- 节点结构体里存
key和value，否则删除头节点时不知道该从哈希表里删哪个键 - 用
list.splice(list.end(), list, it)把迭代器it挪到末尾，比先erase再push_back更高效（避免拷贝） - 插入新项前，先检查是否已存在——若存在，要更新值并挪到尾；若不存在，才新建节点、插入哈希表和链表
- 缓存满时，先取
list.front().key，再从unordered_map中删这个 key，最后list.pop_front()
std::list::iterator 的有效性有前提
std::list 的迭代器只有在对应节点没被销毁时才有效。一旦你调用 list.pop_front() 或 list.clear()，所有指向被删节点的迭代器就失效了。所以必须保证：哈希表中存的迭代器，只在对应节点还在链表中时才使用。
立即学习“C++免费学习笔记（深入）”；
常见错误现象：
- 缓存满后删头节点，但忘了同步从
unordered_map中 erase 对应 key → 下次再访问该 key 会解引用已失效迭代器，UB（通常 crash） - 用
auto it = list.begin()拿到头迭代器，然后直接map.erase(it->key)，再list.pop_front()—— 顺序反了，pop_front()后it就失效，但it->key已经读过了，看似能跑，但属于侥幸 - 把
list设为 public 成员，外部直接操作它 → 迭代器生命周期失控，极易出问题
一个极简可运行骨架（C++17）
#include <unordered_map>
#include <list>
template<typename K, typename V>
class LRUCache {
std::list<std::pair<K, V>> lst;
std::unordered_map<K, decltype(lst)::iterator> map;
size_t cap;
public:
LRUCache(size_t capacity) : cap(capacity) {}
V get(const K& key) {
auto it = map.find(key);
if (it == map.end()) return V{};
lst.splice(lst.end(), lst, it->second); // 挪到最后
return it->second->second;
}
void put(const K& key, const V& value) {
auto it = map.find(key);
if (it != map.end()) {
it->second->second = value;
lst.splice(lst.end(), lst, it->second);
return;
}
if (map.size() == cap && cap > 0) {
auto& old = lst.front();
map.erase(old.first);
lst.pop_front();
}
lst.emplace_back(key, value);
map[key] = std::prev(lst.end());
}
};
注意 map[key] = std::prev(lst.end())：因为 emplace_back 后新节点在尾，end() 是尾后，所以用 prev 取最后一个有效迭代器。这是容易漏掉的一处边界。
