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.
哈希表存储映射关系可以在O(1)时间内实现快速查找，利用双向链表存储节点信息，O(1)时间内交换节点。头结点保存最近使用的，尾节点保存最近最少使用的，get时更新最近使用节点（即将当前节点更新至头结点）
class LRUCache{
public:
LRUCache(int capacity) {
cacheCapacity = capacity;
}
int get(int key) {
if(cacheCapacity <0 ){
return -1;
}else{
if(cacheMap.find(key) == cacheMap.end()){
//no such key in map
return -1;
}
//add current node to head
cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
//update map
cacheMap[key] = cacheList.begin();
return cacheMap[key]->val;
}
}
void set(int key, int value) {
//not found
if(cacheMap.find(key) == cacheMap.end()){
if(cacheCapacity == cacheList.size()){
//update map
cacheMap.erase(cacheList.back().key);
//update list
cacheList.pop_back();
}
//add a new node
cacheList.push_front(cacheNode(key,value));
//update map
cacheMap[key] =cacheList.begin();
}else{
//just ahead this node to front
cacheMap[key]->val = value;
cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);
cacheMap[key] = cacheList.begin();
}
}
private:
struct cacheNode{
int key;
int val;
cacheNode(int k,int v):key(k),val(v){}
};
list<cacheNode> cacheList;
unordered_map<int,list<cacheNode>::iterator> cacheMap;
int cacheCapacity;
};