[C++] LRU Cache

https://leetcode.com/problems/lru-cache/description/

 

 

#include <iostream>
#include <list>
#include <map>


using namespace std;


class Node {
public:
    int key;
    int val;

    Node() {}
    Node(int key=-1, int val=-1) : key(key), val(val) {}
    ~Node() {}
};


class LRUCache {
public:
    list<Node> ll;
    map<int,list<Node>::iterator> dict;
    int capacity;
    int cnt;

    LRUCache(int capacity) : capacity(capacity), cnt(0) {}

    int get(int key) {
        if (dict.find(key) != dict.end()) {
            auto it = dict[key];
            Node node(*it);
            ll.erase(it);
            ll.push_back(node);
            dict[key] = prev(ll.end());
            return node.val;
        }
        else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (dict.find(key) != dict.end()) {
            auto it = dict[key];
            Node node = Node(*it);
            node.val = value;
            ll.erase(it);
            ll.push_back(node);
            dict[key] = prev(ll.end());
        }
        else {
            if (cnt == capacity) {
                Node popped = ll.front();
                dict.erase(popped.key);
                ll.pop_front();
                Node node = Node(key, value);
                ll.push_back(node);
                dict[key] = prev(ll.end());
            }
            else {
                Node node = Node(key, value);
                ll.push_back(node);
                dict[key] = prev(ll.end());
                cnt++;
            }
        }
    }
};




int main() {
    LRUCache lru(2);
    lru.put(2, 1);
    lru.put(1, 1);
    lru.get(2);
}