LRU-cache(map+list(stl)).cpp

class LRUCache{
private:
    int _capacity;
    int _len;
    list<pair<int,int> > l;
    map<int, list<pair<int, int> >::iterator> mp;

public:
    LRUCache(int capacity) {
        _capacity = capacity;
        _len = 0;
        l.clear();
    }

    int get(int key) {
        map<int, list<pair<int, int>>::iterator>::iterator it = mp.find(key);
        if (it != mp.end()) {
            list<pair<int, int>>::iterator lit = (*it).second;
            int value = (*lit).second;
            l.push_front(make_pair(key, value));
            l.erase(lit);
            mp[key] = l.begin();
            cout << key << " " << value << endl;
            return value;
        }else{
            cout << key << " " << -1 << endl;
            return -1;
        }
    }

    void set(int key, int value) {
        map<int, list<pair<int, int>>::iterator>::iterator it = mp.find(key);
        if (it != mp.end()) {
            list<pair<int, int>>::iterator lit = (*it).second;
            l.erase(lit);
            l.push_front(make_pair(key, value));
            mp[key] = l.begin();

        }else{
            l.push_front(make_pair(key, value));
            mp[key] = l.begin();

            if (_len < _capacity) {
                _len ++;
            }else{
                //cout << "delete" << (l.back()).first << " " << (l.back()).second << endl;
                mp.erase((l.back()).first);
                l.pop_back();
            }
        }
    }
};