17370845950

LRU用std::list+std::unordered_map实现，通过链表维护访问时序（最新在头、淘汰尾部），map存key到链表迭代器的映射，确保get/put均为O(1)；LFU需按频次分桶，每桶内LRU管理，辅以minFreq优化淘汰；不用std::map因其实现为红黑树，查找O(log n)，不满足缓存高频O(1)要求。

LRU 用 std::list + std::unordered_map 实现最简可靠版本

核心是维护「访问时序」：最新访问的放链表头，淘汰时删尾部。不能只靠 map 记 key-value，必须用双向链表快速移动节点位置。

• std::list<:pair int>> 存 {key, value}，支持 O(1) 删除任意节点和 push_front
• std::unordered_map>::iterator> 快速定位 key 对应的链表迭代器
• 每次 get()：查 map → 找到则从 list 中 erase 原位置，再 push_front()，更新 map 中迭代器
• 每次 put()：若 key 已存在，同上更新；否则检查容量，满则先 pop_back() 并删 map 中对应 key，再插入新节点

class LRUCache {
    int cap;
    std::list> cache;
    std::unordered_map>::iterator> map;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto it = map[key];
        int val = it->second;
        cache.erase(it);
        cache.push_front({key, val});
        map[key] = cache.begin();
        return val;
    }
    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            cache.erase(map[key]);
        } else if (cache.size() >= cap) {
            auto last = cache.back();
            map.erase(last.first);
            cache.pop_back();
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
};

LFU 需要频率分组 + 双向链表嵌套，std::unordered_map 套 std::list 是关键结构

LFU 淘汰最低频且最久未用的项，光记 frequency 不够 —— 同频次下还得有访问时序。所以得按 freq 分桶，每桶内用 LRU 方式管理（即链表），再用 map 索引每个 key 所在的桶和节点。

• 外层：std::unordered_map>，key 是 frequency，value 是该频次下所有 Node{key, value, freq} 的链表
• 中间：std::unordered_map::iterator, int>>，记录 key → {所在链表迭代器, 当前 freq}
• 还需一个 int minFreq，用于 O(1) 找到待淘汰桶（避免遍历所有 freq）
• get()：查 key → 得到 oldFreq；从 oldFreq 桶中删除节点；插入到 oldFreq + 1 桶头；若 oldFreq 桶空且等于 minFreq，则 minFreq++
• put()：若 key 存在，同 get() 更新；否则新建 Node 插入 freq=1 桶，minFreq = 1；若超容，删 minFreq 桶尾节点

为什么不用 std::map 替代 std::unordered_map？性能差在哪

std::map 是红黑树，O(log n) 查找；而缓存操作要求 O(1) 定位，尤其在高并发或高频调用场景下，log n 会明显拖慢吞吐。实测百万次 get()，unordered_map 比 map 快 3–5 倍。

• 除非你需要按 key 排序（LFU/LRU 都不需要），否则无理由选 std::map
• unordered_map 的哈希冲突在负载因子 .reserve(n) 避免 rehash
• 注意自定义 key 类型需提供 hash 和 ==，内置类型如 int、string 已内置

容易被忽略的边界：迭代器失效与 list::splice() 的正确用法

直接 erase() 再 push_front() 看似自然，但对 list 迭代器来说，erase 后原迭代器立即失效 —— 而 map 里还存着它，下次访问就 UB。正确做法是用 splice() 移动节点，不破坏迭代器有效性。

立即学习“C++免费学习笔记（深入）”；

• 错误写法：cache.erase(it); cache.push_front(...); map[key] = cache.begin(); → it 已失效，但 map 未清，后续可能解引用野指针
• 正确写法（LRU）：cache.splice(cache.begin(), cache, it); map[key] = cache.begin(); → splice 是移动，it 仍有效
• LFU 中跨桶移动也必须用 splice，否则旧桶 erase 后，map 中保存的迭代器指向已销毁内存

实际写 LFU 时，minFreq 的维护和空桶清理最容易漏；哪怕只少一行 if (buckets[oldFreq].empty()) minFreq = std::min(minFreq, oldFreq + 1);，都会导致后续淘汰错对象。