146. LRU Cache

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {

    }

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        touch(it);
        return it->second.first;            //it->!!!!!!
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) touch(it);        //faster to give touch (it) instead of (key)
            else {
                if (cap == cache.size()) {        
                    //faster to get cache.size():::constant instead used.size():::linear(C++98), actually it turns to constant in C++11
                    cache.erase(used.back());
                    used.pop_back();
                }
                used.push_front(key);
            }
        cache[key] = make_pair(value, used.begin());
    }
private:
    int cap;
    list<int> used;
    unordered_map<int, pair<int, list<int>::iterator>> cache;
    void touch(unordered_map<int, pair<int, list<int>::iterator>>::iterator it) {    
        used.erase(it->second.second);
        used.push_front(it->first);
        it->second.second = used.begin();    //don't forget this to update the iterator in the map!!!!!
    }
};

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