題目
首先來看題目哄芜，就是實(shí)現(xiàn)一個(gè)LRU，最近最少使用魔眨。
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
思路
get()相當(dāng)于讀舌剂，set()即是寫裕便。一次讀或?qū)懸馕吨鴮彺鎵K使用了一次请垛，該緩存的優(yōu)先級就提高催训。
思路比較簡單，基于哈希表和雙向鏈表宗收。先通過哈希表查找緩存塊的位置漫拭，也就是緩存塊在鏈表中的位置。然后把該緩存塊置于鏈表表頭混稽。如果緩存已經(jīng)滿了采驻，那就把表尾的緩存塊丟掉审胚，再在表頭插入新的緩存塊。
實(shí)現(xiàn)
用C++11實(shí)現(xiàn)的時(shí)候比較蛋疼礼旅，怪自己不夠熟悉STL膳叨。
這里用到連個(gè)容器：
-
std::list，相當(dāng)于雙向鏈表各淀。splice()懒鉴，push_front()，pop_back()的復(fù)雜度為$O(1)$碎浇。 -
std::unordered_map，相當(dāng)于哈希表璃俗。find()奴璃，insert()，erase()的復(fù)雜度為$O(1)$（單個(gè)element）城豁。
這里需要注意的地方有兩點(diǎn)：
- 由于這里用了
std::list苟穆，所以就不能用指針指向list中的element，要用iterator唱星。值得注意的是雳旅，std::list的iterator是不會(huì)因?yàn)椴迦雱h除而改變所指向的element的，而std::vector的iterator是會(huì)改變所指向的element的（例如erase了之后）间聊。
所以在此哈希表可以這樣實(shí)現(xiàn)：
unordered_map<int, list<T>::iterator> cacheMap; -
std::list中攒盈，element的移動(dòng)可以用splice()來實(shí)現(xiàn)：
例如：
std::list<int> list = {1,2,3};
auto it = list.begin();
it = std::next(it); //it指向第二個(gè)element，2
if (it != list.begin())
{
// 將list.begin()置于it之后
list.splice(list.begin(), list, it, std::next(it)); // 2,1,3
}
My Solution
/*
* LRUCache
*
* Using double linked list (stl list) and hash map(stl unordered_map)
*/
#include <iostream>
#include <unordered_map>
#include <memory>
#include <list>
using namespace std;
struct KeyVal
{
int key;
int value;
};
class LRUCache{
private:
int capacity; // cache capacity
list<KeyVal> cache; // cache, implement in Double-Linked-List
unordered_map<int, list<KeyVal>::iterator> cacheMap; // Hash Map, quickly access to value
public:
LRUCache(int capacity):
capacity(capacity)
{ }
int get(int key) {
auto it = cacheMap.find(key);
// Find by key
if (it != cacheMap.end()) {
//Find it! Get the value.
auto kv = it->second;
// Move to front
if (kv != cache.begin())
cache.splice(cache.begin(), cache, kv, next(kv));
return kv->value;
}
return -1;
}
void set(int key, int value) {
auto it = cacheMap.find(key);
// Find by key
if (it != cacheMap.end() ){
// find and set new value
auto kv = it->second;
kv->value = value;
// move front
if (kv != cache.begin())
cache.splice(cache.begin(), cache, kv, next(kv));
}
else {
// Not found
if (cacheMap.size() < capacity) {
KeyVal newKv = {key, value};
// set in cache
cache.push_front(newKv);
// add to map
cacheMap.insert(make_pair(key, cache.begin()));
}else {
// Capacity is not enough
// Delete the least used value
int oldKey = cache.back().key;
cache.pop_back();
cacheMap.erase(oldKey);
// Add new value
KeyVal newKv = {key, value};
cache.push_front(newKv);
cacheMap.insert(make_pair(key, cache.begin()));
}
}
}
};
