c++如何实现LRU Cache缓存机制_c++ 双向链表与哈希映射结合【案例】

裘德小鎮的故事 2025-12-30 00:00:00 次阅读

必须协同使用std::list和std::unordered_map：list维护访问顺序且迭代器稳定（删除非所指节点不失效），map提供O(1)定位；capacity为0时put应直接返回。

为什么不能只用 `std::list` 或只用 `std::unordered_map`

单独用 std::list 无法在 O(1) 时间定位某个 key 对应的节点——每次 get 都得遍历，退化成 O(n)；只用 std::unordered_map 则无法维护访问顺序，淘汰最久未用项时得遍历所有 value 找最小时间戳，也是 O(n)。必须让两者协作：unordered_map 存 key → list::iterator 映射，list 存实际 pair 并保证头尾有序。

`list::iterator` 能稳定指向元素的前提是什么

std::list 的迭代器在插入/删除其他节点时不失效（这是它和 vector 的关键区别），但前提是不删除该迭代器本身指向的节点。所以你在 get 时把节点移到 front，或在 put 时删除 back 节点，都必须先用 map 查到对应 iterator，再用 splice 或 erase 操作——不能直接保存裸指针或索引。

错误写法：auto ptr = &(*it); —— list 迭代器不是指针，取地址无意义且不保活
正确做法：cache_list.splice(cache_list.begin(), cache_list, it); 移动节点
map 中存储的是 std::list>::iterator，不是 pair*

如何避免 `put` 时重复插入导致内存泄漏或逻辑错乱

常见坑是：key 已存在，却先 erase map 项、再 push_front 新节点，最后再 insert map —— 这中间如果 list 操作失败（比如内存不足），map 就丢了映射，且旧节点还在 list 里。更安全的做法是统一用「查-删-插」流程，并复用原节点：

void put(int key, int value) {
    if (cache_map.find(key) != cache_map.end()) {
        auto it = cache_map[key];
        it->second = value;                    // 更新值
        cache_list.splice(cache_list.begin(), cache_list, it); // 移至头部
    } else {
        cache_list.push_front({key, value});
        cache_map[key] = cache_list.begin();
        if (cache_map.size() > capacity) {
            int tail_key = cache_list.back().first;
            cache_map.erase(tail_key);
            cache_list.pop_back();
        }
    }
}