专栏首页C++的沉思LRU缓存淘汰机制C++实现
原创

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

前言

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

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

代码实现

#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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++多线程如何获取真正安全的单例

    如果你认为有两种可能,1、2和3、4的话,那说明你是按典型的程序员思维看问题的--没有像编译器和处理器一样处理问题。事实上, 1、4也是一种可能的结果。有两个基...

    evenleo
  • C++ string实现

    作为C++从业者,我相信都会被考察过实现简单的string类,包括构造、析构、拷贝构造以及赋值拷贝等,因为这能够很好的考察面试者的C++基本功。借看《剑指off...

    evenleo
  • C++实现epoll echo服务器

    通常来说,实现处理tcp请求,为一个连接一个线程,在高并发的场景,这种多线程模型与Epoll相比就显得相形见绌了。epoll是linux2.6内核的一个新的系统...

    evenleo
  • 二叉树遍历(Python)

    https://github.com/Coxhuang/binary-tree-traversal

    Coxhuang
  • 【一天一大 lee】二叉树的前序遍历 (难度:中等) - Day20201027

    前端小书童
  • openshift/origin工作记录(5)——node节点系统资源预留

    解决思路为设置node节点系统资源预留值。

    胡了了
  • 【面试现场】如何在500w个单词中统计特定前缀的单词有多少个?

    题目:我有500w个单词,你帮忙设计一个数据结构来进行存储,存好之后,我有两个需求。

    帅地
  • openshift/origin工作记录(5)——node节点系统资源预留

    实际应用中发现,如果不做处理,当集群内应用数量不断增加时,会占满node节点的系统资源,导致某node节点挂掉,同时也会造成openshift集群的卡死。

    胡了了
  • Python 序列化数据

    嘉美伯爵
  • 条件语句/变量和基本数据类型

    在32位机器上,整数的位数为32位,取值范围为-2**31~2**31-1,即-2147483648~2147483647   在64位系统上,整数的位数为64...

    py3study

扫码关注云+社区

领取腾讯云代金券