C++怎么实现一个LRU缓存淘汰算法_C++数据结构设计与LRU Cache实现

尼克 2025-12-02 00:00:00 次阅读

LRU缓存通过哈希表和双向链表组合实现，O(1)完成查找与顺序维护。1. 哈希表映射key到链表节点；2. 链表头部存最近使用项；3. 访问或插入时更新位置；4. 容量超限时删除尾部节点。

实现一个LRU（Least Recently Used）缓存淘汰算法，核心在于快速访问数据的同时维护访问顺序。当缓存满时，优先淘汰最久未使用的数据。C++中可以通过结合 哈希表（unordered_map） 和 双向链表（list） 高效实现，达到O(1)的查找、插入和删除效率。

基本思路与数据结构选择

为了同时满足快速查找和顺序管理：

unordered_map：存储键（key）到双向链表节点的映射，实现O(1)查找。
list（双向链表）：维护访问顺序，最近使用的放头部，最久未用的在尾部，便于O(1)移动和删除。

每次访问某个key，就将其对应节点移到链表头部；插入新元素时若超出容量，则删除尾部节点。

C++代码实现

以下是一个完整的LRU Cache类实现：

#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;
        }

        // 新插入，检查是否超容
        if (cache.size() >= capacity) {
            int old_key = used.back().first;
            cache.erase(old_key);
            used.pop_back();
        }

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

关键操作说明

splice 是实现高效移动的核心：

used.splice(used.begin(), used, it->second) 将指定节点直接移到链表头部，不涉及内存分配，时间复杂度为O(1)。
避免了先删除再插入带来的开销。

emplace_front 直接在链表头部构造新节点，比 push_front 更高效。

使用示例

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    std::cout << lru.get(1) << "\n"; // 输出 1
    lru.put(3, 3);                    // 淘汰 key=2
    std::cout << lru.get(2) << "\n"; // 输出 -1
    return 0;
}

基本上就这些。通过哈希表+双向链表的组合，C++能简洁高效地实现LRU缓存，适合面试和实际应用。注意边界处理和STL成员函数的正确使用即可。