LRU Cache

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.

1.申请一块连续的内存，可以在内存中存储Node(key，val)，再用一个hashmap来保存key与对应的Node的地址，双向链表来保存上述Node
2.执行set(key, value)操作的时候，首先判断这个key是否已经在map中了，如果在，则将其提升到双向链表的头部，如果不存在，则申请一块内存，这里就会有两种情况(1)已经没有可用的内存了，这是将队尾的节点替换掉(2)还有内存，申请这块内存
3.执行get操作，判断这个key是否存在，不存在，返回-1，存在，则将这个节点加到双向链表的头部

在写下面的程序需要注意的是，里面有一个指针容器，同时里面有个指针数组，他们里面指向的同一块内存，在单独使用指针容器的时候，很容易忘了释放容器里面指针指向的值，造成内存泄露，所以这用一个指向指针数组的指针来看管这块内存

struct Node{
    int key;
    int val;
    Node *prev, *next;
};
class LRUCache{
public:
    LRUCache(int capacity) {
        entries_ = new Node[capacity];

        for(int i = 0; i < capacity; i++){
            free_entries_.push_back(entries_ + i);
        }

        head_ = new Node;
        tail_ = new Node;
        head_->prev = NULL;
        head_->next = tail_;
        tail_->prev = head_;
        tail_->next = NULL;        
    }
    ~LRUCache(){
        delete head_;
        delete tail_;
        delete entries_;
    }

    int get(int key) {
        Node * temp = hashmap_[key];
        if(temp != NULL){
            detach(temp);
            attach(temp);
            return temp->val;
        }else{
            return -1;
        }
    }

    void set(int key, int value) {
        Node *temp = hashmap_[key];
        if(temp != NULL){
            detach(temp);
            temp->val = value;
            attach(temp);
        }else{
            //没有可用的节点
            if(free_entries_.empty()){
                //去掉最不常用的，双向链表的尾端
                temp = tail_->prev;
                detach(temp);
                hashmap_.erase(temp->key);
            }else{
                temp = free_entries_.back();
                free_entries_.pop_back();
            }
            temp->key = key;
            temp->val = value;
            attach(temp);
            hashmap_[key] = temp;
        }
    }
private:
    unordered_map<int, Node* > hashmap_;
    vector<Node *> free_entries_; // 存储可用结点的地址
    Node *head_, *tail_;
    //申请的内存，用来存放cache值
    Node *entries_; // 双向链表中的结点

    //从双向链表中删除一个节点
    void detach(Node *node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    //插入到双向链表头部
    void attach(Node *node){
        node->next = head_->next;
        node->prev = head_;
        head_->next = node;
        node->next->prev = node;
    }
};