LRU/LFU

LRU/LFU

146.LRU缓存

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = mp.find(key); //返回迭代器
        //如果 key 不存在则返回 -1
        if(it==mp.end()) return -1;
        //提升为最近使用的，将该结点移动到链表头
        lst.splice(lst.begin(), lst, it->second);
        return mp[key]->second;
    }
    
    void put(int key, int value) {
        if(mp.find(key)==mp.end()){ //key不存在
            if(lst.size()==cap){
                //删除最久未使用的元素
                mp.erase(lst.back().first);
                lst.pop_back();
            }
        }else{ //key已存在，抹去
            lst.erase(mp[key]);
        }
        //插入{key, value}
        lst.push_front({key, value});
        //添加mp中 key 到 list迭代器的映射
        mp[key] = lst.begin();
    }
private:
    //缓存容量
    int cap;
    //双向链表，存储 key-value
    list<pair<int, int>> lst;
    //哈希表，存储 key-(key, value) 迭代器
    unordered_map<int, list<pair<int, int>>::iterator> mp;
};

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