C++怎么实现一个LRU缓存_C++缓存机制与LRU实现方法

新闻中心 NEWS CENTER

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

C++怎么实现一个LRU缓存_C++缓存机制与LRU实现方法

2025-11-13

浏览次数：次

返回列表

答案：LRU缓存通过哈希表和双向链表实现，支持O(1)查找、插入与删除，访问或添加节点时移至链表头部，容量超限时删除尾部最久未使用节点。

c++怎么实现一个lru缓存_c++缓存机制与lru实现方法

实现一个LRU（Least Recently Used）缓存，核心在于快速访问数据的同时维护访问顺序，当缓存满时淘汰最久未使用的项。C++中可以通过结合哈希表和双向链表高效实现。

LRU缓存的基本原理

LRU缓存要求：

支持O(1)时间的插入、查找和删除操作。
每次访问某个键值后，将其标记为“最近使用”。
当容量超限时，自动删除最久未使用的条目。

为了满足这些需求，通常采用：

std::unordered_map：用于存储键到节点的映射，实现快速查找。
自定义双向链表：维护访问顺序，头结点是最新的，尾结点是最旧的。

设计双向链表节点结构

每个缓存项需要保存键、值，并能前后连接：

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

这个结构便于在链表中快速移动或删除节点。

LRUCache类的实现

完整类定义包括初始化、获取、插入等操作：

Perplexity

Perplexity是一个ChatGPT和谷歌结合的超级工具，可以让你在浏览互联网时提出问题或获得即时摘要

302

查看详情

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, Node*> cache;
    Node* head; // 指向最新使用的节点
    Node* tail; // 指向最久未使用的节点
<pre class='brush:php;toolbar:false;'>// 将现有节点移到链表头部
void moveToHead(Node* 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->prev = nullptr;
    node->next = head;
    head->prev = node;
    head = node;
}

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

// 删除尾部节点（最久未使用）
void removeTail() {
    if (!tail) return;
    Node* toDel = tail;
    tail = tail->prev;
    if (tail) tail->next = nullptr;
    else head = nullptr;
    cache.erase(toDel->key);
    delete toDel;
}

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

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

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

};

使用示例与注意事项

测试代码：

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << lru.get(1) << endl; // 输出 1
    lru.put(3, 3);             // 容量满，淘汰 key=2
    cout << lru.get(2) << endl; // 输出 -1（已淘汰）
    return 0;
}

注意点：