C++ code with 2 helper functions


#1
#include<list>
unordered_map<int, list<int>::iterator> um_dll;
unordered_map<int, int> key_val;
int cap;
int curr;
list<int> dll;

void delete_key(int key)
{
    if(key_val.find(key) == key_val.end())
        return;
    dll.erase(um_dll[key]);
    --curr;
    key_val.erase(key);
}

void insert_key_val(int key, int value)
{
    key_val[key] = value;
    dll.push_front(key);
    um_dll[key] = dll.begin();
    ++curr;
}

LRUCache::LRUCache(int capacity) 
{
    um_dll.clear();
    key_val.clear();
    dll.clear();
    cap = capacity;
    curr = 0;
}

int LRUCache::get(int key) 
{
    if(key_val.find(key) == key_val.end())
    {
        return -1;
    }
    else
    {
        int val = key_val[key];
        delete_key(key);
        insert_key_val(key, val);
        return val;
    }
}

void LRUCache::set(int key, int value) 
{
    if(key_val.find(key) != key_val.end())
    {
        delete_key(key);
        insert_key_val(key, value);
    }
    else
    {
        if(curr == cap)
        {
            int least_used = dll.back();
            delete_key(least_used);
            insert_key_val(key, value);
        }
        else
        {
            insert_key_val(key, value);
        }
    }
}

#2
#include<list>
unordered_map<int,int>ump;
list<int>l;
int capacity;
LRUCache::LRUCache(int cap) {
    ump.clear();
    l.clear();
    capacity=cap;
}

int LRUCache::get(int key) {
    list<int>::iterator it;
    if(ump.find(key)!=ump.end())
    {
        int x= ump[key];
        it = find(l.begin(),l.end(),key);
        l.erase(it);
        l.push_back(key);
        return x;
    }
    else
    return -1;
}

void LRUCache::set(int key, int value) {
    list<int>::iterator it;
    if(ump.find(key)!=ump.end())
    {
        it = find(l.begin(),l.end(),key);
        l.erase(it);
        ump[key] = value;
        l.push_back(key);
        return;
    }
    if(l.size()>=capacity)
    {
        int x = l.front();
        ump.erase(x);
        l.pop_front();
        l.push_back(key);
        ump[key] = value;
    }
    else
    {
        l.push_back(key);
        ump[key]= value;
    }
}