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

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

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

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

問(wèn)題一

上篇文章我說(shuō) std::map 是哈希表，這里犯了錯(cuò)誤。?

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

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

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

問(wèn)題二

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

這個(gè)代碼我當(dāng)時(shí)是在 C 在線(xiàn)編譯網(wǎng)站運(yùn)行的，當(dāng)時(shí)測(cè)試的時(shí)候沒(méi)問(wèn)題。然后有個(gè)讀者反饋他跑了這個(gè)代碼發(fā)現(xiàn)會(huì)出問(wèn)題。

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

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

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

把上面的問(wèn)題更正后，完整版的 LRU 代碼如下：

犯錯(cuò)是好事。

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