c++怎么实现一个LRU缓存淘汰算法_c++实现LRU缓存的思路与示例-C++-PHP中文网

c++怎么实现一个LRU缓存淘汰算法_c++实现LRU缓存的思路与示例

下次还敢

发布： 2025-11-01 05:39:30

原创

330人浏览过

LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)时间复杂度，最近访问节点置于链表头部，满时淘汰尾部最久未用节点。

c++怎么实现一个lru缓存淘汰算法_c++实现lru缓存的思路与示例

LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。为了高效实现，通常结合哈希表和双向链表，C++中可以用 unordered_map 和自定义的双向链表来完成。

基本思路

使用一个双向链表维护访问顺序，最近访问的节点放在链表头部，最久未访问的在尾部。同时用哈希表快速定位节点位置：

get(key)：若存在，返回值并将该节点移到链表头；否则返回 -1
put(key, value)：若已存在，更新值并移到头部；若不存在且缓存已满，删除尾部节点，插入新节点到头部

关键数据结构设计

定义双向链表节点和缓存容量：

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

登录后复制

成员变量包括：

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

头尾指针：方便插入删除
哈希表：unordered_map<int, ListNode*>
当前大小与最大容量

核心操作实现

封装两个辅助函数简化逻辑：

存了个图

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

查看详情

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

登录后复制

这两个函数用于调整节点位置，保证 O(1) 时间复杂度。

完整示例代码

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

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

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

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

ListNode* popTail() {
    ListNode* last = tail->prev;
    removeNode(last);
    return last;
}

登录后复制

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

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

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

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

~LRUCache() {
    for (auto& pair : cache) {
        delete pair.second;
    }
    delete head;
    delete tail;
}

登录后复制

};

使用示例

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;
}

登录后复制

基本上就这些。用哈希表加双向链表，能保证 get 和 put 都是 O(1) 时间复杂度，符合 LRU 的高效要求。注意手动管理内存或改用智能指针避免泄漏。

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