std::list 不适合 LRU-K 因其无法 O(1) 更新中间时间戳，导致每次 get() 平均 O(K) 遍历与重排，高 QPS 下吞吐降超 30%；应改用环形数组+单调 tick 实现真 O(1) 第 K 次时间推导。
标准 std::list + std::unordered_map 组合无法支撑高性能 LRU-K；K ≥ 2 时，必须放弃“为每个 key 存链表式历史记录”的思路，否则访问延迟随 QPS 线性恶化。
为什么 std::list 不适合维护 K 次访问时间
LRU-K 的淘汰依据不是“最新一次访问时间”，而是“第 K 次访问的时间戳”（即倒数第 K 次）。而 std::list 节点只支持 O(1) 移动到头尾，不支持 O(1) 定位并更新中间某次时间戳。
- 用链表节点存 K 个时间戳 → 插入新时间需遍历找最老位置，平均
O(K)，K=4 就是 4 次指针跳转 + cache miss - 每次
get()都重排链表按第 K 次时间排序 → 实测在中高 QPS 下触发隐式重排逻辑，吞吐下降超 30% - 误把 LRU-1 的 head/tail 模式套用到 LRU-K → 导致“刚满 K 次”的热数据，反而比“K−1 次+沉寂很久”的冷数据更早被淘汰
用环形数组 + 单调 tick 实现 O(1) 第 K 次时间推导
每个 key 对应一个长度为 K 的 std::array 和一个游标 size_t cursor，新访问覆盖最老一次，第 K 次访问时间即 access_ticks[(cursor - K + 1 + K) % K]（注意负索引取模要先加 K）。
- 时间戳不依赖系统时钟，用单调递增的
tick（如原子自增计数器），避免回拨、精度低问题 - 环形数组索引必须用
size_t并显式做(cursor - K + 1 + K) % K，不能写(cursor - K + 1) % K（C++ 负数取模行为未定义） - K 值建议硬编码为 2 或 3；K=4 时空间翻倍但命中率仅提升
- 时间戳和 value 必须分离存储：热数据 page buffer 和访问历史不能混在同一结构体里，否则驱逐时无法原子释放内存
淘汰时不扫全量，改用热度桶分层采样
维护全局有序队列代价太高。正确做法是只在需要驱逐时，对候选 key 集合批量计算第 K 次访问时间，再映射到离散热度桶（如 0–50ms、50–200ms、200–1s、>1s）。
- 桶用
std::vector<:list>>，每个桶内 key 按插入顺序排列，不做排序 - 淘汰只查最冷的 1–2 个桶；若桶为空，再向前合并相邻桶（避免空桶卡住驱逐）
- 每 100 次
insert()后触发一次桶重组：遍历所有桶，把now_tick - access_time > 1s的 key 移到新桶，防止冷数据永久滞留 - 桶数量不宜超过 8；实测 16 桶时 hash 分布倾斜导致 30% key 挤在前两个桶，淘汰效率反降
真正难的不是实现 promotion/demotion 逻辑，而是让 history slot 的内存布局完全 cache-line 局部——std::array 必须紧挨着 count 字段，且整个 HistorySlot 不能跨 cache line；否则哪怕算法再“O(1)”，也会因频繁 miss 被拖垮。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
