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

    int get(int key)
    {
        if (m.count(key) != 0)
        {
            int val = m[key]->second;
            l.erase(m[key]);
            l.push_front({key, val}); //访问过的元素移动到头部
            m[key] = l.begin();
            return val;
        }
        return -1;
    }

    void put(int key, int value)
    {
        if (m.count(key) != 0)
        { //已经存在
            l.erase(m[key]);
            l.push_front({key, value});
            m[key] = l.begin();
        }
        else
        {
            if (l.size() == cap)
            { //同步删除
                m.erase(l.back().first);
                l.pop_back();
            }
            l.push_front({key, value});
            m[key] = l.begin();
        }
    }

private:
    int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};