C++ List and Map solution


#1

unordered_map<int, int>store; // key value
unordered_map<int, list::iterator> keystore;
unsigned int size1;
listlru;

LRUCache::LRUCache(int capacity) {
size1 = capacity;
// clear all containers
store.clear();
lru.clear();
keystore.clear();
}

int LRUCache::get(int key) {
auto it = keystore.find(key);

if(it != keystore.end()) { // If key exists ....remove it from the list ans push it into the list at front (as 
                           // recently used)
    lru.erase(it->second);
    lru.push_front(key);
    it->second = lru.begin();
    
    return store[key];
} 
return -1;

}

void LRUCache::set(int key, int value) {
auto it = keystore.find(key);
store[key] = value;

if(it==keystore.end()){    // If not exists add it into list
    lru.push_front(key);
    keystore[key] = lru.begin();
    
    if(lru.size()>size1){  // If list size overflows remove least recently used key (last item of the list)
        int removekey = lru.back();
        lru.pop_back();
        store.erase(removekey);
        keystore.erase(removekey);
    }  
} 
else {  // if give key already exists update it and add it to the front of the lru list
    lru.erase(it->second); 
    lru.push_front(key);
    it->second = lru.begin(); 
}

}