c++如何实现一个高效的LRU缓存_c++缓存淘汰算法设计与实现-C++-PHP中文网

c++如何实现一个高效的LRU缓存_c++缓存淘汰算法设计与实现

尼克

发布： 2025-12-05 12:21:38

原创

285人浏览过

答案：通过哈希表和双向链表结合实现LRU缓存，get和put操作均达到O(1)时间复杂度，利用哈希表快速查找，双向链表维护访问顺序，最新访问节点移至头部，淘汰时从尾部删除，确保高效性。

c++如何实现一个高效的lru缓存_c++缓存淘汰算法设计与实现

实现一个高效的LRU（Least Recently Used）缓存，核心在于快速访问数据的同时维护访问顺序，使得最久未使用的元素能被快速淘汰。C++中可以通过结合哈希表和双向链表来达到O(1)的插入、查找和删除效率。

LRU缓存的基本原理

LRU缓存根据“最近最少使用”原则管理有限容量的数据。当缓存满时，优先淘汰最久未访问的条目。为了高效实现这一机制，需要：

快速查找某个key是否在缓存中 —— 使用哈希表（unordered_map）
维护访问顺序，支持快速移动或删除节点 —— 使用双向链表（自定义或list）

将两者结合：哈希表存储key到链表节点的指针映射，链表按访问时间排序，最新访问的放在头部，淘汰从尾部进行。

数据结构设计

定义双向链表节点和缓存主体结构：

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

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

登录后复制

缓存类包含：

哈希表：unordered_map 快速定位节点
双向链表头尾指针：方便在首尾操作
容量限制：capacity
当前大小：size

关键操作实现

主要接口为 get 和 put：

畅图

AI可视化工具

179

查看详情

get(int key)：

若key不存在，返回-1
存在则将其对应节点移到链表头部（表示最新使用），并返回value

put(int key, int value)：

如果key已存在，更新value并移至头部
如果不存在且缓存已满，删除尾部节点（最久未用），同时从哈希表中移除
创建新节点插入头部，并加入哈希表

辅助函数用于简化链表操作：

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

登录后复制

完整代码示例

#include <unordered_map>
<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;'>std::unordered_map<int, ListNode*> cache;
ListNode *head, *tail;
int capacity, size;

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

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

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

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

登录后复制

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

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

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()) {
        ListNode* node = it->second;
        node->value = value;
        moveToHead(node);
    } else {
        ListNode* newNode = new ListNode(key, value);
        cache[key] = newNode;
        addToHead(newNode);
        ++size;
        if (size > capacity) {
            ListNode* removed = removeTail();
            cache.erase(removed->key);
            delete removed;
            --size;
        }
    }
}

登录后复制

};

这个实现保证了 get 和 put 操作均为 O(1) 时间复杂度，适合高频读写场景。

基本上就这些。只要理解哈希表+双向链表的配合逻辑，LRU 就不难实现。注意内存释放和指针操作的正确性即可。

以上就是c++++如何实现一个高效的LRU缓存_c++缓存淘汰算法设计与实现的详细内容，更多请关注php中文网其它相关文章！