应手写双向链表节点+裸指针映射，因std::list+std::unordered_map易致迭代器失效；需精确控制指针、统一初始化、严格按序操作内存，哨兵模式简化边界处理。
为什么不用 std::list + std::unordered_map 就容易出错
直接用 std::list 存值、std::unordered_map 存键到迭代器的映射，看似简洁，但实际运行时极易触发迭代器失效：比如 std::list::splice 或 erase 后，若 map 中缓存的迭代器没同步更新，下一次访问就会 undefined behavior。更隐蔽的问题是，std::list::iterator 不能跨容器复用，也不能直接保存为裸指针——必须确保 map 中的迭代器始终指向当前 list 中有效节点。
- 每次
get()或put()涉及节点移动时，必须先用map.erase(key)，再list.push_front()，最后map[key] = list.begin() - 不能用
list.splice(list.begin(), list, it)把中间节点挪到头部——因为it来自 map 查得，而splice后原it在旧位置失效，但 map 里还留着它 -
std::list的size()是 O(1)，但频繁erase+push_front仍需注意内存局部性，小对象影响不大，大对象建议用std::list<:unique_ptr>>
手写双向链表节点比依赖 STL 更可控
标准容器封装太深，LRU 核心逻辑（头插、尾删、任意节点提至头部）需要精确控制指针。自己定义节点结构，能避免迭代器生命周期管理问题，也方便调试和注入日志。
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};- 构造时统一初始化
prev/next为nullptr，避免野指针 - 在
put()中删除最久未用节点时，先从map中erase(old_tail->key)，再delete old_tail，顺序不能反 - 提频操作（如
get()命中后移到头部）只需四步：断开原链接 → 插入头部 → 更新 head → 修正新节点的prev/next
std::unordered_map 是性能与安全的平衡点
用原始指针而非智能指针，是因为节点生命周期完全由 LRU 容器自身管理（头插、尾删、替换全在类内闭环），引入 std::shared_ptr 会增加原子计数开销，且无必要；而 std::unique_ptr 会导致 map 中存储的是移动后的独占权，无法支持「查找后提频」这类需多次访问同一节点的场景。
- 插入新节点时：new Node → 插入 list 头部 →
cache_map[key] = new_node - 删除节点时：先
cache_map.erase(node->key)，再手动delete node，否则内存泄漏 - 不建议用
std::map替代std::unordered_map：LRU 不要求有序，红黑树的 O(log n) 查找会拖慢热点路径
边界处理比算法本身更容易翻车
LRU 类里最容易被忽略的是容量为 0 或 1 的情况，以及重复 put 相同 key 的行为——这既是更新值，也是访问频次提升，必须触发提频逻辑，而不是简单覆盖。
立即学习“C++免费学习笔记（深入）”；
- 构造时
capacity 应直接设为 0，并使所有操作退化为 no-op（get返回 -1，put不存） -
put(key, value)遇到已存在 key：必须先从链表中移除对应节点，再插入头部，同时更新值——不能只改node->value，否则链表顺序不变，违背 LRU 语义 - 尾节点（
tail）的prev指针永远指向倒数第二个节点，tail本身不存有效数据（哨兵模式），可省去大量空指针判断；但务必在构造函数中初始化head->next = tail,tail->prev = head
手写节点+裸指针映射的组合，看着低级，实则把所有生命周期和链接逻辑暴露出来，反而不容易漏掉某处 prev 没置空、某次 erase 忘了更新 map 这类细节。真正难的不是“怎么连”，而是“什么时候连、连完谁负责清理”。
