c++中如何实现简单的LRU淘汰策略_c++双向链表与哈希表结合【详解】

必须用双向链表+哈希表组合：双向链表支持O(1)节点移动与删除，哈希表提供key到节点迭代器的O(1)索引；单独list无法O(1)定位，单独unordered_map无法维护时序。

为什么必须用双向链表 + 哈希表组合

单靠 std::list 无法在 O(1) 时间定位某个 key 对应的节点位置；单靠 std::unordered_map 又无法维护访问时序。LRU 的核心操作——“访问即置顶”和“淘汰尾部”——要求：查找快（O(1)）、移动快（O(1)）、删除快（O(1)）。只有双向链表支持任意节点的常数时间摘除与插入，而哈希表提供 key 到链表节点指针的直接映射。

如何设计节点与容器结构

不能直接存 std::list<:pair v>>，因为 erase() 需要迭代器，

而哈希表里得存这个迭代器。正确做法是：哈希表值类型为 std::list::iterator，Node 为自定义结构体，含 key 和 value。这样每次访问 key 时，能用哈希表 O(1) 拿到对应节点的迭代器，再用 splice() 把它移到链表头部。

• std::list 存储所有活跃项，头为最近使用，尾为最久未用
• std::unordered_map::iterator> 提供 key → 节点位置的直连索引
• 每次 get() 或 put() 都要调用私有函数 moveToHead(iterator)，用 splice(head_iter, list, it) 实现零拷贝移动

put() 中淘汰逻辑怎么写才不漏判

淘汰只发生在 put() 且容量超限时，但要注意两种情况都得处理：key 已存在（更新 value 并刷新位置），key 不存在（插入新节点并可能淘汰）。容易出错的是：先 insert 再检查 size，导致实际 size 超过 capacity + 1 才删——这会让缓存短暂溢出。

void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
        cache[key]->value = value;
        moveToHead(cache[key]);
        return;
    }
    Node node{key, value};
    lru_list.push_front(node);
    cache[key] = lru_list.begin(); // 迭代器有效
    if (cache.size() > capacity) {
        int tail_key = lru_list.back().key;
        lru_list.pop_back();
        cache.erase(tail_key); // 必须先删链表再删 map，否则迭代器失效
    }
}

迭代器失效是最大陷阱

std::list 的迭代器只有在对应节点被 erase() 时才失效；push_front()、splice()、pop_back() 都不使其他迭代器失效。但一旦你对某个节点调用了 erase()，所有指向它的迭代器立刻变悬垂指针。所以 cache.erase(tail_key) 必须在 lru_list.pop_back() 之后——否则你拿着一个刚被删节点的迭代器还试图从 map 里删它，行为未定义。

另一个常见错误：用 auto it = lru_list.begin(); lru_list.erase(it); 后继续用 it ——哪怕只是打印，也属于未定义行为。所有涉及 erase 的地方，务必确认后续不再使用该迭代器。