c++中如何实现LRU缓存_c++ LRU缓存实现方法-C++-PHP中文网

c++中如何实现LRU缓存_c++ LRU缓存实现方法

尼克

发布： 2025-10-07 09:31:02

原创

637人浏览过

使用哈希表和双向链表实现LRU缓存，通过unordered_map映射键到节点，双向链表维护访问顺序，get和put操作均O(1)时间完成，访问或插入时将节点移至链表头部，容量满时删除尾部最久未使用节点。

c++中如何实现lru缓存_c++ lru缓存实现方法

在C++中实现LRU（Least Recently Used）缓存，核心思路是结合哈希表和双向链表，以达到O(1)的查找、插入和删除效率。LRU缓存会优先淘汰最久未使用的数据，因此需要快速定位元素并维护访问顺序。

使用unordered_map + 双向链表

标准做法是使用std::unordered_map存储键到节点的映射，配合自定义的双向链表管理访问顺序。

步骤说明：

每次访问某个键时，将其对应的节点移到链表头部（表示最新使用）
插入新键值对时，添加到链表头部
当缓存满时，删除链表尾部的节点（最久未使用）
使用哈希表快速找到节点位置，避免遍历链表

代码实现：

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

#include <iostream>
#include <unordered_map>
<p>struct ListNode {
int key, value;
ListNode<em> prev;
ListNode</em> next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><p>class LRUCache {
private:
int capacity;
std::unordered_map<int, ListNode<em>> cache;
ListNode</em> head; // 指向最新使用的节点
ListNode* tail; // 指向最久未使用的节点</p><pre class='brush:php;toolbar:false;'>// 将节点移动到头部
void moveToHead(ListNode* node) {
    if (node == head) return;

    // 断开原连接
    if (node == tail) {
        tail = tail->prev;
        tail->next = nullptr;
    } else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // 插入到头部
    node->next = head;
    node->prev = nullptr;
    head->prev = node;
    head = node;
}

// 添加新节点到头部
void addToHead(ListNode* node) {
    if (!head) {
        head = tail = node;
    } else {
        node->next = head;
        head->prev = node;
        head = node;
    }
}

// 删除尾部节点
void removeTail() {
    ListNode* toDelete = tail;
    if (head == tail) {
        head = tail = nullptr;
    } else {
        tail = tail->prev;
        tail->next = nullptr;
    }
    cache.erase(toDelete->key);
    delete toDelete;
}

登录后复制

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

int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) return -1;

    ListNode* node = it->second;
    moveToHead(node);
    return node->value;
}

void put(int key, int value) {
    auto it = cache.find(key);
    if (it != cache.end()) {
        it->second->value = value;
        moveToHead(it->second);
    } else {
        ListNode* newNode = new ListNode(key, value);
        if (cache.size() >= capacity) {
            removeTail();
        }
        addToHead(newNode);
        cache[key] = newNode;
    }
}

~LRUCache() {
    while (head) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

登录后复制

};

使用std::list简化实现

可以借助std::list自动管理双向链表，减少手动指针操作。

存了个图

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

查看详情

#include <list>
#include <unordered_map>
<p>class LRUCache {
private:
int capacity;
std::list<std::pair<int, int>> lst; // 存储 key-value 对
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;</p><p>public:
LRUCache(int cap) : capacity(cap) {}</p><pre class='brush:php;toolbar:false;'>int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) return -1;

    // 移动到链表前端
    lst.splice(lst.begin(), lst, 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;
        lst.splice(lst.begin(), lst, it->second);
        return;
    }

    if (cache.size() >= capacity) {
        auto& last = lst.back();
        cache.erase(last.first);
        lst.pop_back();
    }

    lst.push_front({key, value});
    cache[key] = lst.begin();
}

登录后复制

};

这种方法更简洁，splice函数能高效地将节点移到头部。