不能直接用 std::list + std::unordered_map 做高效 LRU，因虽能工作但存在性能隐患：定位节点需 O(N) 遍历、splice 易触发未定义行为、内存不连续导致 cache miss 频繁、动态分配开销大；自定义数组池方案通过预分配连续内存、索引代替指针、静态容量设计，实现真正 O(1) 操作与 L1 cache 友好访问。
为什么不能直接用 std::list + std::unordered_map 做 LRU？
它能工作，但性能隐患明显：每次 get 或 put 都要调用 list::erase 和 list::splice，而 std::list 的迭代器擦除是 O(1)，但定位节点是 O(N) —— 因为 std::unordered_map 存的是迭代器，而你得先从 map 拿到迭代器，再把它挪到 front；这本身没问题，但问题出在：std::list 的 splice 要求目标位置迭代器有效，且不能跨容器，稍有不慎就触发未定义行为（比如迭代器失效后还拿来 splice）。
更实际的坑是内存局部性差：节点分散堆上，频繁 cache miss；而且每个节点带两个指针（prev/next）+ 动态分配开销，对高频小对象（如 int 键值对）很不友好。
用自定义双向链表 + 数组池实现固定容量 LRU
核心思路：预分配一块连续内存（数组），每个槽位既是数据载体，也是链表节点。用 next/prev 索引（size_t）代替指针，避免指针失效和 heap 分配。
-
capacity编译期确定（比如用template<size_t n></size_t>），所有结构体大小可静态计算 - 链表头尾用哨兵索引（比如
0为 head，N+1为 tail），真实节点占[1, N]，避免空指针判断 -
std::array存节点，std::array<:optional>>, N></:optional>存键值 —— 但更高效的是把 key/value 直接嵌进节点结构体，避免二次查找 - 哈希表仍用
std::unordered_map<k size_t></k>，存 key 到数组下标映射；注意：插入满时需先淘汰 tail 前一个节点，再复用其槽位
示例关键片段：
立即学习“C++免费学习笔记（深入）”；
template<typename K, typename V, size_t N>
struct LRUCache {
struct Node {
K key;
V value;
size_t prev = 0;
size_t next = N+1; // 默认连向 tail
};
std::array<Node, N+2> nodes; // [0]=head, [N+1]=tail
std::unordered_map<K, size_t> index;
size_t head = 0;
size_t tail = N+1;
void move_to_front(size_t i) {
// 摘下 i：跳过 i 的前后节点
nodes[nodes[i].prev].next = nodes[i].next;
nodes[nodes[i].next].prev = nodes[i].prev;
// 插入 head 后
nodes[i].next = nodes[head].next;
nodes[i].prev = head;
nodes[nodes[head].next].prev = i;
nodes[head].next = i;
}
};
get 和 put 的边界条件怎么处理？
最容易错的是满容量时 put 的淘汰逻辑：不是删 tail，而是删 nodes[tail].prev（即 tail 前一个真实节点），然后复用它的槽位；同时必须从 index 中 erase 对应 key —— 否则下次 get 会拿到已失效的下标。
-
get不存在时返回默认V{}，不修改链表，也不插入 -
put已存在 key：只更新 value 并move_to_front，不改变容量占用 -
put新 key 且缓存已满：先淘汰nodes[tail].prev，清空其key（若 key 非 trivially destructible，需显式调用 destructor），再复用该下标 - 所有数组下标访问必须加断言或调试检查（如
i > 0 && i <= N），避免越界读写
为什么不用 std::deque 或 boost::circular_buffer？
std::deque 是分段连续，迭代器可能失效，且不支持 O(1) 随机访问 + O(1) 头尾增删 + O(1) 中间移除的组合；circular_buffer 本质是环形队列，没法高效把中间元素提到开头。
真正高性能的关键不是“用了什么容器”，而是：避免动态分配、保证内存连续、消除迭代器失效、把哈希查找和链表调整压缩在同一级 cache line 内。自定义数组池方案让一次 get 最多触发 1 次哈希查找 + 4 次数组索引访问（prev/next 更新），全部落在 L1 cache 内；而 std::list 版本至少触发 2~3 次随机内存访问。
如果容量不确定或很大（比如 >1M），那就别硬上数组池——该用 slab allocator + intrusive list，但那是另一回事了。
