LRU算法实现c++

以下是LRU算法的C++实现：

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

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }
        // 将当前访问的节点移到链表头部，并更新哈希表中该节点的地址
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        it->second = cacheList.begin();
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            // 如果 key 已经存在，先删除旧的节点
            cacheList.erase(it->second);
        }
        // 插入新节点到链表头部，并在哈希表中添加该节点
        cacheList.push_front(make_pair(key, value));
        cache[key] = cacheList.begin();
        // 如果超出缓存容量，删除链表尾部节点，并在哈希表中删除对应的项
        if (cache.size() > cap) {
            int k = cacheList.rbegin()->first;
            cacheList.pop_back();
            cache.erase(k);
        }
    }

private:
    int cap;
    list<pair<int, int>> cacheList;
    unordered_map<int, list<pair<int, int>>::iterator> cache;
};

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，因为缓存中已经删除了 key 为 2 的项
    cache.put(4, 4);
    cout << cache.get(1) << endl; // 输出 -1，因为缓存中已经删除了 key 为 1 的项
    cout << cache.get(3) << endl; // 输出 3
    cout << cache.get(4) << endl; // 输出 4

    return 0;
}