因嵌入式等场景需确定性性能，数组实现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 —— 它底层仍是动态分配，违背“纯数组”初衷。
立即学习“C++免费学习笔记（深入）”；
-
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 < CAPACITY; ++i) {
if (cache[i].valid && cache[i].key == key) {
auto tmp = cache[i];
// 把 i 后面所有项前移
for (int j = i; j < CAPACITY - 1; ++j) {
cache[j] = cache[j + 1];
}
cache[CAPACITY - 1] = tmp; // 放末尾
return tmp.value;
}
}- 查找用线性扫描，别试图排序——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 快；它的价值在于可控、可预测、无隐藏分配 —— 用之前，先想清楚你到底需要什么。
