大家好，我是小林。昨天發(fā)了一篇「小林手撕 LRU 算法」的文章，當時這個算法寫比較趕，導致代碼里面有一些不對的地方，被細心的讀者發(fā)現了。

有時候自己寫的代碼真的是當局者迷，旁觀者清，所以 codereview 環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。

這篇就不細說 LRU 算法的思路了，如果不清楚該算法的實現思路的同學，可以先看上一篇文章。

這次主要指出和更正上一篇文章的代碼的問題。

問題一

上篇文章我說 std::map 是哈希表，這里犯了錯誤。?

C 使用哈希表數據結構的容器是 std::unordered_map，查詢效率是 O(1)。

而 std::map 的底層數據結構是紅黑樹，查詢效率是 O(logn)。

這兩個我常常搞混了，老是覺得有 map 字眼的容器的底層數據結構是哈希表，這其實是很嚴重的錯誤了，因為當數據量非常大的時候，哈希表和紅黑樹的查詢效率的差距很快就顯現出來了。

問題二

在實現 get 函數的時候，我把已經被 erase 的迭代器，重新 push_front 到鏈表里了。

這個代碼我當時是在 C 在線編譯網站運行的，當時測試的時候沒問題。然后有個讀者反饋他跑了這個代碼發(fā)現會出問題。

然后，我在 Linux 環(huán)境編譯測試了下，發(fā)現被 erase 的迭代器，就會變成空值了，所以相當于 push_front 了個寂寞。

因此，應該改成重新創(chuàng)建個 pair 來存放即將被 erase 的迭代器的內容，然后再將 pair 加入到鏈表里，如下代碼：

反思下，以后驗證代碼還是在實際環(huán)境上跑，雖然 C 在線編譯網站方便，但是有問題未必能發(fā)現出來。

把上面的問題更正后，完整版的 LRU 代碼如下：

犯錯是好事。

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