lru 缓存 c++

以下是使用C++实现LRU缓存的示例代码：

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

using namespace std;

class LRUCache {
private:
    unordered_map<int, pair<int, list<int>::iterator>> cache;
    list<int> keys;
    int capacity;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        keys.erase(cache[key].second);
        keys.push_front(key);
        cache[key].second = keys.begin();
        return cache[key].first;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            keys.erase(cache[key].second);
        }
        keys.push_front(key);
        cache[key] = { value, keys.begin() };
        if (cache.size() > capacity) {
            cache.erase(keys.back());
            keys.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;
}

LRUCache类中使用了一个哈希表来存储缓存的键值对，同时使用一个双向链表来存储缓存的键。在get方法中，如果缓存中存在该键，就将其移到链表头部并返回对应的值；如果不存在，就返回-1。在put方法中，如果缓存中已经存在该键，就将其移到链表头部并更新对应的值；如果不存在，就将该键值对插入到哈希表中，并将其放到链表头部。如果缓存超过了容量限制，就淘汰链表尾部的键值对。