std::list + std::unordered_map 不适用于 LRU-2,因其链表仅记录最近一次访问顺序,无法维护倒数第二次访问时间(prev_access),且无法支持晋升/降级逻辑、实时过期检查及双时间戳原子更新。

不能用 std::list + std::unordered_map 直接套标准 LRU 模式来实现带过期的 LRU-2,因为 LRU-2 的淘汰依据不是「最后一次访问时间」,而是「倒数第二次访问时间」;过期检查也必须在每次 get() 和 put() 时触发,否则已超时但长期未访问的 key 会滞留内存。
为什么 std::list + std::unordered_map 不适用于 LRU-2
标准 LRU 链表只记录单次访问顺序,而 LRU-2 要求每个 key 至少被访问两次才晋升到主缓存,并在淘汰时比较「上一次访问时间」(即第二次最近访问)——这个时间点无法从链表位置推导出来。强行复用链表顺序会导致:刚被访问两次的 key 可能因新 key 插入而立刻被踢出,违背 LRU-2 “观察窗口”设计初衷。
-
std::list的节点位置只反映最近一次访问顺序,不携带历史访问信息 - 没有机制区分「第一次访问」和「第二次访问」,无法支撑晋升/降级逻辑
- 链表遍历找「倒数第二次最久」是 O(n),不符合 LRU-2 实时淘汰要求
必须用两个哈希表维护双时间戳
核心不是链表,而是显式维护两个时间点:latest_access(最新)和 prev_access(上一次)。所有时间统一用 std::chrono::steady_clock::time_point,避免 system_clock 回拨导致误删。
-
cache_:类型为std::unordered_map<key std::pair timepoint>></key>,存值和最新访问时间 -
history_:类型同上,但只存 key 对应的「上一次访问时间」,即倒数第二次访问时刻 - 每次
get(key)时:先用now() - cache_[key].second > ttl_判断是否过期;未过期则把当前时间写入history_[key],再更新cache_[key].second - 每次
put(key, value)时:同样先过期检查;若缓存满,遍历history_找prev_access最早的 key 删除(不是看cache_里的时间)
cache2(历史观察层)必须设大小上限并随机清理
history_ 不是临时日志,而是有容量约束的观察窗口。放任增长会导致内存泄漏,但按时间顺序精确淘汰又不可行(它不存完整访问序列)。折中做法是硬限 size + 随机剔除。
组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记(深入)”;
- 插入前检查
history_.size() > max_history_size(例如 10000) - 超限时,用
std::uniform_int_distribution随机选约 10% 的 key 删除,而不是遍历全量 - 如果 key 已存在,只更新
prev_access和latest_access,不增加 size - 注意:
history_中的过期项也要在get()/put()里一并清理,不能只靠随机剔除
过期检查不能只在插入时做
只在 put() 时检查过期,会漏掉那些长期没被访问、但早已超时的 key。LRU-2 的惰性清理必须覆盖所有入口:每次 get() 和 put() 都要对涉及的 key 做实时过期判断,且清理动作要原子完成(先查再删,不能删完再查)。
- 在
get()中:命中后先检查cache_[key]是否过期,过期则erase并返回空,不更新任何时间戳 - 在
put()中:即使 key 不存在,也要检查history_[key]是否过期(防止旧观察记录残留) - 所有时间差计算用
now() - time_point得到duration,直接与ttl_(如std::chrono::seconds(300))比较,避免反复duration_cast
真正难的不是结构搭建,而是时间语义的一致性:history_ 里那个“上一次”,必须严格对应真实发生的倒数第二次访问;一旦在并发或异常路径下错位,整个 LRU-2 行为就不可预测。所以所有时间更新必须包裹在临界区,且绝不复用 now() 多次——每个操作只调一次时钟。

















