Implementing LRU Cache using doubly linked list and unordered map in c++

Question

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

Unrelated: `#include` being used in conjunction with `#include `, `#include `, and `#include ` suggests you don't know what `#include` is for, how it does it and why you shouldn't include it directly. [Here's a bit of reading that should help](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — user4581301, Jun 06 '22 at 18:26
Why is your `L` a `List` instead of `List`? If you track keys in the list then you can use `M.erase(L.back())`. Well, you need to store the iterator and string in the map so it's it bit more complicated than that. — Goswin von Brederlow, Jun 06 '22 at 18:38
`L.back()` returns a value, not an iterator. `--L.end()` will work so long as `capacity` is not allowed to be 0. What would be the point of a capacity of zero? — user4581301, Jun 06 '22 at 18:46
@GoswinvonBrederlow no , the map has first entry has int and second as iterator to a list . .end() returns the iterator (one ahead from the start , as now pointed out by an answer which helped me ) .last() returns the element — Ayush Agarwal, Jun 08 '22 at 02:35
@user4581301 yes sir , I have no idea which functions come under that library , but i tend to include it always , will see the resource , thnx — Ayush Agarwal, Jun 08 '22 at 02:37
I was thinking `if (*(it.second) == L.last())` but `--L.end()` works too. You still have the problem that your LRU is `O(n)` which makes it slow. You need to store the key in the list so you don't have to search the unordered_map. — Goswin von Brederlow, Jun 08 '22 at 07:36

score 0 · Accepted Answer · answered Jun 06 '22 at 18:57

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.

Implementing LRU Cache using doubly linked list and unordered map in c++

1 Answers1