lru算法c++实现

LRU (Least Recently Used)算法是一种缓存淘汰策略，通常用于缓存中的数据管理。下面是C++实现：

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

using namespace std;

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

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

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        } else {
            // 将访问过的节点移到链表头部
            lruList.splice(lruList.begin(), lruList, cache[key]);
            return cache[key]->second;
        }
    }

    void put(int key, int value) {
        if (cache.find(key) == cache.end()) {
            // 判断容量是否已满
            if (lruList.size() == capacity) {
                int delKey = lruList.back().first;
                lruList.pop_back();
                cache.erase(delKey);
            }
            lruList.push_front(make_pair(key, value));
            cache[key] = lruList.begin();
        } else {
            // 更新节点值，并将节点移到链表头部
            cache[key]->second = value;
            lruList.splice(lruList.begin(), lruList, cache[key]);
        }
    }
};

int main() {
    LRUCache cache(2); // 容量为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;
}

LRUCache类中使用了一个哈希表cache和一个双向链表lruList。哈希表用于存储缓存中的键值对，双向链表用于按照访问顺序存储键值对。在get方法中，如果key不存在于哈希表中，则返回-1；否则将访问过的节点移到链表头部，并返回节点的值。在put方法中，如果key不存在于哈希表中，则判断缓存是否已满，若已满则删除链表尾部的节点，并删除哈希表中对应的键值对，然后将新的键值对插入到链表头部，并在哈希表中添加新的键值对；如果key已存在于哈希表中，则更新节点的值，并将访问过的节点移到链表头部。