It is the same idea of Hash + double linked list. However, I didn't use std::list. I build the hash from key to pointer. The memory cost maybe lower than previous solutions.

```
struct Node {
int key;
int val;
Node * pre;
Node * next;
Node():key(-1),val(-1),pre(NULL), next(NULL){}
Node(int k, int v, Node * p = NULL, Node *n = NULL):key(k),val(v),pre(p),next(n){}
};
class LRUCache{
private:
int cap;
unordered_map<int, Node *> cache;
Node * head;
Node * tail;
public:
LRUCache(int capacity){
cap = capacity;
head = tail = NULL;
}
void updateNode(Node * node){
if( node == tail )
return;
if( node == head ){
head = node->next;
}else{
node->pre->next = node->next;
node->next->pre = node->pre;
}
tail->next = node;
node->pre = tail;
node->next = NULL;
tail = node;
}
int get(int key){
if( cache.find(key) != cache.end() ){
Node * targetNode = cache[key];
updateNode(targetNode);
return targetNode->val;
}else
return -1;
}
int set(int key, int value){
if( cache.find(key) != cache.end() ){
Node * targetNode = cache[key];
targetNode->val = value;
updateNode(targetNode);
}else{
while( cap != 0 && cache.size() >= cap ){
Node * delNode = head;
head = head->next;
if( head == NULL ) tail = NULL;
cache.erase(delNode->key);
delete delNode;
}
if( cap > 0 ){
Node *newNode = new Node(key, value, NULL, NULL);
if(tail != NULL){
tail->next = newNode;
newNode->pre = tail;
tail = newNode;
}else{
head = tail = newNode;
}
cache[key] = newNode;
}
}
}
};
```