LRU

簡介

LRU算法湾揽，即最近最少使用算法旅挤，是一種常用的頁面置換算法踢关，用于管理緩存中的數(shù)據(jù)對象伞鲫。它的核心思想是基于時間局部性原理粘茄，即最近被訪問的數(shù)據(jù)在未來可能會被再次訪問。當(dāng)緩存空間不足時，LRU算法會淘汰最近最久未使用的數(shù)據(jù)對象柒瓣。

算法原理

1. 通過固定長度的鏈表維護緩存數(shù)據(jù)的訪問順序
2. 最近使用過的或者新添加的數(shù)據(jù)放在鏈表的頭部
3. 添加新的數(shù)據(jù)時超過鏈表長度儒搭，刪除鏈表尾部數(shù)據(jù)
4. 存儲鍵和鏈表迭代器的映射，用于快速查找鏈表中的數(shù)據(jù)芙贫。在使用get方法時搂鲫，直接從哈希表中獲取數(shù)據(jù)

實現(xiàn)

#ifndef LRU_HPP__ 
#define LRU_HPP__

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

namespace lru
{

// LRU緩存類
template<typename T>
class LruCache 
{
public:
    // 構(gòu)造函數(shù)，初始化容量
    LruCache(int cap) : capacity(cap) {}

    // 獲取緩存數(shù)據(jù)磺平，如果鍵不存在則拋出異常
    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;
    }

    // 嘗試獲取緩存數(shù)據(jù)魂仍，如果鍵存在則返回true并賦值給result，否則返回false
    bool try_get(const std::string& key, T& result) 
    {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) 
        {
            return false;
        }
        // 更新最近使用的數(shù)據(jù)順序
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        result = it->second->value;
        return true;
    }

    // 設(shè)置緩存數(shù)據(jù)拣挪，如果鍵已存在則更新值
    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();
        }
    }

    // 返回緩存中存儲的鍵值對數(shù)量
    int size() const 
    {
        return cacheList.size();
    }

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

private:
    // 緩存節(jié)點結(jié)構(gòu)體菠劝，包含鍵和值
    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;   // 哈希表，用于通過鍵快速查找鏈表節(jié)點
};


}


#endif  // LRU_HPP__