Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LRU缓存淘汰机制C++实现

LRU缓存淘汰机制C++实现

原创
作者头像
evenleo
修改于 2020-10-13 06:22:46
修改于 2020-10-13 06:22:46
8400
举报
文章被收录于专栏:C++的沉思C++的沉思

前言

LRU 是 Least Recently Used 的简写,字面意思是最近最少使用。

通常用于缓存的淘汰策略实现,由于缓存的内存非常宝贵,所以需要根据某种规则来剔除数据保证内存不被撑满。

代码实现

代码语言:txt
AI代码解释
复制
#ifndef _LRU_CACHE_H_
#define _LRU_CACHE_H_

#include <unordered_map>
/*
* LRU是Least Recently Used的简写,字面意思是最近最少使用,通常用于缓存淘汰策略
* 维护一个双向链表,并用无序关联式容器unordered_map存储链表的节点
*/
template <typename Key, typename Value>
class LRUCache {
private:
    struct Node {
        Key key;
        Value value;
        Node* prev;
        Node* next;
        Node(Key k, Value v)
            : key(k)
            , value(v)
            , prev(nullptr)
            , next(nullptr)
        {
        }
    };

public:
    LRUCache(size_t capacity)
        : capacity_(capacity)
        , head_(nullptr)
        , tail_(nullptr)
    {
    }
    ~LRUCache()
    {
        while (head_ != nullptr) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
    }

    /*
    * @brief 获取缓存值
    * 根据key获取value,不存在返回nullptr
    * 存在,则在双向链表中删除该节点,再将节点添加到表头
    */
    Value* get(Key key)
    {
        auto it = datas_.find(key);
        if (it == datas_.end()) {
            return nullptr;
        } else {
            Node* node = datas_[key];
            remove(node);
            appendHead(node);
            return &node->value;
        }
    }

    /*
    * @brief 将键值对放进缓存中
    * 缓存已存在,更新value,并在双向链表中删除该节点,再将节点添加到表头
    * 不存在,创建节点node,如果当前缓存大小小于缓存容量,直接将节点添加到
    * 表头即可,否则将双向链表的尾结点在关联式容器hashMap中删除,然后在双
    * 向链表中也删除尾节点,最后将新节点添加到表头和hashMap中
    */
    void put(Key key, Value value)
    {
        auto it = datas_.find(key);
        if (it != datas_.end()) {
            Node* node = it->second;
            node->value = value;
            remove(node);
            appendHead(node);
        } else {
            Node* node = new Node(key, value);
            if (datas_.size() < capacity_) {
                appendHead(node);
                datas_[key] = node;
            } else {
                datas_.erase(tail_->key);
                Node* delNode = tail_;
                remove(delNode);
                delete delNode;
                appendHead(node);
                datas_[key] = node;
            }
        }
    }

private:
    /*
    * 将节点添加到双向链表的头部
    */
    void appendHead(Node* node)
    {
        if (head_ == nullptr)
            head_ = tail_ = node;
        else {
            node->next = head_;
            head_->prev = node;
            head_ = node;
        }
    }

    /*
    * 在双向链表删除node节点,但不销毁节点,主要是为了其他方法可以通用
    */
    void remove(Node* node)
    {
        if (head_ == tail_) {
            head_ = tail_ = nullptr;
        } else if (head_ == node) {
            head_ = node->next;
            head_->prev = nullptr;
        } else if (tail_ == node) {
            tail_ = node->prev;
            tail_->next = nullptr;
        } else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }

        node->next = nullptr;
        node->prev = nullptr;
    }

private:
    size_t capacity_; // 缓存容量
    Node* head_; // 双向链表的头结点
    Node* tail_; // 双向链表的尾结点
    std::unordered_map<int, Node*> datas_; // 无序关联式容器
};

