LRU Cache

• Time : O(1)
• Space : O(capacity)

c++

#include <list> 

list<int> lru;
unordered_map<int, list<int>::iterator> lrump;
unordered_map<int, int> cache;
int cap;

LRUCache::LRUCache(int capacity) {
    cap = capacity;
    cache.clear();
    lru.clear();
    lrump.clear();
}

int LRUCache::get(int key) {
    if(!cache.count(key)) return -1;
    set(key, cache[key]);
    return cache[key];
}

void LRUCache::set(int key, int value) {
    if(lrump.count(key)) lru.erase(lrump[key]);
    lru.push_front(key);
    lrump[key] = lru.begin();
    cache[key] = value;
    while(lru.size() > cap) {
        int k = lru.back(); lru.pop_back();
        lrump.erase(k);
        cache.erase(k);
    }
}