Description

Submission

class LRUCache {
    list<int> l;
    map<int, list<int>::iterator> key2iter;
    map<int, int> key2val;
    int capacity;
    
public:
    LRUCache(int capacity) {    
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(!key2val.count(key)) return -1;
        auto it = key2iter[key];
        l.push_front(key);
        l.erase(it);
        key2iter[key] = l.begin();
        return key2val[key];
    }
    
    void put(int key, int value) {
        if(get(key) != -1) {
            key2val[key] = value;
            return;
        } 
        
        if(key2val.size() >= capacity) {
            int keyEvict = *l.rbegin();
            key2val.erase(keyEvict);
            key2iter.erase(keyEvict);
            l.pop_back();
        }

        l.push_front(key);
        key2val[key] = value;
        key2iter[key] = l.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);
 */