C++如何实现简单带过期机制的LRU-2二级缓存淘汰

LRU-2不能直接套用std::list+unordered_map，因其需维护两个独立访问历史队列（最近两次访问与主淘汰链表），而标准组合仅支持单层LRU，无法表达“上一轮命中但本轮未命中”状态，硬套会导致逻辑耦合、遍历查找、时间复杂度退化为O(n)。

LRU-2缓存结构为什么不能直接套用std::list + unordered_map？

因为LRU-2需要维护**两个独立的访问历史队列**：一个记录最近两次访问（用于判断是否“稳定命中”），另一个是主LRU链表（用于淘汰）。标准容器组合只能支撑单层LRU，无法天然表达“某key是否在上一轮被访问过但本轮没被访问”这一状态。硬塞会导致逻辑耦合、删除/更新时需遍历查找，时间复杂度退化到O(n)。

如何用两个哈希表 + 双向链表实现O(1)的LRU-2核心操作？

关键在于把“访问频次历史”和“淘汰顺序”解耦：

• std::unordered_map<Key, Node*>：主索引，指向双向链表节点，支持O(1)定位
• std::unordered_map<Key, size_t>：访问计数快照，只存“上次检查周期内命中次数”，非实时计数（避免频繁写）
• 双向链表std::list<Node>：按最近一次访问时间排序，头为最新，尾为最旧——这是淘汰依据

每次get()时，不立即移动节点，而是标记该key“本轮已访问”；在put()或定时检查点，统一扫描快照表：若某key在快照中计数≥2，则保留在链表中；否则从链表尾部开始逐个淘汰未被本轮命中的节点。这样避免了每次访问都触发链表重排。

过期时间怎么和LRU-2协同，而不是各自为政？

如果把TTL当成独立字段存在节点里，会在淘汰时引入额外判断开销（每个候选节点都要比对expire_time < now），破坏O(1)假设。更合理的方式是：在链表节点中同时存access_time和expire_time，但只在淘汰路径上做TTL检查——即从链表尾部遍历时，跳过未过期节点，直到找到第一个既“未被本轮访问”又“已过期”的节点才真正淘汰。这样：

立即学习“C++免费学习笔记（深入）”；

• 未过期但冷数据：留着，等下次检查再处理
• 已过期但热数据（刚被get()过）：不淘汰，因为get()会刷新access_time和expire_time
• 过期+冷：立刻踢出

注意：put()必须同步更新expire_time = now + ttl，且get()也要刷新（否则TTL会静默失效）。

实际编码时最容易漏掉的三个细节

一是get()后忘记调用touch()更新access_time和expire_time，导致缓存项提前过期；二是快照表（二级计数）没有在每次检查周期开始前清空，造成“历史命中”误判；三是链表节点析构时没从两个哈希表中删除对应条目，引发后续get()访问野指针。

这些错误不会立刻报错，而是在高并发或长时间运行后出现缓存击穿或内存泄漏。建议在Node构造/析构函数里加日志，或用std::shared_ptr管理节点生命周期，强制绑定哈希表引用。