LeetCode 146. LRU缓存机制-526互联

class LRUCache {
public:
    struct node
    {
        int key,val;
        node *l,*r;
        node(int a,int b)
        {
            l=r=NULL;
            key=a;
            val=b;
        }
    }*L,*R;
    unordered_map<int,node*> mp;//保存key和节点的映射，使得查找O(1)
    int n;
    LRUCache(int capacity) {
        L=new node(-1,-1),R=new node(-1,-1);//创建双端链表两头节点
        L->r=R;R->l=L;
        n=capacity;
    }
    
    int get(int key) {
        if(mp.count(key))
        {
            auto p=mp[key];
            //更新优先级
            remove(p);
            insert(p);
            return mp[key]->val;
        }
        else return -1;
    }
    
    void put(int key, int value) {
        if(mp.count(key))
        {
            auto p=mp[key];
            p->val=value;
            remove(p);
            insert(p);
        }
        else//插入新节点
        {
            node * t=new node(key,value);
            if(mp.size()==n)//删除最久未使用的节点
            {
                auto p=R->l;
                remove(p);
                mp.erase(p->key);
                delete p;
            }    
            mp[key]=t;
            insert(t);
        }
    }
    void insert(node *p)//往头部插入
    {
        L->r->l=p;
        p->r=L->r;
        L->r=p;
        p->l=L;
    }
    void remove(node *p)
    {
        p->r->l=p->l;
        p->l->r=p->r;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */