不能只用std::map或std::unordered_map，因LRU需O(1)查key、更新时序、删最久未用项：哈希表缺时序维护，红黑树无法O(1)提至首部；须“哈希表+双向链表”组合实现。
为什么不能只用 std::map 或 std::unordered_map
因为 LRU 的核心操作是「在 O(1) 时间内完成：① 查 key、② 更新访问顺序、③ 删除最久未用项」。单纯哈希表能 O(1) 查，但无法维护访问时序；红黑树（std::map）能按插入/访问顺序组织，但无法 O(1) 定位并移动某个节点到头部——它不支持任意节点的常数时间“提至首部”操作。
所以必须自己管理时序：典型解法是「哈希表 + 双向链表」，前者负责 O(1) 查找，后者负责 O(1) 移动和淘汰。
手写双向链表节点和缓存主体结构要注意什么
别直接继承 std::list 或用 std::list——你没法在 O(1) 内通过 key 找到对应 list 迭代器（std::list::iterator），而每次 erase 都得遍历找节点，退化成 O(N)。
正确做法是让哈希表的 value 存储指向链表节点的指针（或迭代器），同时链表节点里存 key（用于反查哈希表，删除时清理映射）：
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
关键点：
-
Node必须存key，否则淘汰尾节点时无法从哈希表中删除对应项 - 头插尾删：新访问/插入放 head 后，淘汰取 tail 前一个（即实际 tail 是 dummy 尾哨兵）
- 所有链表操作（
moveToHead、addToHead、removeTail）必须手动维护prev/next指针，漏掉任一端会内存错乱 - 哈希表用
std::unordered_map，不是Node值类型（避免拷贝破坏指针有效性）
get 和 put 的边界逻辑最容易出错在哪
常见 crash 或行为异常集中在三类场景：
-
get时 key 不存在，返回 -1，但千万别忘了：不更新链表，也不往哈希表塞新节点 -
put时 key 已存在：只更新 value 并moveToHead，**不要 new 新节点，也不要 erase 旧节点再 insert**——否则会泄漏原节点内存，且哈希表里还存着野指针 -
put时容量满：先removeTail（拿到被删节点的key，再从哈希表 erase），再addToHead；顺序颠倒会导致哈希表残留已释放节点指针
示例片段（简化版）：
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
moveToHead(node);
return;
}
Node* newNode = new Node(key, value);
cache[key] = newNode;
addToHead(newNode);
++size;
if (size > capacity) {
Node* tail = removeTail(); // tail->prev 是真实尾节点
cache.erase(tail->prev->key); // 注意：删的是 tail->prev 的 key
delete tail->prev;
size--;
}
}
要不要用智能指针？C++17 下能用 std::list 迭代器替代裸指针吗
不用 std::shared_ptr：LRU 生命周期明确（缓存对象存活期间节点一直有效），引入引用计数纯属增加开销和复杂度；std::unique_ptr 也不合适——你需要多个地方持有同一节点指针（哈希表 + 链表），而 unique_ptr 不允许多重引用。
用 std::list + std::unordered_map 是可行的（C++17 起 std::list::iterator 在 splice/splice_after 后仍有效），但注意：
- 每次
splice移动节点时，必须确保迭代器没被提前失效（比如在erase后还拿着旧迭代器） - 哈希表 value 类型必须是
std::list，不能是::iterator const_iterator（后续要改 value） - 仍然需要在节点里存
key，因为std::list::iterator解引用后才能拿到 key，无法反向从迭代器推出 key（除非额外 map 映射）
裸指针方案更直白、可控，只要严格配对 new/delete，比迭代器方案更容易排查悬垂指针问题。
真正容易被忽略的是：无论用哪种实现，moveToHead 必须先从原位置 unlink，再插入 head 后——少一步就会导致链表断裂或环形引用，调试时极难定位。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
