Solution in c++ using STLs


#1
map<int,int> cache;
deque<int> lru;
int cap;
set<int> s;

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

int LRUCache::get(int key) {
    
    if(cache.count(key) > 0)
    {
        int id;
        for(int i = 0; i < lru.size(); i++)
        {
            if(lru[i] == key)
            {
                id = i;
                break;
            }
        }
        lru.erase(lru.begin()+id);
        lru.push_back(key);

        return cache[key];
    }
    else
    {
        return -1;
    }
}

void LRUCache::set(int key, int value) {
    
    if(cache.size() < cap or cache.count(key) > 0)
    {
        cache[key] = value;
        
        if(s.find(key) != s.end())
        {
            int id;
            for(int i = 0; i < lru.size(); i++)
            {
                if(lru[i] == key)
                {
                    id = i;
                    break;
                }
            }
            lru.erase(lru.begin()+id);
            lru.push_back(key);
        }
        else
        {
            s.insert(key);
            lru.push_back(key);
        }
    }
    else
    {
        int val = lru.front();
        lru.pop_front();
        cache.erase(val);
        s.erase(val);
        cache[key] = value;
        s.insert(key);
        lru.push_back(key);
    }
}

#2

Why don’t you use map in get key function like here

int LRUCache::get(int key)
{
if (cache.find(key)!=cache.end())
return cache[key];
else
return -1;
}


#3

we dont require set:-

map<int,int> cache;
deque lru;
int cap;
LRUCache::LRUCache(int c)
{
cap=c;
cache.clear();
lru.clear();
}

int LRUCache::get(int key)
{
if(cache.find(key)!=cache.end())
{
int id=-1;
for(int i=0;i<lru.size();i++)
if(lru[i]==key){id=i;break;}
lru.erase(lru.begin()+id);
lru.push_back(key);
return cache[key];
}
else return -1;
}

void LRUCache::set(int key, int value)
{
if(cache.find(key)!=cache.end())
{
cache[key]=value;
int id=-1;
for(int i=0;i<lru.size();i++)
if(lru[i]==key){id=i;break;}
lru.erase(lru.begin()+id);
lru.push_back(key);
}
else if(lru.size()<cap)
{
cache[key]=value;lru.push_back(key);
}
else
{
int val=lru.front();
lru.pop_front();
cache.erase(val);
cache[key]=value;
lru.push_back(key);
}
}


#4

Why are we using set here?