C++怎么实现一个LRU缓存_C++ LRU缓存算法实现步骤详解-C++-PHP中文网

C++怎么实现一个LRU缓存_C++ LRU缓存算法实现步骤详解

穿越時空

发布： 2025-10-23 09:49:02

原创

160人浏览过

LRU缓存通过哈希表和双向链表实现O(1)操作：1. 用unordered_map映射key到节点，双向链表维护访问顺序；2. get时查map并移至链表头；3. put时更新或插入，超容则删尾结点。

c++怎么实现一个lru缓存_c++ lru缓存算法实现步骤详解

LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，核心思想是：当缓存满时，优先淘汰最久未使用的数据。C++ 中实现 LRU 缓存通常结合哈希表和双向链表，以达到 O(1) 的查找、插入和删除效率。

1. 数据结构选择

要高效实现 LRU 缓存，需要两种数据结构配合：

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

我们自定义一个双向链表节点：

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

登录后复制

2. 核心操作设计

LRU 缓存需要支持两个主要操作：

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

存了个图

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

查看详情

get(key)：获取键对应的值，若不存在返回 -1；存在则将其移到链表头部（表示最近使用）。
put(key, value)：插入或更新键值对。若已存在，更新值并移至头部；若不存在且缓存已满，先删除尾部节点（最久未用），再插入新节点到头部。

3. 辅助函数：链表操作

为了简化逻辑，封装几个私有方法：

removeNode(node)：将节点从链表中摘除。
addToHead(node)：将节点插入到链表头部。
moveToHead(node)：将已有节点移动到头部（先删除再添加）。
removeTail()：删除尾节点，并从 map 中移除对应 key。

4. 完整代码实现

#include <iostream>
#include <unordered_map>
<p>class LRUCache {
private:
struct Node {
int key, value;
Node<em> prev;
Node</em> next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>std::unordered_map<int, Node*> cache;
Node* head;
Node* tail;
int capacity;
int size;

void removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

void addToHead(Node* node) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

void moveToHead(Node* node) {
    removeNode(node);
    addToHead(node);
}

Node* removeTail() {
    Node* node = tail->prev;
    removeNode(node);
    return node;
}

登录后复制

public: LRUCache(int cap) : capacity(cap), size(0) { head = new Node(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head; }

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()) {
        Node* node = cache[key];
        node->value = value;
        moveToHead(node);
    } else {
        Node* newNode = new Node(key, value);
        cache[key] = newNode;
        addToHead(newNode);
        size++;

        if (size > capacity) {
            Node* removed = removeTail();
            cache.erase(removed->key);
            delete removed;
            size--;
        }
    }
}

~LRUCache() {
    Node* curr = head;
    while (curr) {
        Node* temp = curr;
        curr = curr->next;
        delete temp;
    }
}

登录后复制

};

5. 使用示例

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

登录后复制

基本上就这些。这个实现保证了 get 和 put 操作都在 O(1) 时间内完成，符合 LRU 缓存的基本要求。关键点在于双向链表与哈希表的协同管理，以及对边界情况（如空链表、单节点）的正确处理。

以上就是C++怎么实现一个LRU缓存_C++ LRU缓存算法实现步骤详解的详细内容，更多请关注php中文网其它相关文章！