题目：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.

思路：

本题的一大特色是使用了双向链表。并且含有两个函数，spilt 和 insert 函数，插入就是把一个节点插入头结点之后的操作函数，而分开就是把当前节点从原有链表中分离出来。

需要说明的是：head 和 tail 节点并不算任何节点。

首先是get 函数：

首先用哈希表查找是否存在，不存在直接返回-1。如果存在，则由于访问了当前数据，先是分离当前节点，再将其插入到最前面。最后返回其值。

其次是set 函数：

先是使用get 函数判断是否存在，注意：如果存在，get 函数已经进行分离和插入操作了。

如果不存在，还需要判断是否超过大小。这里使用hash表的大小判断。没有越界，直接赋值新节点，越界了，先是分离，再插入新节点。

代码：

class LRUCache{private:    struct Node{        int key;        int value;        Node *prev,*next;        Node(int k,int v):key(k),value(v),prev(NULL),next(NULL){}    };        unordered_map
     
      mapper;    Node *head,*tail;    int capacity;        void insert(Node *target){        target->next=head->next;        head->next->prev=target;        head->next=target;        target->prev=head;    }        void split(Node *target){        target->prev->next=target->next;        target->next->prev=target->prev;        //insert(target);    }    public:    LRUCache(int capacity) {        this->capacity=capacity;        head=new Node(0,0);        tail=new Node(0,0);        head->next=tail;//设立开头结尾指针，方便操作        tail->prev=head;    }        int get(int key) {        if(mapper.find(key)==mapper.end()){            return -1;        }        Node *target=mapper[key];                if(target!=head->next){//如果不是第一个，那么根据最小使用原则，使用了一次target，把他挪到                             //最前面            split(target);            insert(target);        }                return target->value;    }    void set(int key, int value) {        if(get(key)!=-1){//  数值已经存在            head->next->value=value;//get 这个函数里面已经有分离 插入 这些操作了.            return;                    }        //下面判断不存在，但是要考虑是否越界                Node *tmp=NULL;        if(mapper.size()==capacity){            tmp=tail->prev;            split(tmp);            mapper.erase(tmp->key);            tmp->value=value;            tmp->key=key;        }/*            tmp->value=value;            tmp->key=key;*/  // 不能这么写，因为上面定义的tmp是一个单链表指针，这样赋值是双链表指针        tmp=new Node(key,value);        mapper[key]=tmp;        insert(tmp);    }};