LRU（Least Recently Used）是一種緩存淘汰算法，當(dāng)未命中時(shí)梨撞，將最近最少使用（即上一次使用的時(shí)間離現(xiàn)在最久）的塊置換出去來(lái)加載新塊雹洗。
例如，以下塊的訪問(wèn)順序?yàn)?A B C D E D F：
一旦 A B C D 被放置在緩存中（每個(gè)新訪問(wèn)增量為 1）卧波，而后又訪問(wèn) E 沒(méi)有命中队伟，需要將其替換進(jìn)其中一個(gè)塊中。根據(jù) LRU 算法幽勒，由于 A 具有最低的時(shí)間記錄 A(0)，E 將取代 A港令。
算法需要跟蹤何時(shí)最近一次使用了各個(gè)塊啥容，這個(gè)代價(jià)是昂貴的。實(shí)際上只要維持被訪問(wèn)的順序就可以了顷霹，而不必知道確切的時(shí)間記錄咪惠。我們可以用 STL 中的雙向鏈表來(lái)實(shí)現(xiàn)這樣一個(gè)功能。
題目參考 Leetcode 146淋淀。
實(shí)現(xiàn) get 和 put 兩種方法遥昧，其中：
-
get(key)返回 key 對(duì)應(yīng)的 value（保證大于 0），如果沒(méi)有則返回 -1朵纷。 -
put(key, value)無(wú)返回值炭臭，若命中，將其 value 置為新值袍辞；若未命中鞋仍，但 capacity 大于當(dāng)前已存塊數(shù)，直接插入搅吁；若未命中且數(shù)量已達(dá) capacity威创，執(zhí)行 LRU 算法進(jìn)行替換落午。
借助 list 來(lái)記錄塊的使用情況，每一個(gè)新加入或命中的塊都被放到頭部肚豺，未命中時(shí)被替換掉的一定是位于尾部的節(jié)點(diǎn)溃斋。用一個(gè) unordered_map 來(lái)存儲(chǔ) key 對(duì)應(yīng)的 value 和在 list 中的位置（因?yàn)閷?duì) list 迭代器的刪除操作不會(huì)導(dǎo)致其他迭代器失效），每次操作后都需要更新存儲(chǔ)的 list 迭代器吸申。
代碼如下梗劫，具體細(xì)節(jié)參照注釋?zhuān)?/p>
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int value_1 = obj.get(key);
* obj.put(key,value);
*/
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
cache.reserve(cap); // 預(yù)留 capacity 大小的空間
}
int get(int key) {
auto iter = cache.find(key);
if(iter != cache.end()) { // 若命中
touch(iter); // 更新節(jié)點(diǎn)記錄
return iter->second.first; // 返回 value 值
}
return -1; // 未獲取到返回 -1
}
void put(int key, int value) {
auto iter = cache.find(key);
if(iter == cache.end()) { // 未命中
if(cache.size() == cap) { // cache 已滿(mǎn)
cache.erase(data.back()); // 從 cache 中刪除位于 list 末尾的 key
data.pop_back(); // 從 data 中彈出位于 list 末尾的 key
}
data.push_front(key); // cache 無(wú)論滿(mǎn)不滿(mǎn)都需要，從頭部加入新的 key呛谜，更新時(shí)間順序記錄
}
else { // 命中
touch(iter); // 更新節(jié)點(diǎn)記錄
}
cache[key] = {value, data.begin()}; // 未命中時(shí)置新塊在跳，命中時(shí)置新值
}
private:
list<int> data;
unordered_map<int, pair<int, list<int>::iterator>> cache;
int cap;
/*
命中時(shí)，將塊在 list 中原來(lái)的節(jié)點(diǎn)刪除隐岛，重新插入到頭部猫妙。
unordered_map 中存儲(chǔ)的迭代器也需要修改。
*/
void touch(unordered_map<int, pair<int, list<int>::iterator>>::iterator it) {
int k = it->first;
data.erase(it->second.second);
data.push_front(k);
it->second.second = data.begin();
}
};
