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

import "container/list"

type LRUCache struct {
    //缓存容量
    cap int
    //双向链表，存储 key-value
    lst *list.List
    //哈希表，存储 key-(key, value) 迭代器
    mp map[int]*list.Element
}

type pair struct {
    key   int
    value int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap: capacity,
        lst: list.New(),
        mp:  make(map[int]*list.Element),
    }
}

func (this *LRUCache) Get(key int) int {
    //返回迭代器
    element, ok := this.mp[key]
    //如果 key 不存在则返回 -1
    if !ok {
        return -1
    }
    //提升为最近使用的，将该结点移动到链表头
    this.lst.MoveToFront(element)
    return element.Value.(pair).value
}

func (this *LRUCache) Put(key int, value int) {
    if element, ok := this.mp[key]; !ok { //key不存在
        if this.lst.Len() == this.cap {
            //删除最久未使用的元素
            back := this.lst.Back()
            this.lst.Remove(back)
            delete(this.mp, back.Value.(pair).key)
        }
    } else { //key已存在，抹去
        this.lst.Remove(element)
    }
    //插入{key, value}
    newElement := this.lst.PushFront(pair{key: key, value: value})
    //添加mp中 key 到 list迭代器的映射
    this.mp[key] = newElement
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */