146. LRU Cache.cpp

/*
list version
*/

class LRUCache {
public:
    
    list<pair<int,int>> q;
    unordered_map<int,list<pair<int,int>>::iterator> hash;
    list<pair<int,int>>::iterator it;
    int cap;
    
    LRUCache(int capacity) {
        cap = capacity;
        q.clear();
        hash.clear();
    }
    
    int get(int key) {
        
        if(hash.count(key)==0){ 
            return -1; 
        }
        
        // move node to begin()
        q.splice(q.begin(), q, hash[key]);
        
        return hash[key]->second;
    }
    
    void put(int key, int value) {
        auto itr = hash.count(key);  
        
        if(itr>0) { 
            hash[key]->second= value; 
            q.splice(q.begin(), q, hash[key]);
        }else{ 
            if(q.size() == cap) { 
                hash.erase(q.back().first);
                q.pop_back();
                q.push_front(pair<int,int>(key,value)); 
            }else{ 
                q.push_front(pair<int,int>(key,value)); 
            }
            hash[key] = q.begin();
        }

    }
    
    
};