lfu缓存的核心难点在于高效维护“最低频次+最久未使用”的双重排序，仅用数组无法o(1)定位淘汰项；需配合frequency和timestamp数组及min_freq变量增量更新，避免全量扫描。
LFU缓存的核心难点在哪
LFU（Least Frequently Used）要求每次淘汰访问频次最低且最久未使用的项，光用 std::vector 或裸数组无法高效支持“按频次分组 + 组内按时间排序”的双重需求。数组本身不带索引结构，直接模拟会导致 get() 和 put() 退化到 O(n) —— 尤其是查找最小频次、定位该频次下最老的 key 这两步。
关键不是“能不能用数组”，而是“怎么用数组不牺牲性能”。答案是：数组只存数据，用额外结构管理频次和时序。
用数组存 value，但必须配 frequency 数组和 timestamp 数组
你得维护至少三块连续内存：
-
keys：int[]或std::vector<int></int>，存 key（或哈希后的位置索引） -
values：int[]，对应 value -
frequencies：int[]，每个位置记录当前 key 的访问频次 -
timestamps：int[]，记录最后一次get()或put()的逻辑时间戳（递增计数器）
这样做的好处是：所有访问都是 O(1) 索引；坏处是每次 get() 都要更新 frequencies[i] 和 timestamps[i]，而 put() 淘汰时得遍历整个数组找「频次最小且 timestamp 最小」的下标。
常见错误现象：
- 只维护
frequencies，忽略timestamps→ 同频次项无法判断谁更老，淘汰随机 - 用系统时间（如
time(nullptr)）当 timestamp → 并发或快速调用时戳相同，失去顺序性 - 没做 key 存在性检查，
put()覆盖时忘记重置频次 → 导致旧 key 频次虚高
如何避免每次 put 都全量扫描数组
全扫 O(n) 在容量大时不可接受。折中方案是加一个“最小频次缓存”变量 min_freq，并在每次操作中增量维护它：
-
get(key)：找到下标 i 后，frequencies[i]++；若原频次等于min_freq且该频次下只剩这一个 key，则需遍历一次更新min_freq -
put(key, value)：若缓存未满，直接插入；若已满，先按min_freq找出所有候选下标，再从中选timestamp最小者淘汰
注意点：
-
min_freq初始值设为 1，但首次put后要立即设为 1，不能依赖初始化 - 淘汰前必须确认该 key 是否已存在——如果存在，应更新 value 和 frequency，不触发淘汰
- 数组长度固定，建议用
std::vector而非裸new int[N]，避免手动管理生命周期
C++ 示例片段：核心淘汰逻辑
int findLfuIndex() {
int candidate = -1;
int min_ts = INT_MAX;
for (int i = 0; i <p>这个函数只在真正需要淘汰时调用，且仅在 <code>min_freq</code> 对应的桶里筛选，比扫全部快得多。但要注意：如果 <code>min_freq</code> 对应多个 key，仍需完整遍历这些位置 —— 所以实际性能取决于频次分布，不是严格 O(1)，但实践中远好于无优化的 O(n)。
</p><p>真正复杂的点不在数组本身，而在「频次变化时如何不漏掉更新 <code>min_freq</code>」。少一次判断，缓存行为就可能错乱。这个逻辑边界容易被忽略，调试时建议打日志输出每次 <code>min_freq</code> 变更和淘汰下标。</p>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
