手撕 LRU 算法（更正版）

时间：2021-08-01 01:05:23

关键字：算法 LRU 代码

手机看文章

扫描二维码
随时随地手机看文章

[导读]大家好，我是小林。昨天发了一篇「小林手撕LRU算法」的文章，当时这个算法写比较赶，导致代码里面有一些不对的地方，被细心的读者发现了。有时候自己写的代码真的是当局者迷，旁观者清，所以codereview环节是很重要的，很难有人能一次性写出「完美」的代码。问题一上篇文章我说std::...

大家好，我是小林。昨天发了一篇「小林手撕 LRU 算法」的文章，当时这个算法写比较赶，导致代码里面有一些不对的地方，被细心的读者发现了。
有时候自己写的代码真的是当局者迷，旁观者清，所以 codereview 环节是很重要的，很难有人能一次性写出「完美」的代码。

问题一

上篇文章我说 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 代码如下：

犯错是好事。
至少我比昨天的自己更博学了些。