LRU
简介
LRU算法，即最近最少使用算法，是一种常用的页面置换算法，用于管理缓存中的数据对象。它的核心思想是基于时间局部性原理，即最近被访问的数据在未来可能会被再次访问。当缓存空间不足时，LRU算法会淘汰最近最久未使用的数据对象。
算法原理
- 通过固定长度的链表维护缓存数据的访问顺序
- 最近使用过的或者新添加的数据放在链表的头部
- 添加新的数据时超过链表长度，删除链表尾部数据
- 存储键和链表迭代器的映射，用于快速查找链表中的数据。在使用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__
