std::unordered_map + std::list 组合在 lfu 中天然慢，因其查找最小非空桶需遍历所有桶，最坏 o(f)；而正确解法用双向链表维护升序频率桶 + freq_to_bucket 哈希映射，确保最小频率始终为链表头，实现严格 o(1) 查找与更新。

为什么 std::unordered_map + std::list 组合在 LFU 中天然慢

LFU 的核心瓶颈不是“计数”，而是“按频率查最小值 + 快速移动节点”。用 std::unordered_map 存 key→value/count，再用 std::list 按频率分桶，每次访问都要遍历所有桶找最低频非空桶——最坏 O(F)，F 是当前最大频率，完全不可接受。

真正可行的解法是：用一个全局有序结构维护“当前所有活跃频率”，且支持 O(1) 查最小、O(1) 增删。这不是靠堆（堆不支持 O(1) 删除任意节点），而是靠双向链表 + 频率到链表节点的反向映射。

• 每个频率对应一个 Bucket 节点，按频率升序串成双向链表
• freq_to_bucket_ 是 std::unordered_map<int bucket></int>，实现 O(1) 定位
• 新增频率时，只在链表尾插入；删除空桶时，直接 unlink，不遍历
• 最小频率永远是链表头，无需查找

如何保证 get/put 操作严格 O(1) 且无内存泄漏

关键在节点生命周期和指针管理。不能让 Bucket 和缓存项（CacheNode）互相持有裸指针，否则 unlink 时极易 dangling。正确做法是：所有节点统一由 std::list 管理内存，只存迭代器。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• key_to_node_ 映射 key → std::list<cachenode>::iterator</cachenode>，而非指针
• Bucket 结构里存 std::list<cachenode>::iterator</cachenode> 的集合（用 std::list<:list>::iterator></:list> 或更优的 std::unordered_set<:list>::iterator, IteratorHash></:list>）
• 每次 get(key)：先通过 key_to_node_ 找到原节点，取出其 freq，从旧 Bucket 的迭代器集合中 erase，再插入新频率对应的 Bucket；若新频率桶不存在，则创建并插入链表末尾
• 每次 put(key, value)：若已存在，同 get 流程更新；若不存在且满容量，从链表头（最小 freq）的 Bucket 中 pop_front 一个节点，并从 key_to_node_ 中 erase 对应 key

为什么不能用 std::priority_queue 实现 LFU 的 min-freq 查询

std::priority_queue 只能取 top，无法删除任意元素，也无法感知某个频率是否已变为空桶。当某个 Bucket 被清空后，堆里仍残留该频率，后续 pop 会拿到无效值，必须额外维护一个 lazy-delete 集合，反而破坏 O(1) 保证。

更严重的是：多个 key 共享同一频率时，std::priority_queue 无法区分“这个频率还有没有有效节点”。你没法在不 pop 的前提下检查堆顶频率是否 still valid。

• 错误示例：std::priority_queue<int std::vector>, std::greater<int>> min_freq_heap_</int></int> —— 插入重复频率，但删除时无法定位具体哪个频率实例
• 正确替代：双向链表 + freq_to_bucket_ map，空桶被删时直接从链表摘除，头节点永远可信
• 额外收益：LRU 层级可自然嵌套——每个 Bucket 内部用 list 维护访问时序，淘汰时取 front 即可

核心源码逻辑片段（无第三方依赖，C++17）

struct CacheNode {
    int key, value, freq;
    CacheNode(int k, int v) : key(k), value(v), freq(1) {}
};

struct Bucket {
    int freq;
    std::list<:list>::iterator> nodes; // 迭代器集合
    Bucket(int f) : freq(f) {}
};

class LFUCache {
    int capacity_;
    std::list<bucket> buckets_; // 频率升序链表
    std::unordered_map<int std::list>::iterator> key_to_node_;
    std::unordered_map<int std::list>::iterator> freq_to_bucket_;
    std::list<cachenode> cache_;

public:
    LFUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto it = key_to_node_.find(key);
        if (it == key_to_node_.end()) return -1;
        auto node_it = it->second;
        int old_freq = node_it->freq;
        int new_freq = old_freq + 1;

        // 从旧 bucket 移除
        auto& old_bucket = freq_to_bucket_.at(old_freq);
        old_bucket->nodes.remove(node_it);

        // 若旧 bucket 为空，删除它
        if (old_bucket->nodes.empty()) {
            freq_to_bucket_.erase(old_freq);
            buckets_.erase(old_bucket);
        }

        // 插入新 bucket
        auto new_bucket_it = freq_to_bucket_.find(new_freq);
        if (new_bucket_it == freq_to_bucket_.end()) {
            buckets_.emplace_back(new_freq);
            new_bucket_it = --buckets_.end();
            freq_to_bucket_[new_freq] = new_bucket_it;
        }
        new_bucket_it->second->nodes.push_back(node_it);
        node_it->freq = new_freq;

        return node_it->value;
    }

    void put(int key, int value) {
        if (capacity_ == 0) return;
        auto it = key_to_node_.find(key);
        if (it != key_to_node_.end()) {
            it->second->value = value;
            get(key); // 复用 get 逻辑更新 freq
            return;
        }

        // 新 key，检查容量
        if (key_to_node_.size() == capacity_) {
            // 淘汰链表头 bucket 中第一个 node
            auto& head_bucket = buckets_.front();
            auto node_it = head_bucket.nodes.front();
            key_to_node_.erase(node_it->key);
            cache_.erase(node_it);
            head_bucket.nodes.pop_front();

            if (head_bucket.nodes.empty()) {
                freq_to_bucket_.erase(head_bucket.freq);
                buckets_.pop_front();
            }
        }

        // 插入新节点
        cache_.emplace_back(key, value);
        auto node_it = --cache_.end();
        key_to_node_[key] = node_it;

        // 初始化为 freq=1
        auto& bucket_1 = freq_to_bucket_[1];
        if (bucket_1 == buckets_.end()) {
            buckets_.emplace_back(1);
            bucket_1 = --buckets_.end();
        }
        bucket_1->nodes.push_back(node_it);
    }
};
</cachenode></int></int></bucket></:list>

注意：真实工程中需补全 IteratorHash 特化（因 std::list::iterator 不可直接哈希），且 Bucket 中的 nodes 更宜用 std::unordered_set 加自定义 hash 避免 list::remove 的 O(n)。但上面逻辑已体现最小频率寻址优化的本质——链表头即答案，其余全是维护开销。真正的性能敏感点不在算法分支，而在迭代器拷贝与内存局部性：cache_ 和 buckets_ 应尽量紧凑，避免跨 cache line 访问。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！