#endif

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
想进大厂、想提升底层功力、想搞懂LRU缓存,这一篇就够了!
历史题目:Ceph MDS 路径解析场景: 输入:/mnt/data/project1/report.docx 输出:逐级路径 ["mnt", "data", "project1", "report.docx"]
早起的鸟儿有虫吃
2025/07/10
460
想进大厂、想提升底层功力、想搞懂LRU缓存,这一篇就够了!
【LeetCode】146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
韩旭051
2021/01/07
4790
【LeetCode热题100】【链表】LRU缓存
我昨天面了天美L1的游戏客户端开发,面了我100分钟,问完实习、项目、计算机图形学和C++后给了我两道算法题做,一道是最长公共子序列,一道是LRU缓存,我知道是经典的题目,但是我都没敲过,我之前写过一个KV的数据库系统用过LRU(最近最少使用)缓存,用的是双向链表和哈希表解决的,当时是实现了一个双向链表,用来存储value,哈希表存储key和对应存储value的链表节点的指针,最近被访问的key就把它的节点移到链表头,超过容量就删掉链表尾
叶茂林
2024/03/31
1090
146. LRU 缓存机制
要在O(1)时间复杂度完成这两种操作,我们想到的使用HashMap来进行操作,而且参考LRUCache的特性,需要对元素进行移动或者删除,首选的是双向链表。
用户7447819
2021/07/23
3030
Leetcode|146. LRU 缓存机制(key2node哈希链表)
《Leetcode|146. LRU 缓存机制(key2node哈希链表)》 《Leetcode|460. LFU 缓存(KV+KF+FK哈希链表+minFreq)》
SL_World
2021/09/18
2170
146. LRU缓存机制 Krains 2020-08-05 12:50:28 链表
要想在O(1)时间内get到已存的值,可以使用哈希表,而哈希表存储键值是没有先后顺序的,因此就不能够在O(1)的时间内删除最久未使用的元素,可以采用双向链表,链表的优点是插入删除元素快,而且维护键值的先后顺序,我们结合哈希表和双向链表的优势,用哈希表结合双向链表方式实现LRU。
Krains
2020/08/06
3310
手写双向循环链表+LRU练习
这里我们将循环链表中的结点值采用key与val存储。其余的就比较easy了,相信看完非常容易理解。
公众号guangcity
2020/07/02
4320
【Leetcode】146.LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
Leetcode名企之路
2019/03/18
1.1K0
【Leetcode】146.LRU缓存机制
146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类: LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之
编程张无忌
2021/06/29
2410
漫谈 LevelDB 数据结构(三):LRU 缓存( LRUCache)
LRU 是工程中多见的一个数据结构,常用于缓存场景。近年来,LRU 也是面试中一道炙手可热的考题,一来工程用的多,二来代码量较少,三来涉及的数据结构也很典型。LeetCode 中有一道相应的题目:lru-cache。相对实际场景,题目进行了简化:本质上要求维护一个按访问时间有序的 kv 集合,且 kv 皆是整数。经典解法是使用一个哈希表(unordered_map)和一个双向链表,哈希表解决索引问题,双向链表维护访问顺序。这是我当时的一个解法,特点是用了两个辅助函数,并且可以返回节点自身,以支持链式调用,从而简化了代码。
木鸟杂记
2021/09/26
1.2K0
golang刷leetcode 经典(1) LRU缓存机制
设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作:获取数据 get 和 写入数据 put 。
golangLeetcode
2022/08/02
4430
LRU缓存
LRU 算法就是一种缓存淘汰策略,原理不难,但是面试中写出没有 bug 的算法比较有技巧,需要对数据结构进行层层抽象和拆解,本文就带你写一手漂亮的代码。
狼啸风云
2023/11/18
2390
昨天面试被问到的 缓存淘汰算法FIFO、LRU、LFU及Java实现
第一次请求时把计算好的结果存放在缓存中,下次遇到同样的请求时,把之前保存在缓存中的数据直接拿来使用。
万猫学社
2022/04/22
3510
146. LRU 缓存机制
什么是LRU? 很多时候尤其以前内存比较值钱的时候,我们空间比较宝贵,不会很大,那么就存在了重点数据和非重点数据,我们要在内存不够的时候有限保存重点数据淘汰非重点数据;LRU也就是说我们认为最近使用过的数据应该是重点数据,很久都没用过的数据应该是非重点数据,内存满了就优先删那些很久没用过的数据。 有哪些应用场景呢? 1.手机上划显示的任务列表,都是按照最近打开顺序排列的 2.redis的lru淘汰策略 思路: 1.利用linkedhashmap实现lru,因为其本身就存在lru策略,只需要
名字是乱打的
2021/12/23
2470
146. LRU 缓存机制
LeetCode 146. LRU缓存机制(哈希链表)
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
Michael阿明
2021/02/20
5370
LeetCode 146. LRU缓存机制(哈希链表)
LC146— LRU 缓存机制
146. LRU 缓存机制 难度中等1299 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类: LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存
Java架构师必看
2021/05/14
3800
图解LeetCode——146. LRU 缓存
那么针对第一个问题,我们可以采用哈希表或者数组的方式进行数据存储,因为本题的提示部分已经指出key值是在[0, 10000]区间内的,并不存在负数,所以为了提升执行速度,我们选择数组作为底层的存储结构。其中,需要注意的是,存储的value是下面要介绍的双向链表中的Node节点。
爪哇缪斯
2023/05/31
3230
图解LeetCode——146. LRU 缓存
Leetcode LRU 缓存机制
缓存是一种提高数据读取性能的技术,在计算机中cpu和主内存之间读取数据存在差异,CPU和主内存之间有CPU缓存,而且在内存和硬盘有内存缓存。当主存容量远大于CPU缓存,或磁盘容量远大于主存时,哪些数据应该被应该被清理,哪些数据应该被保留,这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
用户10384376
2023/02/25
3350
Leetcode LRU 缓存机制
聊聊缓存淘汰算法-LRU 实现原理
我们常用缓存提升数据查询速度,由于缓存容量有限,当缓存容量到达上限,就需要删除部分数据挪出空间,这样新数据才可以添加进来。缓存数据不能随机删除,一般情况下我们需要根据某种算法删除缓存数据。常用淘汰算法有 LRU,LFU,FIFO,这篇文章我们聊聊 LRU 算法。
andyxh
2019/10/30
8490
聊聊缓存淘汰算法-LRU 实现原理
最常见面试算法之 LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU(最近最少使用)缓存机制。它应该支持以下操作:
阿宝哥
2020/02/14
1.8K0
最常见面试算法之 LRU 缓存机制
相关推荐
想进大厂、想提升底层功力、想搞懂LRU缓存,这一篇就够了!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档