LRU-2是双栈结构淘汰算法，本质区别在于维护Stack A和Stack B两个独立LRU栈：新数据入A，第二次访问才升B，淘汰仅从B底进行，从而过滤偶发热点噪声；标准LRU无此分级机制。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

LRU-2 是什么，和标准 LRU 有什么本质区别？ LRU-2 不是“LRU 的二次优化”，而是明确的双栈结构淘汰算法：它维护两个独立的 LRU 栈（Stack A 和 Stack B），新数据先入 Stack A；若某 key 在 Stack A 中**被再次访问**，就将其提升到 Stack B 的栈顶；淘汰时只从 Stack B 的栈底驱逐。这使得 LRU-2 对“偶发热点”更鲁棒——单次访问不会进二级，必须两次访问才升级，天然过滤噪声。 标准 std::list + std::unordered_map 实现的 LRU 无法直接复用，因为 LRU-2 需要两套独立的访问计数与位置管理，且“第二次访问”需精确识别（不是任意重复访问，而是首次访问后再次命中）。

如何用 C++17 实现带 TTL 的 LRU-2？关键结构怎么组织？ 核心是三个组件协同：

• 两个 std::list<Key>：分别对应 Stack A（m_stack_a）和 Stack B（m_stack_b）
• 一个统一的 std::unordered_map<Key, CacheEntry>：CacheEntry 包含 value、过期时间 expire_time、所属栈标记（in_stack_a / in_stack_b）、以及在对应 list 中的 std::list<Key>::iterator
• 一个单调递增的时钟源（推荐 std::chrono::steady_clock::now()，避免系统时间跳变）

注意：不能为每个 entry 单独启定时器，TTL 检查必须 lazy —— 只在 get() 或 put() 时检查并清理过期项；否则并发下资源开销不可控。

put() 和 get() 中怎么处理“第二次访问”和 TTL 判断？ get() 流程：

• 查 m_cache，若 key 不存在或已过期（entry.expire_time <= now），返回空，且立即从 map 和对应 list 中 erase
• 若存在且未过期：  • 若 entry.in_stack_a == true，说明这是第二次访问 → 将其从 m_stack_a erase，插入 m_stack_b 头部，更新 entry.in_stack_a = false; entry.in_stack_b = true  • 若 entry.in_stack_b == true，仅将该 key 在 m_stack_b 中移到头部（标准 LRU 行为）  • 更新 entry.last_access = now

put() 流程：

• 先按 get() 方式清理可能存在的旧 key（避免残留过期项）
• 新 entry 默认加入 m_stack_a 头部，标记 in_stack_a = true
• 若缓存超限，优先从 m_stack_b 尾部淘汰（LRU-2 规则）；若 m_stack_b 为空，则从 m_stack_a 尾部淘汰

容易被忽略的边界问题有哪些？

• std::list::erase(iterator) 后，原 iterator 立即失效 —— 必须在 erase 前保存 key 值用于后续 map 删除，不能依赖 iterator->first
• 并发场景下，std::shared_mutex 比 std::mutex 更合适：读多写少，get() 用 shared_lock，put() 用 unique_lock
• TTL 时间比较必须用同一 clock：所有 expire_time 字段存储为 std::chrono::steady_clock::time_point，而非秒数或毫秒数，避免精度丢失和溢出
• “第二次访问”的判定必须严格基于本次 get() 是否命中已有未过期 entry —— 如果上次访问后 entry 已过期，这次是全新加载，不算第二次

LRU-2 的复杂度不在结构本身，而在状态同步：stack 归属、map 迭代器、过期标记三者必须原子一致。稍有疏忽就会出现 iterator 失效 crash 或漏删过期项。建议把 list 操作和 map 更新包在一个作用域内完成，中间不穿插任何可能抛异常的逻辑。