c++怎么实现一个LRU缓存算法_c++中LRU缓存的设计与实现

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

LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)：哈希表映射key到链表节点，链表维护访问顺序，最近使用置头，满时删尾。

实现一个LRU（Least Recently Used）缓存的核心思路是：当缓存满时，优先淘汰最久未使用的数据。为了高效地完成插入、查找和更新操作，C++中通常结合哈希表（unordered_map）和双向链表（list）来实现。

1. LRU缓存的基本要求

一个LRU缓存需要支持以下两个核心操作：

get(key)：如果键存在，返回对应的值，并将该键移到最近使用位置；否则返回 -1。
put(key, value)：插入或更新键值对。如果超出容量，删除最久未使用的条目。

这两个操作的时间复杂度都应为 O(1)。

2. 数据结构选择

要达到 O(1) 的时间复杂度，可以这样设计：

unordered_mapair>::iterator>：用于快速定位某个 key 是否存在及其在链表中的位置。
list>：双向链表存储键值对，最近使用的放在链表头部，最久未使用的在尾部。

这种组合既能快速查找，又能高效地移动和删除节点。

3. 实现代码示例

#include 
#include 
#include 

class LRUCache {
private:
    int capacity;
    std::unordered_map>::iterator> cache;
    std::list> used;

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

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }
        // 将当前访问的节点移到链表头部
        used.splice(used.begin(), used, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            // 更新值并移到头部
            it->second->second = value;
            used.splice(used.begin(), used, it->second);
            return;
        }

        // 插入新元素到链表头部
        used.emplace_front(key, value);
        cache[key] = used.begin();

        // 如果超过容量，删除尾部元素
        if (cache.size() > capacity) {
            int lastKey = used.back().first;
            cache.erase(lastKey);
            used.pop_back();
        }
    }
};