FIFO实现必须配对使用queue和unordered_set，仅用queue会导致O(n)查找，降低性能；LRU应采用list+unordered_map实现，避免vector的O(n)操作；对比实验需固定访问序列、帧数和长度，并验证Belady异常。
FIFO 实现中 queue 和 unordered_set 必须配对使用
只用 queue 无法快速判断页面是否已在内存中，每次查命中都要遍历队列，时间复杂度升到 O(n)，模拟大规模访问序列时会明显拖慢。必须搭配 unordered_set 做 O(1) 存在性检查。
常见错误是只维护 queue，然后在每次访问前手动遍历——这会让 FIFO 模拟本身变成性能瓶颈，掩盖了算法本身的缺页行为。
-
queue只存插入顺序，不负责查找 -
unordered_set负责“有没有”，queue负责“谁最老” - 淘汰时先从
queue取front()，再从unordered_set中erase()对应值 - 插入新页时，两个容器要同步
push()和insert()
LRU 的双向链表 + map 实现比 vector find 更可靠
用 vector 模拟 LRU 时，每次访问命中都要把对应元素移到末尾，用 std::find 定位再 erase + push_back，实际是 O(n) 操作。在 1000+ 访问长度下，性能差距会拉大到毫秒级，且容易因迭代器失效出错。
标准做法是用 list（双向链表）存访问顺序，用 unordered_map 建立页面号到链表节点的映射。这样：访问命中时只需 splice 到尾部；插入新页时直接 push_back 并更新 map；淘汰时取 front() 即可。
- 避免用
vector::erase(it)后再push_back——移动成本高，且可能触发内存重分配 -
list::splice是 O(1)，比反复删除插入安全得多 - map 的 value 类型必须是
list，不能是 int 或 size_t 索引::iterator - 淘汰前务必检查
list.empty()，否则front()未定义
命中率对比必须固定访问序列与帧数，否则结果不可比
不同算法对局部性敏感度差异极大。比如一个强循环序列（如 {1,2,3,1,2,3,...}）下，LRU 命中率可能接近 100%，而 FIFO 可能只有 33%；但换成随机序列，两者差距会收窄甚至反转。不控制变量就跑对比，等于白跑。
实操建议：先生成一段带局部性的典型序列（例如 60% 顺序 + 20% 小范围跳转 + 20% 大跳转），用同一段 vector 输入所有算法，帧数（frameCount）也保持一致。别在测 FIFO 时用 4 帧、测 LRU 时用 5 帧。
- 序列长度至少 200，太短看不出趋势
- 帧数建议从 3 开始试，再逐步加到 8，观察拐点
- 输出必须包含：总访问数、缺页次数、命中次数、命中率（
(总-缺页)/总） - 不要只看最终数字，加一行日志打印每次缺页时的内存状态（如
[1,4,2]），方便人工核对逻辑
Belady 异常不是理论玄学，FIFO 下真能复现
增加物理帧数反而导致缺页增多——这不是 bug，是 FIFO 的固有缺陷。用经典序列 {1,2,3,4,1,2,5,1,2,3,4,5}，在帧数=3 和帧数=4 两种配置下分别跑 FIFO，你会看到缺页数从 9 升到 10。这个现象在 LRU 和 OPT 中不会出现。
它源于 FIFO 完全忽略访问模式，只认“谁先来”。多一帧后，某些本该早被淘汰的页面被多留了一轮，反而挤掉了后续高频页面的位置。验证时务必关闭所有缓存优化（如编译加 -O0），确保执行路径干净。
- 测试 Belady 必须用 FIFO，LRU 不会出现此现象
- 序列里要有重复块（如 1,2,3,4 循环）和突变点（如突然跳到 5）
- 打印每步的
queue内容，对照课本推演步骤，确认淘汰选择是否符合 FIFO 规则 - 一旦发现帧数增加但缺页上升，就是 Belady 被触发，不是代码写错了
实际跑对比时，最容易被忽略的是：**访问序列的生成逻辑是否引入了隐式缓存或伪随机偏差**。比如用 rand() % N 生成页面号，若 N 不是 2 的幂，低比特会偏向某些值，导致局部性失真。宁可用 std::mt19937 配 std::uniform_int_distribution，哪怕多写三行。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
