手撕 LRU 算法（更正版）

昨天發(fā)了一篇「小林手撕 LRU 算法」的文章，當(dāng)時這個算法寫比較趕，導(dǎo)致代碼里面有一些不對的地方，被細(xì)心的讀者發(fā)現(xiàn)了。

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

這篇就不細(xì)說 LRU 算法的思路了，如果不清楚該算法的實現(xiàn)思路的同學(xué)，可以先看上一篇文章。

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

問題一

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

C++ 使用哈希表數(shù)據(jù)結(jié)構(gòu)的容器是 std::unordered_map，查詢效率是 O(1)。

而 std::map 的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹，查詢效率是 O(logn)。

這兩個我常常搞混了，老是覺得有 map 字眼的容器的底層數(shù)據(jù)結(jié)構(gòu)是哈希表，這其實是很嚴(yán)重的錯誤了，因為當(dāng)數(shù)據(jù)量非常大的時候，哈希表和紅黑樹的查詢效率的差距很快就顯現(xiàn)出來了。

問題二

在實現(xiàn) get 函數(shù)的時候，我把已經(jīng)被 erase 的迭代器，重新 push_front 到鏈表里了。

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

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

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

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

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

犯錯是好事。

至少我比昨天的自己更博學(xué)了些。