【深度笔记】LRU Cache

因为经常使用LRU（Least Recently Used，最近最少使用）或其他缓存替换策略来管理存储在KV Cache中的数据，保证高效的数据访问。在Transformer等深度学习模型中，KV Cache被广泛应用于存储Self-Attention机制中的中间计算结果，如注意力权重和值。

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

using namespace std;

class LRUCache {
private:
    int capacity;
    unordered_map<int, pair<int, list<int>::iterator>> cacheMap;
    list<int> lruList;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        // Move accessed key to the front of the list (most recently used)
        lruList.splice(lruList.begin(), lruList, cacheMap[key].second);
        return cacheMap[key].first;
    }
    
    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            // Update existing key, move it to the front of the list
            lruList.splice(lruList.begin(), lruList, cacheMap[key].second);
            cacheMap[key].first = value;
        } else {
            if (cacheMap.size() >= capacity) {
                // Evict least recently used key
                int lruKey = lruList.back();
                lruList.pop_back();
                cacheMap.erase(lruKey);
            }
            // Insert new key-value pair
            lruList.push_front(key);
            cacheMap[key] = {value, lruList.begin()};
 

实现了一个简单的LRU缓存，使用了一个双向链表 lruList 来维护访问顺序，以及一个 unordered_map cacheMap 用来存储键值对和对应的链表迭代器。