c++实现LRU置换算法

### C++ 实现 LRU 缓存置换算法

为了实现基于 C++ 的 LRU (Least Recently Used) 缓存机制，可以采用多种方法。一种常见的做法是利用双向链表配合哈希映射来跟踪最近最少使用的项。

下面是一个简单的 C++ 实现例子：

#include <iostream>
#include <list>
#include <unordered_map>

template<typename K, typename V>
class LRUCache {
private:
    size_t capacity;
    std::list<std::pair<K, V>> cache;
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> map;

public:
    explicit LRUCache(size_t cap):capacity(cap){}

    void put(const K& key, const V& value){
        auto it = map.find(key);
        if(it != map.end()){
            cache.erase(it->second); // Remove old entry from list.
            map.erase(it);           // Erase corresponding hash table record.
        }
        
        cache.push_front(std::make_pair(key,value));
        map[key]=cache.begin();
        
        while(cache.size()>capacity){
            // When over capacity, remove least recently used item at back of deque.
            map.erase(cache.back().first);
            cache.pop_back();    
        }   
    }

    bool get(const K& key,V &value)const{
        auto it=map.find(key);
        if(it==map.cend())return false; // If not found.

        value=it->second->second;
        return true;
    }
};

此代码片段定义了一个模板类 `LRUCache` ，它接受两个参数作为键和值的数据类型[^1]。该结构体内部维护着一个双端队列用于存储缓存条目以及一个无序映射用来快速定位特定的缓存项目。当向缓存中添加新数据时 (`put`)，如果已经存在相同的键，则更新其对应的值并将其移动到最前面；否则创建新的记录放在列表前端。每当超出设定的最大容量(`capacity`)之后就会移除最后面也就是最早加入的那个元素。获取操作(`get`)会尝试找到指定键所关联的值，并返回是否成功找到了匹配的结果。