class LRUCache {
public:
    list<pair<int,int>> my_list;
    int max_size = 0;
    LRUCache(int capacity) {
        max_size = capacity;
    }
    int get(int key) {
        auto it = my_list.begin();
        for(int i=0 ; i<my_list.size() ;i++,it++)
        {
            if(it->first == key) 
            {
                pair<int,int> tmp = *it;
                my_list.erase(it);
                my_list.push_front(tmp);
                return tmp.second;
            }
        }
        return -1;
    }
    void put(int key, int value) {
        auto it = my_list.begin();
        for(int i=0 ; i<my_list.size() ;i++,it++)
        {
            if(it->first == key)
            {
                my_list.erase(it);
                break;
            }
        }
        my_list.push_front({key,value});
        if(my_list.size() > max_size) my_list.pop_back();
        return ;
    }
};
/**
 * 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);
 */

class LRUCache {
public:
    struct  Node
    {
        int key;
        int value;
        Node* pre;
        Node* next;
        Node():key(0),value(0),pre(nullptr),next(nullptr) {}
        Node(int x,int y):key(x),value(y),pre(nullptr),next(nullptr) {}
    };
    LRUCache(int capacity) {
        _capacity = capacity;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre  = head;
    }
    int get(int key) {
        if(my_map.find(key) == my_map.end() ) return -1;
        Node* tmp = my_map[key];
        remove_node(tmp);
        add_head(tmp);
        return tmp->value;
    }
    void put(int key, int value) {
         if(my_map.find(key) == my_map.end() ) //不存在
         {
             Node* new_node = new Node(key,value);
             my_map[key] = new_node;
             add_head(new_node);
             size++;
             if(size > _capacity)
             {
                 my_map.erase(tail->pre->key);
                 remove_node(tail->pre);
             }
         }else
         {
             Node* tmp = my_map[key];
             tmp->value = value;
             remove_node(tmp);
             add_head(tmp);
         }
    }
    void add_head(Node* new_node)
    {
        new_node->pre = head;
        new_node->next = head->next;
        head->next->pre = new_node;
        head->next = new_node;
    }
    void remove_node(Node* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
private:
    int _capacity;
    Node* head;
    Node* tail;
    int size=0;
    unordered_map<int,Node*> my_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);
 */