146.LRU cache

146.LRU cache

题目链接

146. LRU 缓存 - 力扣（LeetCode）

完整代码

class LRUCache {
private:
    int cap=0;
    list<pair<int,int>> lru;   //真正的cache
    unordered_map<int,list<pair<int,int>>::iterator> mp;   //主要用处就是查找
public:
    LRUCache(int capacity) {
        cap = capacity;						//容量
    }
    
    int get(int key) {						//作为就是把最近访问的放在表头
        if(mp.find(key)!=mp.end()){							//有这个元素
            lru.splice(lru.begin(),lru,mp[key]);			//将一个 list 容器中的元素插入到另一个容器的指定位置
            return lru.begin()->second;				//返回元素
        }else{
            return -1;								//没有这个元素
        }
    }

    
    void put(int key, int value) {
        if(get(key)!=-1){				//cache中有key，调用get后自动插入到表头【key存在】
            lru.begin()->second = value;
        }else{			//【key不存在】
            if(lru.size()==cap){			//如果容量满了
                int delkey = lru.back().first;		 //记录最久未访问的key
                lru.pop_back();						 //pop掉，置换
                mp.erase(delkey);					 //查找表中也删除	
            }
            lru.emplace_front(key,value);			//头部生成一个元素
            mp[key]=lru.begin();					//加入查找表
        }
    }
};

/**
 * 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);
 */

参考资料

C++实现LRU缓存——LeetCode146 - 简书 (jianshu.com)