I have implemented LRU cache after watching multiple online sources but am unable to understand why the code outputs value "alpha" for 3 , please suggest how to cure this in the LRU cache implementation . I have checked multiple online sources but all of them are for implementing int to int mapping , here i want to give input as integer and store a string which hasnt been covered anywhere
Here is the code :
#include <iostream>
#include<bits/stdc++.h>
// we have used doubly linked list as it was readily availaible in the c++ stl library
#include <list>
// we do not need ordered map , unordered map is enough for hashing
#include <unordered_map>
using namespace std;
class LRU_Cache{
public:
// this cache stores strings
// integers are mapped to strings , i.e. we can access data using integers
list<string> L;
unordered_map<int,list<string>::iterator > M;
int capacity ;
LRU_Cache(int cap){
capacity = cap;
L.clear();
M.clear();
}
int size(){
return capacity;
}
void feedin(int key , string data){
// if key not present in cache already
if(M.find(key)==M.end()){
// when cache is full then remove last then insert else just insert
// so we just need if rather than if else
if(L.size()==capacity){
// remove the last element first from map then from list
// removing from map
for(auto it:M){
if((it.second) == L.end()){
// M[it.first] = M.end();
M.erase(it.first);//it.first
break;
}
}
// removing from list
L.pop_back();
}
// key is not present and cache is not full case
else{
}
// now insertion
L.push_front(data);
M[key]=L.begin();
return;
}
// key is present in cache already
else{
// erase the already present data for that key in the list
L.erase(M[key]);
// add the data to the list
L.push_front(data);
// reassign the value of iterator in the map for that key
M[key]=L.begin();
// we do not need to remove the last value here ,
// since size of cache remains same after this operation
return;
}
}
string gettin(int key){
if(M.find(key)==M.end()){
return "0";
}
else{
return *M[key];
}
}
};
int main()
{
// Declaring a LRU Cache
LRU_Cache lru1(2);
// Checking the size
cout<<"The size of this LRU Cache is : " <<lru1.size()<<endl;
// Adding data to it
lru1.feedin(3,"beta");
lru1.feedin(1,"alpha");
lru1.feedin(8,"gamma");
// checking the data now
cout<<lru1.gettin(1)<<endl;
cout<<lru1.gettin(3)<<endl;
cout<<lru1.gettin(6)<<endl;
cout<<lru1.gettin(8)<<endl;
return 0;
}
And here is the output
alpha gamma 0 gamma
EDIT : The doubt has been solved now and the code is now available at https://github.com/ayush-agarwal-0502/LRU-Cache-Implementation for anyone who was trying to implement a LRU Cache and needs explanation or code
In feedin replace
if((it.second) == L.end())
with
if((it.second) == --L.end())
and ensure capacity can never be zero. This shouldn't be much of a restriction because there is no point to a LRU cache that can't cache anything.
Explanation:
I believe the mistake is in believing that L.end() returns an iterator referring to the last item in L. It doesn't. end() returns a sentinel marking the end of the list. It doesn't correspond to any elements in the list, and this is why it is useable as the item not found case in searches.
In feedin,
if((it.second) == L.end())
compares L iterators stored in M to an iterator that is guaranteed to not be in L and thus will not be in M. Nothing is ever found. To get an iterator for the last item in L, you need --L.end(). Note that --L.end() is valid when the list is not empty, something guaranteed by a capacity greater than 0.