直接用 std::map + std::list 实现 LFU 易超时，因删除最低频节点需可能遍历全部频率，且 std::list 不支持 O(1) 定位前驱导致任意节点删除非 O(1)。
为什么直接用 std::map + std::list 实现 LFU 容易超时
LFU 要求每次 get 或 put 都能 O(1) 更新频率并找到最低频且最久未用的节点。如果用 std::map 存频率到节点链表的映射，再额外维护一个 minFreq，看似可行——但问题出在「删除最低频节点」时：你得先查 freqMap[minFreq] 是否为空，为空就得 ++minFreq 再查，最坏可能遍历全部频率值；更麻烦的是，std::list 不支持 O(1) 删除任意迭代器指向的节点（除非你持有其前驱），而你只有 key 对应的 value 指针，无法反向定位前驱。
freqList 必须是双向链表 + 每个节点带 freq 字段
核心破局点在于：不按频率分桶管理链表，而是让整个缓存本身是一条双向链表，每个节点显式记录自己的 freq，同时维护一个 freq2head 映射（unordered_map）指向每个频率的**最新插入节点**（即该频率下最年轻节点）。这样：
-
get(key)时，先从key2node找到节点，将其从原频率链位置摘下，再插到freq+1链的头部（若freq+1无头，则新建） -
put(key, value)若满，需淘汰：直接取freq2head[minFreq]的尾节点（即该频率下最老节点），它必然满足「最低频 & 最久未用」 -
minFreq只在put新增节点且触发淘汰时更新：若删完后freq2head[minFreq]对应链空了，就 ++minFreq
为什么不能只靠 freq 排序，必须结合插入/访问时间戳
纯按 freq 升序排序会导致同频节点无法区分新旧——比如两个节点都是 freq=2，但一个刚被 get 过，另一个是上次 put 进来的，后者应优先淘汰。标准解法是：同频节点在链表中按**最近访问时间倒序排列**（新访问的插在头部），这样每条频率链天然是 LRU 行为。所以淘汰时取该链尾部，就是同频中最老的那个。
实现上无需存真实时间戳，只要保证「同频下，后 get / put 的节点一定比先的更靠近链头」即可。这通过每次更新都把节点移到对应 freq 链头部来达成。
关键细节：节点移动时如何避免重复分配内存
每次 get 都要将节点从旧 freq 链摘下、挂到新 freq 链头，若每次都 new/delete，性能崩盘。正确做法是：
- 所有节点在构造
LFUCache时一次性 malloc 一块连续内存（或用std::vector预分配），用 free list 管理可用节点 - 节点结构里存
prev/next指针，以及key/value/freq，不带虚函数、不依赖 RTTI - 摘链操作仅改指针：
oldPrev->next = oldNext; oldNext->prev = oldPrev;，插链同理 -
key2node是unordered_map，值为裸指针，不负责生命周期
这样所有操作全是指针搬运，无内存分配开销，实测比 map+list 快 3–5 倍。
真正难的不是写对逻辑，而是确保 minFreq 更新时机精准、同频链的头尾维护不出错、以及节点复用时 prev/next 清零——这几个地方一错，缓存就会漏删或误删。建议在 removeNode() 和 addToHead() 里加 assert 检查前后指针是否自洽。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
