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

CodePudding user response：

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.