如何用c++实现一个简单的LRU缓存淘汰算法【算法实战】-C++-PHP中文网

如何用c++实现一个简单的LRU缓存淘汰算法【算法实战】

穿越時空

发布： 2025-12-20 17:59:02

原创

214人浏览过

LRU缓存用unordered_map+list实现：哈希表O(1)查key，链表O(1)维护时序；get时命中则移至头部并更新迭代器，未命中返回-1；put时存在则更新并前置，不存在且满容则删尾部再头插。

如何用c++实现一个简单的lru缓存淘汰算法【算法实战】

用C++实现LRU缓存，核心是让“最近最少使用”的元素自动被淘汰，关键在于快速查找 + 快速移动到最新位置。标准做法是：哈希表（unordered_map） + 双向链表（list）组合——哈希表提供O(1)查找，链表维护访问时序，且支持O(1)头插、尾删和任意节点摘除。

数据结构选型与设计逻辑

不能只用map或vector：map按key排序不反映访问顺序；vector删除中间元素是O(n)。而list是双向链表，erase一个迭代器是O(1)；unordered_map存key→list迭代器，就能在查到节点的同时，立刻把它移到链表头部（表示最新访问）。

缓存结构通常包含：

一个std::list<:p style="color:#f60; text-decoration:underline;" title="ai" href="https://www.php.cn/zt/17539.html" target="_blank">air>：存(key, value)，头部为最新访问，尾部为最久未用
一个std::unordered_map::iterator>：通过key快速定位链表中对应节点
一个int capacity：最大容量，超限时删尾部节点

关键操作的实现要点

get(int key)：查map，存在则把对应节点移到list头部，更新map中该key的新迭代器，返回value；不存在返回-1。

立即学习“C++免费学习笔记（深入）”；

put(int key, int value)：

AI社交封面生成器

一句话/一张图一键智能生成社交媒体图片的AI设计神器

108

查看详情

如果key已存在：更新value，移到头部，更新map迭代器
如果key不存在：检查是否已达capacity；若已满，先删list尾部节点，并从map中擦除其key；再头插新节点，map中加入新映射

注意：list::push_front()返回新插入元素的迭代器，可直接存入map；用list::erase()删尾部时，要先用back().first拿到key再删map，否则迭代器失效后无法反查key。

完整可运行代码示例

以下是最简实用版本（省略异常处理，适合学习和面试）：

class LRUCache {
    int cap;
    list<pair<int, int>> cache; // {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> map;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto it = map[key];
        int val = it->second;
        cache.erase(it);
        cache.push_front({key, val});
        map[key] = cache.begin();
        return val;
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            cache.erase(map[key]);
        } 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();
    }
};

登录后复制

调用示例：LRUCache lru(2); lru.put(1,1); lru.put(2,2); lru.get(1); lru.put(3,3); → 此时缓存含{3,3}和{1,1}，{2,2}被淘汰。