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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-02

浏览次数：次

返回列表

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

c++怎么实现一个lru缓存淘汰算法_c++数据结构设计与lru cache实现

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

基本思路与数据结构选择

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

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

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

C++代码实现

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

拾贝

一键同步微信读书所有笔记和划线，并在新标签页回顾

171 查看详情

#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
    std::list<std::pair<int, int>> 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成员函数的正确使用即可。

以上就是C++怎么实现一个LRU缓存淘汰算法_C++数据结构设计与LRU Cache实现的详细内容，更多请关注其它相关文章！

# 象中 # 网站seo优化就选天天软文专业 # 如何做网站百度排名优化 # 衡阳网站建设制作推广 # 有利于推广的外贸网站 # 安徽招商关键词排名优化 # 雄安网站建设优化公司 # seo推广预期 # seo优化对网络影响 # 评估网站建设方案 # 全员营销推广主题 # 最久 # 是一个 # c++ # 如何处理 # 尼克 # 拾贝 # 数据结构 # 移到 # 如何使用 # 链表 # red # stream # ios # ai # lru缓存