lru.cpp

struct node{
    int key;
    int value;
    node* prev;
    node* next;
};

template <class T>
class round_list {
    T* head;
public:
    round_list(): head(new T()){
        head->prev = head;
        head->next = head;
    }
    void push_back(T* n) {
        auto last = head->prev;
        n->prev = last;
        n->next = last->next;
        last->next->prev = n;
        last->next = n;
    }    
    void pop(T* n){
        n->next->prev = n->prev;
        n->prev->next = n->next;
    }
    T* first(){
        return (head != head->next) ? head->next : nullptr;
    }
};

class LRUCache {
    round_list<node> list;
    std::map<int, node*> map;
    int capacity;
public:
    LRUCache(int capacity): capacity(capacity) { }
    
    int get(int key) {
        auto it = map.find(key);
        if (it != map.end()) {
            list.pop(it->second);
            list.push_back(it->second);
            return it->second->value;
        }
        return -1;
    }
    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            list.pop(it->second);
            it->second->value = value;
            list.push_back(it->second);
        } else{
            if (map.size() == capacity){
                map[key] = list.first();
                list.pop(map[key]);
                map.erase(map[key]->key);
                map[key]->value = value;
                map[key]->key = key;
            }
            else{
                map[key] = new node {key, value, nullptr, nullptr};
            }
            list.push_back(map[key]);
        }
    }
};

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