LFU缓存需三组件协同实现O(1)操作：key_map映射key到list迭代器，freq_map按频次分组并维护LRU时序，Node含key/value/freq；仅哈希表+频次计数器会导致驱逐O(n)、同频次无法区分新旧、节点迁移遗漏。
LFU 缓存（Least Frequently Used）在高并发读写场景下，单纯用 std::map 或 std::unordered_map 加频次计数器无法做到 O(1) 时间复杂度的 get 和 put——必须同时维护「频次分组」和「组内访问时序」，否则删除最不常用项时会退化为 O(n)。
为什么不能只用哈希表 + 单独频次计数器
常见错误是：用 unordered_map<key, value> 存数据，再配一个 unordered_map<key, int> 记频次，get 时更新频次，put 满时遍历找最小频次键。这会导致：
-
put驱逐阶段需扫描全部 key，时间复杂度 O(n)，不符合 LFU 的理论要求 - 多个 key 频次相同时，无法区分「最近被访问」和「很久未访问」，违背 LFU 语义（应优先保留同频次下更热的）
- 频次更新后，旧频次链表节点没及时迁移，导致缓存行为错乱
核心结构：freq_map + list<list_node> + key_map
标准解法是三组件协同：
-
key_map：从 key 映射到链表节点指针（list<Node>::iterator），实现 O(1) 定位 -
freq_map：从频次（int）映射到该频次对应的双向链表（list<Node>），每条链表内按 LRU 排序（新访问插头，旧的留尾） - 每个
Node包含key、value、freq，且必须可被list迭代器稳定持有
关键点在于：每次 get 或 put 触发频次变化时，要把节点从 freq_map[freq] 中 unlink，再 insert 到 freq_map[freq+1] 头部；若原链表为空，直接 erase 对应 freq 键。
立即学习“C++免费学习笔记（深入）”；
如何避免迭代器失效与内存泄漏
std::list 的迭代器在插入/删除其他节点时不失效，但有两点极易出错：
- 用
list::erase(iterator)后，别再用该 iterator——尤其是你在freq_map[freq].erase(it)后还试图访问it->freq，此时 it 已无效 - 不要用 raw pointer 管理 Node 生命周期；统一用
list<Node>容器管理内存，所有key_map存的是list<Node>::iterator，而非Node* -
freq_map中的空链表要及时清理（freq_map.erase(freq)），否则min_freq可能卡在已无节点的频次上
示例片段（get 关键逻辑）：
if (key_map.find(key) == key_map.end()) return -1;
auto it = key_map[key];
int freq = it->freq;
freq_map[freq].erase(it);
if (freq_map[freq].empty()) {
freq_map.erase(freq);
if (min_freq == freq) min_freq++;
}
it->freq++;
freq_map[it->freq].push_front(*it);
key_map[key] = freq_map[it->freq].begin();
return it->value;
min_freq 怎么维护才不出错
min_freq 不是实时扫描得出的，而是靠「驱逐触发 + 频次链表清空联动」来维护：
- 初始化为 1，首次
put后仍为 1 -
get或put导致某频次链表变空，且该频次等于当前min_freq，则min_freq++ -
put新 key 时，如果缓存已满，就从freq_map[min_freq]尾部删一个（即同频次中最久未用的），删完若该链表为空，则min_freq++
注意：不能在每次 get 后重算 min_freq = min_element(freq_map.keys())，那是 O(F)，F 是不同频次数量，最坏仍是 O(n)。
真正难的不是写出来，而是边界 case：比如连续 put 填满、然后全 get 同一个 key、再 put 新 key，这时 min_freq 是否跳变正确，freq_map[1] 是否已被清空却没删掉……这些地方一漏，缓存就会漏删或误删。
