前言：
因?yàn)樽约翰殚單恼聲r(shí)經(jīng)常遇到缘挽，這些問(wèn)題：因?yàn)榄h(huán)境不同而導(dǎo)致結(jié)果不一致蔫劣、因?yàn)槲恼绿S度太大而導(dǎo)致無(wú)法理解诡必、因?yàn)槲恼麓a運(yùn)行結(jié)果不同而苦惱脊框。
所以為了看我文章的人不會(huì)遭遇同樣的問(wèn)題，
以后我的文章將遵循以下原則：
1.會(huì)在文章開頭標(biāo)明相關(guān)配置與環(huán)境
2.盡可能循序漸進(jìn)（還是看不懂可能是我沒(méi)有這樣的天賦），標(biāo)出閱讀的前提知識(shí)
3.列出的代碼自己先跑一遍
////////////////////////////////////////
語(yǔ)言：c++
前提知識(shí)：
1.map
2.queue
集成開發(fā)環(huán)境：Visual Studio 2017
////////////////////////////////////////
最近在虎牙一面時(shí)，被面試官問(wèn)到的一道算法題——使用map為容器實(shí)現(xiàn)LRU算法壹若。
LRU，Least Recently Used屿储，最近最少使用頁(yè)面換出算法，常用于頁(yè)面置換算法硬萍，是為虛擬頁(yè)式存儲(chǔ)管理服務(wù)的。
當(dāng)時(shí)第一想法是加上個(gè)序號(hào)围详，然后遍歷map將序號(hào)小的換出朴乖，所以就想著將序號(hào)作為鍵，但是當(dāng)時(shí)就被指出這樣就抹殺了map的優(yōu)勢(shì)無(wú)法快速找到所需頁(yè)面助赞。
然后又想著另開一個(gè)隊(duì)列存儲(chǔ)相應(yīng)的鍵买羞，容量超出時(shí)先進(jìn)的鍵當(dāng)然先出，但是這樣又有一個(gè)問(wèn)題雹食，還是當(dāng)頁(yè)面重復(fù)使用時(shí)它必須重新回到隊(duì)尾畜普，而無(wú)法快速找到重復(fù)頁(yè)面鍵的這一想法被否決了。
當(dāng)時(shí)還是太年輕了群叶，過(guò)于緊張腦子一片空白吃挑，想了個(gè)低效的方法，再開一個(gè)map街立，使用頁(yè)面的鍵來(lái)存頁(yè)面最近使用的時(shí)間順序舶衬，這樣能快速更新序號(hào)，但是換出頁(yè)面時(shí)還是得遍歷這個(gè)存儲(chǔ)序號(hào)的map太過(guò)于低效赎离。
現(xiàn)在仔細(xì)想想逛犹，還是非常簡(jiǎn)單的問(wèn)題，雖說(shuō)可能不是最好的解決方法梁剔，但比起上面的方法還是比較有效率的虽画。
思路：
使用結(jié)構(gòu)體將頁(yè)面數(shù)據(jù)包起來(lái)的同時(shí)加上使用計(jì)數(shù)，map存儲(chǔ)這個(gè)結(jié)構(gòu)體荣病，另開一個(gè)隊(duì)列码撰，當(dāng)頁(yè)面被使用則將鍵值入隊(duì)，當(dāng)map滿了后則不斷出隊(duì)个盆，每次出隊(duì)就對(duì)鍵值相應(yīng)的Mydata使用計(jì)數(shù)-1灸拍，當(dāng)使用計(jì)數(shù)歸0時(shí)從map中刪除做祝，直至map有空余的容量。
下面為偽代碼：
struct Mydata
{
? ? size_t num;//使用計(jì)數(shù)
? ? int data;//存儲(chǔ)數(shù)據(jù)
Mydata(size_t _num) :num(_num), data(1) {}
};
int main()
{
using omap = std::unordered_map<int, Mydata>;
omap _map;
omap::iterator it;
std::queue<int> que;
while(...)
{
/*
獲取頁(yè)面
計(jì)算使用頁(yè)面鍵值為x
*/
if(it=_map.find(x)鸡岗！=_map.end())//頁(yè)面是否在map中
//++it->second.num;//是則使用次數(shù)+1
else?_map.insert(std::make_pair<int,Mydata>(x,Mydata(1)));否則頁(yè)面插入map中
//que.push(x);鍵值插入queue中
while(_map.size()>=頁(yè)面容量)//直到map空出空間
{
it = _map.find(que.front());
if (!--it->second.num)_map.erase(it);//使用次數(shù)歸0則刪除
que.pop();
}
}
return 0;
}
總結(jié)：
當(dāng)初想利用shared_ptr的自定義deleter和引用計(jì)數(shù)來(lái)實(shí)現(xiàn)上述算法混槐，但是發(fā)現(xiàn)只有復(fù)制share_ptr復(fù)制時(shí)引用計(jì)數(shù)才會(huì)自增，就算存儲(chǔ)的指針數(shù)值一樣引用計(jì)數(shù)也不會(huì)自增轩性，所以最后自己使用了一個(gè)結(jié)構(gòu)體來(lái)進(jìn)行使用計(jì)數(shù)声登，實(shí)現(xiàn)最近未使用的頁(yè)面換出。
如果還有什么更高效的算法揣苏，請(qǐng)?jiān)谠u(píng)論中告訴我悯嗓，感謝閱讀
