c++怎么实现一个LRU缓存淘汰算法_c++最近最少使用缓存机制实现-C++-PHP中文网

c++怎么实现一个LRU缓存淘汰算法_c++最近最少使用缓存机制实现

穿越時空

发布： 2025-10-25 19:46:01

原创

575人浏览过

LRU缓存通过哈希表和双向链表实现，get和put操作均O(1)：访问时移至链表头，满时删尾部节点。

c++怎么实现一个lru缓存淘汰算法_c++最近最少使用缓存机制实现

实现一个LRU（Least Recently Used）缓存淘汰算法，核心是结合哈希表和双向链表，做到查询和更新都在 O(1) 时间完成。C++ 中可以通过 unordered_map 和自定义的双向链表节点来高效实现。

基本思路

LRU 缓存需要满足：

访问某个键时，它变为“最近使用”
当缓存满时，淘汰最久未使用的项
get 和 put 操作都需在 O(1) 完成

为此，我们使用：

unordered_map：快速查找 key 是否存在，以及对应节点位置
双向链表：维护使用顺序，头结点是最新的，尾结点是最老的

数据结构设计

定义双向链表节点和缓存类框架：

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

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

登录后复制

缓存类包含：

存了个图

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

查看详情

容量 capacity
当前大小 size
哈希表 map
伪头部和伪尾部简化边界处理

关键操作实现

封装两个辅助函数：

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

登录后复制

get 操作逻辑：

查 map 是否存在 key
不存在返回 -1
存在则将其移到链表头部（表示最近使用），并返回值

put 操作逻辑：

如果 key 已存在，更新值并移到头部
如果不存在，新建节点插入头部
若超出容量，删除尾部节点（最久未使用）及 map 中对应项

完整代码示例

#include <unordered_map>
using namespace std;
<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;'>int capacity;
unordered_map<int, Node*> cache;
Node* head;
Node* tail;

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

void addToHead(Node* node) {
    node->prev = head;
    node->next = head->next;
    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) {
    auto it = cache.find(key);
    if (it == cache.end()) return -1;
    Node* node = it->second;
    moveToHead(node);
    return node->value;
}

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

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

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

登录后复制

};

这个实现保证了 get 和 put 都是 O(1) 时间复杂度，适合高频访问场景。注意手动管理内存或可改用智能指针。基本上就这些，不复杂但容易忽略细节比如指针连接顺序和析构处理。

以上就是c++++怎么实现一个LRU缓存淘汰算法_c++最近最少使用缓存机制实现的详细内容，更多请关注php中文网其它相关文章！