如何用C语言实现LRU缓存系统，并用unordered_map优化搜索效率？

本文共计1301个文字，预计阅读时间需要6分钟。

直接使用 `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, int>> 存键值，再用 unordered_map<int, list<...>::iterator> 做索引 —— 这没问题；但若误存 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，不能存原始指针或索引 —— 因为 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> 替代迭代器 —— 增加引用计数开销，且无法保证与 list 生命周期一致
• map 的桶数量（bucket_count()）不影响正确性，但若频繁 rehash（如初始 reserve(0)），会拖慢 put 性能

LRU 的 put 操作里，淘汰逻辑放哪儿最安全

淘汰必须放在新元素插入「之后」判断，而不是之前。否则当容量为 1 且重复 put 相同 key 时，可能误删刚插入的节点。正确顺序是：先更新（或插入）节点到链表头，再更新 map，最后检查 cache.size() > capacity，若是则删尾部节点并从 map 中擦除对应 key。

容易被忽略的边界：capacity == 0 时应禁止任何缓存，直接 return；capacity < 0 属于非法输入，建议 assert 或抛异常，不要静默处理。

• 删尾部前，先用 cache.back().key 查 map，再 erase map —— 不能反过来，否则找不到 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 变化时是否清空缓存 —— 这些地方一漏，问题往往延迟暴露，调试成本远高于初始实现。