c++怎么实现一个LRU缓存淘汰算法_c++ LRU缓存实现方法-C++-PHP中文网

c++怎么实现一个LRU缓存淘汰算法_c++ LRU缓存实现方法

尼克

发布： 2025-10-04 21:01:02

原创

977人浏览过

LRU缓存通过哈希表和双向链表实现O(1)操作，最近访问节点移至头部，超出容量时删除尾部节点。

c++怎么实现一个lru缓存淘汰算法_c++ lru缓存实现方法

LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。在 C++ 中，我们可以通过 哈希表 + 双向链表 的组合高效实现 LRU 缓存，使得 get 和 put 操作的时间复杂度都为 O(1)。

基本设计思路

使用以下两个数据结构协同工作：

std::unordered_map：用于快速查找缓存中的键，映射 key 到链表中的节点指针。
双向链表：维护访问顺序，最近使用的放在头部，最久未使用的在尾部，便于快速删除和插入。

每次访问某个 key，就将其移动到链表头部；插入新元素时，若超出容量，则删除尾部节点。

节点结构与类定义

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

登录后复制

定义 LRU 缓存类：

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

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, ListNode*> cache;
    ListNode* head; // 哨兵头节点
    ListNode* tail; // 哨兵尾节点
<pre class='brush:php;toolbar:false;'>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* removeTail() {
    ListNode* node = tail->prev;
    removeNode(node);
    return node;
}

登录后复制

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

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

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* tailNode = removeTail();
            cache.erase(tailNode->key);
            delete tailNode;
        }
    }
}

登录后复制

};

存了个图

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

查看详情

使用示例

简单测试代码：

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) 时间复杂度，符合高频访问场景的需求。通过哨兵节点简化了边界判断，代码更清晰稳定。

基本上就这些，核心是理解哈希表定位 + 双向链表维护顺序的协作机制。不复杂但容易忽略细节，比如指针连接、内存释放等。实际项目中也可考虑用 std::list 替代手动管理链表，进一步简化逻辑。

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