双向链表维护 pair<key, value>，每次用到的一个 key 都把它放到链表头部，容量满时删除链表尾部节点即可。

unordered_map<key, list<pair<key, value>>::iterator> 维护 key 与 链表节点的迭代器映射

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

    }

    int get(int key) {
        if(map.find(key) != map.end()) {
            push_front(key);
            return (*map[key]).second;
        }
        return -1;
    }

    void put(int key, int value) {
        if(map.find(key) != map.end()) {
            push_front(key);
            (*map[key]).second = value;
        } else {
            if(stack.size() >= capacity) {
                int eraseKey = stack.back().first;
                stack.pop_back();
                map.erase(eraseKey);
            }
            stack.emplace_front(key, value);
            map[key] = stack.begin();
        }
    }

private:
    void push_front(int key) {
        int val = (*map[key]).second;
        stack.erase(map[key]);
        stack.emplace_front(key, val);
        map[key] = stack.begin();
    }

    int capacity;
    list<pair<int, int>> stack; // store key, val
    unordered_map<int, list<pair<int, int>>::iterator> map; // key, ptr
};