LRU必须用双向链表+哈希表，因为仅std::list无法O(1)查找，仅std::unordered_map无法维护访问顺序；双向链表支持O(1)删除和移至头部，哈希表存储迭代器实现O(1)定位。
为什么LRU必须用双向链表 + 哈希表
单靠 std::list 或 std::unordered_map 都没法在 O(1) 时间完成「查+删+挪到头」这三件事。哈希表提供 O(1) 查找，但不维护顺序；链表维护访问序，但遍历删节点是 O(n)。双向链表的关键在于：给定一个节点指针，能 O(1) 删除它、也能 O(1) 插到头部——而这恰好是哈希表能提供的（value 存的是迭代器或指针）。
注意：std::list 的迭代器稳定（插入/删除不使其他迭代器失效），所以可以安全存进 unordered_map 里；而 std::vector 或 std::deque 不行。
如何用 std::list 和 std::unordered_map 组合实现
核心设计是：哈希表的 key 是缓存键，value 是 std::list 中对应节点的迭代器；链表节点存完整的 std::pair。
关键操作逻辑：
立即学习“C++免费学习笔记（深入）”；
-
get(key)：查 map → 找到则用迭代器从 list 中
erase再push_front，同时更新 map 中该 key 对应的新迭代器 -
put(key, value)：若 key 已存在，同样先 erase 再 push_front 并更新；若不存在，先检查容量是否满 —— 满则
pop_back并从 map 中 erase 最久未用项，再插入新节点 - 所有
list::push_front返回的迭代器，都要立刻存进 map，否则后续 get 时拿不到有效位置
示例片段（简化版）：
class LRUCache {
int cap;
list> cache;
unordered_map>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (map.find(key) == map.end()) return -1;
auto it = map[key];
cache.push_front(*it);
cache.erase(it);
map[key] = cache.begin(); // 更新迭代器
return cache.begin()->second;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
auto it = map[key];
cache.erase(it);
} else if (cache.size() == cap) {
int lastKey = cache.back().first;
cache.pop_back();
map.erase(lastKey);
}
cache.push_front({key, value});
map[key] = cache.begin();
}
};
面试常踩的三个坑
实际写的时候，这几个点最容易出错：
-
std::list::erase返回的是下一个迭代器，但你传进去的如果已经是end()或非法迭代器，会 UB —— 所以每次 erase 前必须确认 map 中存在且迭代器有效 - 更新 map 时忘记改迭代器值，比如 put 已存在 key 后没重置
map[key] = cache.begin()，下次 get 就用旧迭代器，可能指向已删除节点 - 用
std::list存裸指针（如new Node）而不是直接存 pair —— 这样要自己管理内存，且迭代器失效风险更高；C++11 后完全没必要
能不能用 std::map 替代 std::unordered_map
可以，但不推荐。虽然 std::map 也能存迭代器，但查找是 O(log n)，违背 LRU「所有操作 O(1)」的设计目标。而且面试官看到用 map，大概率会追问「为什么不用哈希表」。
另外注意：std::unordered_map 的迭代器在 rehash 时会失效，但只要你只做 insert/erase/lookup，不触发扩容（比如预设 reserve），就安全；实际中只要别在循环里反复 insert 导致多次 rehash，问题不大。
真正容易被忽略的是：链表节点移动后，map 中旧迭代器立刻失效，必须立刻更新。这个细节一漏，程序可能跑几轮才崩，debug 很费时间。
