LRU算法c++

以下是一个简单的 C++ 实现 LRU 算法的例子：

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

using namespace std;

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

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        auto iter = cacheMap[key];
        int value = iter->second;
        cacheList.erase(iter);
        cacheList.push_front(make_pair(key, value));
        cacheMap[key] = cacheList.begin();
        return value;
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            auto iter = cacheMap[key];
            cacheList.erase(iter);
        }
        cacheList.push_front(make_pair(key, value));
        cacheMap[key] = cacheList.begin();
        if (cacheMap.size() > capacity) {
            auto lastPair = cacheList.back();
            cacheMap.erase(lastPair.first);
            cacheList.pop_back();
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // -1
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

LRU 算法利用哈希表和双向链表实现，其中哈希表用于快速查找，双向链表用于维护访问顺序。在 get 操作中，如果 key 不存在，返回 -1；否则将该 key 对应的节点移动到链表头部，并返回对应的 value 值。在 put 操作中，如果 key 已经存在，将对应的节点移到链表头部；否则将新的 key-value 对添加到链表头部，判断是否超过缓存容量，如果超过则删除链表尾部对应的 key-value 对。