因嵌入式等场景需确定性性能，数组实现lru避免动态分配与指针跳转；用cacheentry数组+valid标记，get/put均o(n)移动元素维持访问序，容量编译期固定。
为什么不用 std::list 而用数组实现 LRU？
因为嵌入式环境、裸机或性能敏感场景下，std::list 的动态内存分配和指针跳转开销不可控；数组能保证 O(1) 随机访问 + 确定性内存布局。但代价是：容量固定、删除/移动元素需手动搬移数据。
核心思路是用数组存缓存项，另用一个整型数组（或单个变量）维护“最近使用顺序”——最简单做法就是每次访问后把对应项挪到数组末尾，新插入也放末尾，淘汰时删开头。
- 适合 key 为整数、value 为简单类型（如
int）的轻量级场景 - 不支持并发访问，无锁设计
- 时间复杂度：访问/更新 O(N)，插入/淘汰 O(N)；空间 O(1) 额外开销
struct 定义与数组布局怎么安排？
缓存项必须带 key 和 value，还要能快速判断是否命中。推荐结构体 + 线性搜索：
struct CacheEntry {
int key;
int value;
bool valid; // 标记是否已填充，避免用哨兵值（如 key == -1）
};
主缓存数组声明为：CacheEntry cache[CAPACITY]。别用 std::vector —— 它底层仍是动态分配，违背“纯数组”初衷。
-
valid == false表示该槽位空闲，可直接覆盖 - 不要省略
valid字段：用 key == 0 或 -1 做无效标记会导致 key=0 无法缓存 - 数组大小
CAPACITY必须在编译期确定（constexpr或宏）
如何实现 get() 和 put() 的数组逻辑？
关键不是“查得快”，而是“更新顺序要对”。每次 get(key) 命中后，要把该项移到数组末尾；put(key, value) 时，若已存在则更新并移至末尾，否则插入末尾（若满，则先删开头第一个 valid == true 的项）。
注意：移动不是交换，是“复制+擦除原位置”，否则顺序会乱：
// 伪代码逻辑（C++ 风格） for (int i = 0; i
- 查找用线性扫描，别试图排序——LRU 顺序靠位置隐含，排序会破坏局部性
- 插入新项前，先检查是否已存在，避免重复 entry
- 淘汰只发生在
put()且缓存满时，删的是cache[0]（前提是它valid == true）
容易被忽略的边界问题
数组实现 LRU 最常崩在三个地方：越界访问、valid 状态错置、移动时漏清原位。
- 移动元素后，原位置必须设
valid = false，否则下次get()可能误命中“幽灵数据” - 插入新项时，如果缓存未满，要找第一个
valid == false的槽位，而不是无脑写cache[CAPACITY-1] - 所有循环索引必须严格用
[0, CAPACITY)，for (int i = 0; i 这种写法极易多走一轮 - 如果 key 类型是
size_t或指针，注意valid字段不能用key == 0判断——必须独立布尔字段
数组版 LRU 看似简单，但每个移动操作都牵扯多个内存写，实际性能未必比小容量 std::list + unordered_map 快；它的价值在于可控、可预测、无隐藏分配 —— 用之前，先想清楚你到底需要什么。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
