[導(dǎo)讀]大家好，我是小林。昨天發(fā)了一篇「小林手撕LRU算法」的文章，當(dāng)時這個算法寫比較趕，導(dǎo)致代碼里面有一些不對的地方，被細心的讀者發(fā)現(xiàn)了。有時候自己寫的代碼真的是當(dāng)局者迷，旁觀者清，所以codereview環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。問題一上篇文章我說std::...
大家好，我是小林。昨天發(fā)了一篇「小林手撕 LRU 算法」的文章，當(dāng)時這個算法寫比較趕，導(dǎo)致代碼里面有一些不對的地方，被細心的讀者發(fā)現(xiàn)了。
有時候自己寫的代碼真的是當(dāng)局者迷，旁觀者清，所以 codereview 環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。
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)出來了。
這個代碼我當(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é)了些。
有時候自己寫的代碼真的是當(dāng)局者迷，旁觀者清，所以 codereview 環(huán)節(jié)是很重要的，很難有人能一次性寫出「完美」的代碼。
問題一
上篇文章我說 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é)了些。
下載文檔
