如何用C++结合unordered_map和双向链表实现LRU缓存系统

LRU缓存即最近最少使用缓存，当缓存容量达到上限时，会优先淘汰最久未被访问的缓存数据。用C++实现LRU缓存时，结合unordered_map和双向链表可以同时满足查询、插入、删除操作的时间复杂度均为O(1)的需求，是工业界常用的实现方案。

核心设计思路

要实现高效的LRU缓存，需要解决两个核心问题：快速定位缓存节点，以及快速调整节点的访问顺序。具体的设计思路如下：

• 使用双向链表维护缓存节点的访问顺序，链表头部为最近访问的节点，尾部为最久未访问的节点。
• 使用unordered_map存储缓存键到双向链表节点的映射，实现O(1)时间复杂度的节点查找。
• 当缓存命中时，将对应节点移动到链表头部；当插入新节点时，若缓存未满则直接插入头部，若缓存已满则删除尾部节点后插入头部。

数据结构定义

首先定义双向链表的节点结构，每个节点需要存储缓存的键、值，以及前驱和后继指针：

// 双向链表节点定义
struct ListNode {
    int key;
    int value;
    ListNode* prev;
    ListNode* next;
    // 构造函数
    ListNode(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

然后定义LRU缓存类，包含容量、当前大小、哈希表、虚拟头尾节点等成员：

#include <unordered_map>
#include <iostream>

class LRUCache {
private:
    int capacity;               // 缓存容量
    int size;                   // 当前缓存大小
    std::unordered_map<int, ListNode*> cacheMap;  // 键到链表节点的映射
    ListNode* head;             // 虚拟头节点
    ListNode* tail;             // 虚拟尾节点

    // 辅助函数：将节点添加到链表头部
    void addToHead(ListNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    // 辅助函数：移除指定节点
    void removeNode(ListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // 辅助函数：将节点移动到头部
    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();
        tail = new ListNode();
        head->next = tail;
        tail->prev = head;
    }
};

核心功能实现

get 方法实现

get方法用于获取指定键的缓存值，如果该键存在，需要将对应的节点移动到链表头部，返回对应的值；如果不存在，返回-1。

int get(int key) {
    // 查找键是否存在于哈希表中
    if (cacheMap.find(key) == cacheMap.end()) {
        return -1;
    }
    // 找到对应节点，移动到头部
    ListNode* node = cacheMap[key];
    moveToHead(node);
    return node->value;
}

put 方法实现

put方法用于插入或更新缓存键值对，如果键已经存在，更新对应的值并将节点移动到头部；如果键不存在，创建新节点插入头部，若缓存已满则删除尾部节点。

void put(int key, int value) {
    // 键不存在的情况
    if (cacheMap.find(key) == cacheMap.end()) {
        ListNode* newNode = new ListNode(key, value);
        // 添加到哈希表和链表头部
        cacheMap[key] = newNode;
        addToHead(newNode);
        size++;
        // 缓存已满，删除尾部节点
        if (size > capacity) {
            ListNode* tailNode = removeTail();
            cacheMap.erase(tailNode->key);
            delete tailNode;
            size--;
        }
    } else {
        // 键已存在，更新值并移动到头部
        ListNode* node = cacheMap[key];
        node->value = value;
        moveToHead(node);
    }
}

完整测试代码

以下是完整的可运行测试代码，验证LRU缓存的功能是否符合预期：

int main() {
    LRUCache* cache = new LRUCache(2);
    cache->put(1, 1);
    cache->put(2, 2);
    std::cout << cache->get(1) << std::endl;  // 返回1
    cache->put(3, 3);                         // 该操作会使得键2被淘汰
    std::cout << cache->get(2) << std::endl;  // 返回-1
    cache->put(4, 4);                         // 该操作会使得键1被淘汰
    std::cout << cache->get(1) << std::endl;  // 返回-1
    std::cout << cache->get(3) << std::endl;  // 返回3
    std::cout << cache->get(4) << std::endl;  // 返回4
    delete cache;
    return 0;
}

复杂度分析

该实现的各项操作时间复杂度如下：

• get操作：unordered_map查找O(1)，移动节点O(1)，总复杂度O(1)。
• put操作：插入或更新节点O(1)，哈希表操作O(1)，总复杂度O(1)。
• 空间复杂度：O(capacity)，哈希表和双向链表存储的节点数量不超过缓存容量。

这种实现方式兼顾了查询和更新的效率，适合对性能要求较高的缓存场景，在实际的后端开发、中间件实现中都有广泛的应用。

LRU_cacheunordered_map双向链表C++修改时间：2026-06-28 08:51:33