LRU

class  {
public:
    list<int> link;
    map<int, int> m;
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(m.find(key) == m.end()) {
            return -1;
        } else {
            link.remove(key);
            link.push_front(key);
        }
        return m[key];
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {       
            m[key] = value;
            link.remove(key);
            link.push_front(key);
        } else {                            //不存在
            if (m.size() >= capacity) {
                int keyLast = link.back();
                link.pop_back();
                m.erase(keyLast);
                
                link.push_front(key);
                m[key] = value;
            } else {
                m[key] = value;
                link.push_front(key);
            }
        }
    }
};