LRU 算法

LRU

简介

LRU算法，即最近最少使用算法，是一种常用的页面置换算法，用于管理缓存中的数据对象。它的核心思想是基于时间局部性原理，即最近被访问的数据在未来可能会被再次访问。当缓存空间不足时，LRU算法会淘汰最近最久未使用的数据对象。

算法原理

1. 通过固定长度的链表维护缓存数据的访问顺序
2. 最近使用过的或者新添加的数据放在链表的头部
3. 添加新的数据时超过链表长度，删除链表尾部数据
4. 存储键和链表迭代器的映射，用于快速查找链表中的数据。在使用get方法时，直接从哈希表中获取数据

实现

#ifndef LRU_HPP__ 
#define LRU_HPP__

#include <list>
#include <unordered_map>
#include <string>
#include <stdexcept>

namespace lru
{

// LRU缓存类
template<typename T>
class LruCache 
{
public:
    // 构造函数，初始化容量
    LruCache(int cap) : capacity(cap) {}

    // 获取缓存数据，如果键不存在则抛出异常
    T get(const std::string& key) 
    {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) 
        {
            throw std::runtime_error("Key not found");
        }
        // 将命中的元素移到链表头部
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        return it->second->value;
    }

    // 尝试获取缓存数据，如果键存在则返回true并赋值给result，否则返回false
    bool try_get(const std::string& key, T& result) 
    {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) 
        {
            return false;
        }
        // 更新最近使用的数据顺序
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        result = it->second->value;
        return true;
    }

    // 设置缓存数据，如果键已存在则更新值
    void set(const std::string& key, const T& value) 
    {
        auto it = cacheMap.find(key);
        
        // 键存在，更新值并将其移到列表前面
        if (it != cacheMap.end()) 
        {
            it->second->value = value;
            cacheList.splice(cacheList.begin(), cacheList, it->second);
        } 
        else 
        {
            // 缓存已满，移除最久未使用的元素
            if (cacheList.size() >= capacity) 
            {
                cacheMap.erase(cacheList.back().key);  // 从哈希表中删除
                cacheList.pop_back();                  // 从链表中删除
            }
            // 插入新键值对到链表头部
            cacheList.emplace_front(key, value);
            cacheMap[key] = cacheList.begin();
        }
    }

    // 返回缓存中存储的键值对数量
    int size() const 
    {
        return cacheList.size();
    }

    // 清空缓存
    void clear() 
    {
        cacheList.clear();
        cacheMap.clear();
    }

private:
    // 缓存节点结构体，包含键和值
    struct CacheNode 
    {
        std::string key;
        T value;
        CacheNode(const std::string& k, const T& v) : key(k), value(v) {}
    };

    // 定义链表类型：存储CacheNode的双向链表
    using ListType = std::list<CacheNode>;
    // 定义哈希表类型：存储键和链表迭代器的映射
    using MapType = std::unordered_map<std::string, typename ListType::iterator>;

    int capacity;    // 缓存容量
    ListType cacheList; // 双向链表，用于维护访问顺序
    MapType cacheMap;   // 哈希表，用于通过键快速查找链表节点
};


}


#endif  // LRU_HPP__