题解 | #设计LRU缓存结构#

实现LRU 两个容器 map<key,list::iterator> :实现快速查找，一一对应。 list 实现存储和最久未使用剔除

添加和删除函数：保持两个容器的一致性 当数据被访问的时候，先删除，再插入到list最前面 当数据添加的时候，先插入，再判断是否满，如果满了则剔除list末尾

    Node(int k=0,int v=0):key(k),val(v){}
    int key;
    int val;
};
class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
     int remove(list<Node>::iterator &ite)
    {
        int key=ite->key;
        int value=ite->val;
         
        ll.erase(ite);
        mm.erase(key);
        return value;
    }
    
    void set(int key,int value)
    {
        auto ite=mm.find(key);
        if(ite!=mm.end())
        {
            remove(ite->second);
        }
        ll.push_front(Node(key,value));
        mm[key]=ll.begin();
           if (cap<mm.size()){
               auto ite=ll.end();
               ite--;
                remove(ite);
            }
           
    }

    int get(int key)
    {
        auto ite=mm.find(key);
        if(ite==mm.end())
            return -1;
        else{
            int val=remove(ite->second);
            ll.push_front(Node(key,val));
            mm[key]=ll.begin();
            return val;
        }

    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        
        //list 数组的操作 
        //hashmap的作用
        cap=k;
        for(int i=0;i<operators.size();i++)
        {
            vector<int> temp=operators[i];
            if(temp[0]==1)
            {
                set(temp[1],temp[2]);
            }else if(temp[0]==2){
                ans.push_back(get(temp[1]));
            }
        }
        return ans;
    }
private:
    vector<int> ans;
    list<Node> ll;
    unordered_map<int,list<Node>::iterator > mm;
    int cap;
};