LRU

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

using namespace std;

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

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            // 更新访问顺序
            lruList.splice(lruList.begin(), lruList, cache[key].second);
            return cache[key].first;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // 如果已经存在，更新值并更新访问顺序
            cache[key].first = value;
            lruList.splice(lruList.begin(), lruList, cache[key].second);
        } else {
            // 如果不存在，插入新值
            if (cache.size() >= capacity) {
                // 移除最久未使用的元素
                int lruKey = lruList.back();
                cache.erase(lruKey);
                lruList.pop_back();
            }
            // 插入新元素
            lruList.push_front(key);
            cache[key] = {value, lruList.begin()};
        }
    }
};

int main() {
    LRUCache lruCache(2);

    lruCache.put(1, 1);
    lruCache.put(2, 2);
    cout << lruCache.get(1) << endl; // 输出 1
    lruCache.put(3, 3);
    cout << lruCache.get(2) << endl; // 输出 -1，因为键 2 不再缓存中
    lruCache.put(4, 4);
    cout << lruCache.get(1) << endl; // 输出 -1，因为键 1 不再缓存中
    cout << lruCache.get(3) << endl; // 输出 3
    cout << lruCache.get(4) << endl; // 输出 4

    return 0;
}

实现说明：

• LRUCache 类：通过双向链表 lruList 记录访问顺序，哈希表 cache 用于快速查找键值对。

• 构造函数：初始化缓存容量 capacity。

• get 方法：根据给定的键 key 返回对应的值。如果存在于缓存中，则将其移到链表头部表示最近使用；否则返回 -1。

• put 方法：插入或更新缓存。如果键已存在，则更新其值，并将其移到链表头部。如果缓存达到容量上限，则淘汰最近最少使用的元素，并在链表头部插入新元素。

• main 函数：示例展示了如何使用 LRUCache 类，进行插入、获取操作，并验证LRU算法的正确性。

这个实现基于哈希表和双向链表实现了高效的LRU缓存，保证了O(1)时间复杂度的get和put操作。