C++怎么实现一个LRU缓存淘汰算法_C++数据结构设计与LRU Cache实现

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

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

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1; // 未命中

        // 命中，将该元素移到链表头部
        used.splice(used.begin(), used, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            // 已存在，更新值并移到头部
            it->second->second = value;
            used.splice(used.begin(), used, it->second);
            return;
        }

        // 新插入，检查是否超容
        if (cache.size() >= capacity) {
            int old_key = used.back().first;
            cache.erase(old_key);
            used.pop_back();
        }

        // 插入新节点到链表头部
        used.emplace_front(key, value);
        cache[key] = used.begin();
    }
};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    std::cout << lru.get(1) << "\n"; // 输出 1
    lru.put(3, 3);                    // 淘汰 key=2
    std::cout << lru.get(2) << "\n"; // 输出 -1
    return 0;
}