c++中如何实现LRU缓存算法_c++ list与unordered_map结合实现【汇总】

用 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。

慧中标AI标书

慧中标AI标书是一款AI智能辅助写标书工具。

下载

容易踩的坑：迭代器失效与 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++免费学习笔记（深入）”；