std::list + std::unordered_map 实现 LRU 易因迭代器失效出错：splice/erase 后 map 中迭代器未同步更新会导致未定义行为；正确做法是 map 存 list::iterator，所有操作原子化，且 put 时须先 pop_front 再 erase map。
为什么 std::list + std::unordered_map 实现 LRU 容易出错
直接用 std::list 存值、std::unordered_map 存迭代器的组合，看似经典，实则踩坑密集。最常见的是迭代器失效：当 std::list 发生 splice 或 erase 时，若 map 中缓存的迭代器未同步更新，后续 erase 会触发未定义行为。
正确做法是只存 std::list<t>::iterator</t>，且所有修改必须原子化：
- 每次
get()调用后，用list.splice(list.end(), list, it)将对应节点移到尾部（O(1)） -
put()时若容量满，先list.pop_front()，再从 map 中 erase 对应 key（注意：必须先删 list 再删 map，否则迭代器悬空） - map 的 value 类型必须是
std::list<:pair v>>::iterator</:pair>，不能是std::pair<k v>*</k>—— 堆分配指针无法保证生命周期
LFU 不能只靠 std::map 实现频率分组
很多实现把每个频率映射到一个 std::list，靠 std::map<int std::list>></int> 管理，但忽略了一个关键问题：当多个 key 频率相同时，LRU 规则仍要生效——即同频下要淘汰最久未用的项。单纯按频率分组无法维护「同频内时间序」。
可靠方案是双层结构：
立即学习“C++免费学习笔记（深入）”；
- 外层：
std::unordered_map<k std::pair int>></k>存 key→(value, freq) - 内层：
std::map<int std::list>></int>存 freq→list of keys，但 list 每次插入必须用push_back，删除用pop_front - 额外维护一个
std::unordered_map<k std::list>::iterator></k>，用于 O(1) 定位 key 在哪个 freq list 中
这样 get() 时：先查外层得 freq，再用迭代器从旧 freq list 中 erase，再 push_back 到 freq+1 的 list 尾部 —— 同频内自然保持访问时序。
LRU 与 LFU 的时间复杂度差异不是常数级
LRU 用 std::list + std::unordered_map 可做到严格 O(1) 的 get 和 put；但 LFU 即便优化到极致，get 仍是 O(log F)，其中 F 是当前最大频率（因为要操作 std::map<int ...></int>）。这不是设计缺陷，而是 LFU 本质需要维护频率有序性。
实际压测中，当缓存项数 > 10⁵ 且热点分布陡峭（少数 key 占 80% 访问），LFU 的命中率优势才明显；反之在均匀访问场景下，LRU 更快且内存开销低约 15%（少一层 map 查找 + 更少的指针跳转）。
关键权衡点：
- LFU 的
minFreq字段必须实时更新，否则put时无法快速定位待淘汰组 —— 常见错误是仅在get中更新，漏掉新 key 插入时的初始化 - LRU 的「最近」是绝对时间序，LFU 的「最少」是相对统计量，对突发流量敏感（比如某 key 突然被刷 100 次，freq 暴涨，可能挤掉真正冷数据）
别在 C++20 前硬套 std::ranges 或 auto 推导做泛型封装
看到网上有些“通用缓存模板”用 auto 推导容器类型或用 std::ranges::find 做查找，实际一编译就报错：C++17 不支持 std::ranges，而 auto 在模板参数推导中无法穿透嵌套类型（比如 std::list<t>::iterator</t> 无法被 auto 正确捕获为可存储类型）。
稳妥写法是显式约束：
- 用
using iterator = typename Container::iterator明确声明 - 淘汰逻辑中避免
std::find（O(N)），坚持用 map 反向索引 - 如果要用 C++20 特性，至少加
static_assert(__cplusplus >= 202002L)防止低版本误用
真正影响性能的从来不是语法糖，而是 cache line 对齐和节点内存布局 —— std::list 每个节点带两个指针，比 std::vector<:pair>></:pair> 随机访问更易失 cache，这点在千兆网卡直连 Redis 代理的场景下会被放大。
