应使用 std::list 而非手写双向链表，因其迭代器稳定、支持零拷贝 splice、size() 为 O(1)，配合 unordered_map 可安全高效实现 LRU；需注意迭代器有效性、key 哈希特化、淘汰时机及 capacity 边界处理。
为什么用 std::list 而不是手写双向链表
直接用 std::list 是因为它的节点指针（std::list::iterator）是稳定的，插入/删除不会使其他迭代器失效，而 std::vector 或 std::deque 不满足这点。手写链表看似可控，但容易在移动节点、更新指针时出错，尤其涉及 erase 后再 push_front 的 LRU 核心逻辑。C++11 之后 std::list 还支持 splice，能零拷贝地把一个节点从中间移到头部，比先 erase 再 push_front 更安全高效。
常见错误：有人用 std::list<pair int>></pair> 存键值，再用 unordered_map<int list>::iterator></int> 做索引 —— 这没问题；但若误存 list::const_iterator 或在 splice 后没同步更新 map 中的迭代器，就会导致访问已释放节点，触发未定义行为。
-
splice必须传入目标容器的迭代器位置（如cache.begin()），不能传源容器的 end 迭代器 - 每次
get或put触发命中时，只调一次splice，不要先erase再push_front -
std::list的size()是 O(1)，但某些老标准库实现可能为 O(n)，建议显式维护计数变量
unordered_map 的 key 和 value 怎么设计才不踩坑
value 必须存 std::list<node>::iterator</node>，不能存原始指针或索引 —— 因为 std::list 内存不连续，无法通过偏移计算地址。key 类型要支持哈希和等价比较：内置类型（int、string）没问题；自定义结构体必须显式特化 std::hash 并重载 operator==，否则编译失败。
典型报错：error: call to implicitly-deleted default constructor of 'std::hash<mykey>'</mykey>。这不是 map 本身的问题，而是你忘了提供哈希函数。
立即学习“C++免费学习笔记（深入）”；
- 如果 key 是
std::string，别用c_str()当 key（会构造临时const char*，哈希行为不可控） - value 类型别用
shared_ptr<node></node>替代迭代器 —— 增加引用计数开销，且无法保证与 list 生命周期一致 - map 的桶数量（
bucket_count()）不影响正确性，但若频繁 rehash（如初始reserve(0)），会拖慢put性能
LRU 的 put 操作里，淘汰逻辑放哪儿最安全
淘汰必须放在新元素插入「之后」判断，而不是之前。否则当容量为 1 且重复 put 相同 key 时，可能误删刚插入的节点。正确顺序是：先更新（或插入）节点到链表头，再更新 map，最后检查 cache.size() > capacity，若是则删尾部节点并从 map 中擦除对应 key。
容易被忽略的边界：capacity == 0 时应禁止任何缓存，直接 return；capacity 属于非法输入，建议 assert 或抛异常，不要静默处理。
- 删尾部前，先用
cache.back().key查 map，再erasemap —— 不能反过来，否则找不到 key - 用
cache.pop_back()而非cache.erase(--cache.end())，更简洁且不易因空容器导致--end()未定义 - 如果
put的 key 已存在，只更新 value 和位置，不增加 size，所以淘汰判断必须在所有分支统一出口处
完整可跑的最小实现长什么样
下面是一个去掉模板、限定 key=int/value=int 的最小可用版本，重点体现链表与 map 的协同逻辑，不含异常处理和线程安全：
class LRUCache {
int cap;
list<pair<int, int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
auto it = map.find(key);
if (it == map.end()) return -1;
cache.splice(cache.begin(), cache, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = map.find(key);
if (it != map.end()) {
it->second->second = value;
cache.splice(cache.begin(), cache, it->second);
} else {
cache.emplace_front(key, value);
map[key] = cache.begin();
if (cache.size() > cap) {
int lastKey = cache.back().first;
cache.pop_back();
map.erase(lastKey);
}
}
}
};
注意 emplace_front 比 push_front({key, value}) 更高效；splice 第二个参数是源容器，第三个是源迭代器，顺序不能反。实际项目中若需支持多种 key/value 类型，再套一层 template 即可，核心逻辑不变。
真正难的不是写出来，而是确认迭代器在 splice/erase 后是否还有效、map 的 erase 是否覆盖了所有路径、capacity 变化时是否清空缓存 —— 这些地方一漏，问题往往延迟暴露，调试成本远高于初始实现。
