146. LRU Cache.cpp

/*
deque version
Error with test data
["LRUCache","put","put","put","put","get","get"]
[[10],[99,27],[8,10],[6,29],[1,9],[6],[1]]

Because push_front and push_back cause iterator invaild.

*/

#include <deque>
#include <unordered_map>

class LRUCache {
public:
    
    deque<pair<int,int>> q;
    unordered_map<int,deque<pair<int,int>>::iterator> hash;
    deque<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_to_front(key);
        return hash[key]->second;
    }
    
    void put(int key, int value) {
        auto itr = hash.count(key);  
        
        if(itr>0) { 
            hash[key]->second= value; 
            move_to_front(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();
        }

    }
    
    void move_to_front(int key){
        int k = hash[key]->first;
        int v = hash[key]->second;
        q.erase(hash[key]); 
        q.push_front(pair<int,int>(k,v)); // error 加上去 使map 1 point 變成6 
        hash[key] = q.begin(); 
    }
    
};