实现一个 LRU 缓存

缓存满了，应该移除谁

内存比慢速存储快，但容量有限。缓存需要一条明确的规则，在空间不足时决定移除哪些内容。操作系统课程里常见 OPT、FIFO、LRU、Clock 和 LFU；这里聚焦 LRU 的行为与实现，其他策略也值得了解，因为理解适用条件比背下一种算法更重要。

LRU 是 Least Recently Used，意为“最近最少使用”：优先淘汰最久没有被访问的条目。

Reference sequence: 4 3 4 2 3 1 4 2
Cache capacity: 3 entries

Load 4: 4
Load 3: 3 4
Load 4: 4 3
Load 2: 2 4 3
Load 3: 3 2 4
Load 1: 1 3 2  (4 is the least recently used, so it is evicted)
Load 4: 4 1 3
Load 2: 2 4 1

示例中左侧表示最近使用。访问已有条目，就把它移到最前面；插入新条目时，如果容量已满，先删除最后一个，再将新条目放到最前面。

需要哪些操作

初始化时确定容量。读取时，命中就返回值并更新访问顺序；未命中则报告不存在。写入已有 key 时更新值并前移；写入新 key 时按需淘汰，再插入。

读和写都会把一个节点提升到最前面，这个动作应当复用。要让这些操作高效，需要同时解决两个问题：快速按 key 找到条目，以及快速修改它在访问顺序中的位置。

为什么是哈希表加双向链表

链表擅长维护顺序，但单独使用时，按 key 查找仍然需要线性扫描。哈希表可以将 key 直接映射到链表节点，提供平均常数时间查找。

单向链表不够直接：删除任意节点或尾节点时，需要知道前驱。通过交换节点内容来绕过前驱查找，又会破坏外部 key 到节点的映射关系。双向链表同时保留前后关系，适合把任意节点前移，也适合从尾部淘汰。

使用 STL 实现

std::list 管理双向链表及其节点生命周期，unordered_map 保存节点迭代器。已知迭代器时，可以常数时间移动或删除节点；加上哈希查找，整体操作具有平均常数时间复杂度。

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    using Entry = pair<int, int>;
    using RecencyList = list<Entry>;

    size_t capacity;
    RecencyList recency;
    unordered_map<int, RecencyList::iterator> entries;

public:
    explicit LRUCache(size_t capacity): capacity(capacity) {}

    int get(int key) {
        auto found = entries.find(key);
        if (found == entries.end()) {
            return -1;
        }

        recency.splice(recency.begin(), recency, found->second);
        return found->second->second;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        auto found = entries.find(key);
        if (found != entries.end()) {
            found->second->second = value;
            recency.splice(recency.begin(), recency, found->second);
            return;
        }

        recency.emplace_front(key, value);
        entries[key] = recency.begin();

        if (entries.size() > capacity) {
            const int evictedKey = recency.back().first;
            entries.erase(evictedKey);
            recency.pop_back();
        }
    }
};

链表保存新旧顺序，哈希表负责定位。splice 把已有节点移到表头，不重新分配节点，也不会让它的迭代器失效。新增和淘汰必须同步更新两份结构；容量为零时，缓存始终为空。

示例使用 -1 表示未命中，适合题目约束。若作为通用组件，应考虑返回 std::optional<int>，让所有整数都能作为有效缓存值。

真正需要保持的不变量只有两个：每个 key 恰好对应一个链表节点；链表顺序始终反映最近一次有效访问。实现细节应围绕这两个约定展开。