c++中如何实现一个LRU缓存淘汰算法_c++ LRU缓存算法实现-C++-PHP中文网

c++中如何实现一个LRU缓存淘汰算法_c++ LRU缓存算法实现

穿越時空

发布： 2025-10-31 21:25:02

原创

494人浏览过

LRU缓存通过哈希表+双向链表实现O(1)操作，最近访问节点置于链表头部，满时淘汰尾部节点。

c++中如何实现一个lru缓存淘汰算法_c++ lru缓存算法实现

LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。在C++中，可以通过哈希表 + 双向链表高效实现O(1)的插入、查找和删除操作。

基本数据结构设计

使用std::unordered_map存储键到节点指针的映射，双向链表维护访问顺序——最近使用的放头部，淘汰从尾部进行。

定义链表节点结构：

struct ListNode {
    int key, value;
    ListNode* prev;
    ListNode* next;
    ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

核心操作实现

封装LRUCache类，包含以下关键函数：

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

存了个图

视频图片解析/字幕/剪辑，视频高清保存/图片源图提取

查看详情

get(int key)：若存在，将对应节点移到链表头并返回值；否则返回-1
put(int key, int value)：新增或更新键值对，若超出容量则删除尾节点

辅助方法用于维护链表：

removeNode(ListNode* node)：从链表中移除指定节点
addToHead(ListNode* node)：将节点插入链表头部

完整代码示例

class LRUCache {
private:
    std::unordered_map<int, ListNode*> cache;
    ListNode* head;
    ListNode* tail;
    int capacity;

    void removeNode(ListNode* node) {
        if (node == head) head = node->next;
        if (node == tail) tail = node->prev;
        if (node->prev) node->prev->next = node->next;
        if (node->next) node->next->prev = node->prev;
    }

    void addToHead(ListNode* node) {
        node->next = head;
        node->prev = nullptr;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

public:
    LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        ListNode* node = cache[key];
        removeNode(node);
        addToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            ListNode* node = cache[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            ListNode* newNode = new ListNode(key, value);
            cache[key] = newNode;
            addToHead(newNode);

            if (cache.size() > capacity) {
                ListNode* toDelete = tail;
                removeNode(tail);
                cache.erase(toDelete->key);
                delete toDelete;
            }
        }
    }
};

注意：实际项目中可考虑智能指针管理内存，避免手动new/delete。这个实现保证了get和put操作均摊时间复杂度为O(1)，符合高频访问场景需求。

基本上就这些。

以上就是c++++中如何实现一个LRU缓存淘汰算法_c++ LRU缓存算法实现的详细内容，更多请关注php中文网其它相关文章！