手撕 LRU 算法（更正版）

大家好，我是小林。

昨天发了一篇「小林手撕 LRU 算法」的文章，当时这个算法写比较赶，导致代码里面有一些不对的地方，被细心的读者发现了。

有时候自己写的代码真的是当局者迷，旁观者清，所以 codereview 环节是很重要的，很难有人能一次性写出「完美」的代码。

这篇就不细说 LRU 算法的思路了，如果不清楚该算法的实现思路的同学，可以先看上一篇文章。

这次主要指出和更正上一篇文章的代码的问题。

问题一

上篇文章我说 std::map 是哈希表，这里犯了错误。

C++ 使用哈希表数据结构的容器是 std::unordered_map，查询效率是 O(1)。

而 std::map 的底层数据结构是红黑树，查询效率是 O(logn)。

这两个我常常搞混了，老是觉得有 map 字眼的容器的底层数据结构是哈希表，这其实是很严重的错误了，因为当数据量非常大的时候，哈希表和红黑树的查询效率的差距很快就显现出来了。

问题二

在实现 get 函数的时候，我把已经被 erase 的迭代器，重新 push_front 到链表里了。

这个代码我当时是在 C++ 在线编译网站运行的，当时测试的时候没问题。然后有个读者反馈他跑了这个代码发现会出问题。

然后，我在 Linux 环境编译测试了下，发现被 erase 的迭代器，就会变成空值了，所以相当于 push_front 了个寂寞。

因此，应该改成重新创建个 pair 来存放即将被 erase 的迭代器的内容，然后再将 pair 加入到链表里，如下代码：

反思下，以后验证代码还是在实际环境上跑，虽然 C++ 在线编译网站方便，但是有问题未必能发现出来。

把上面的问题更正后，完整版的 LRU 代码如下：

犯错是好事。

至少我比昨天的自己更博学了些。