Implementing LRU cache using std::map and std::list in C++. Can't get required output

Question

I am trying to write C++ code to implement a cache. The cache uses Least Recently Used policy explained by the behaviour:

If the cache has a capacity to store 5 keys like 5 3 2 1 4 then if next key=1 comes as a hit, the cache order becomes 1 5 3 2 4.
If next key=6 comes as a miss, the cache order becomes 6 1 5 3 2.

Code I have written below works for Test case 1 and its Output, but not for Test case 2 and its Output. I have shown my code, inputs, and expected outputs below.

Code:

#include <iostream>
#include <map>
#include <list>
#include <algorithm>

using namespace std;

struct Node {
    int value, key;
    Node (int k,int v):value(v),key(k){};
}typedef Node;

class Cache{
protected :
    list <Node> l;
    map<int, list<Node>::iterator> mp;
    int cp;
    virtual void set(int,int) =0;
    virtual int get(int)=0;

}typedef Cache;

class LRUCache:public Cache{

    void removeback(){
        mp.erase(--l.end()->key);
        l.pop_back();
    }
    void addatfront(int k, int v) {
        Node *node = new Node(k,v);
        if (mp.size() == cp)
            removeback();
        //l.push_front({k,v});
        l.push_front(*node);
        mp[k] = l.begin()
    } 
    void movetohead(list<Node>::iterator  arg, int new_val){
        (*arg).value = new_val;
        l.splice(l.begin(),l,arg);
        mp[arg->key]= l.begin();
    }
public:
    LRUCache(int &cap){
        cp = cap;
    }
    void set(int k,int v){
        if (mp.find(k)!=mp.end()){
            if (mp.size()>1)
                movetohead(mp[k],v);
            else
                l.begin()->value = v;
        }
        else
            addatfront(k,v);
    }

    int get (int k){
        if (mp.find(k)!=mp.end())
            return mp[k]->value;
        return -1;
    }
}typedef LRUCache;

int main()
{
    int n, capacity,i;
    cin>> n>> capacity;
    LRUCache l(capacity);
    for (i =0;i< n;i++){
        string command;
        cin>> command;
        if (command == "get"){
            int key;
            cin >> key;
            cout<< l.get(key)<< endl;
        }
        else if(command == "set"){
            int key,value;
            cin>> key>>value;
            l.set(key, value);
        }
    }
    return 0;
}

Input Test case 1:

3 1
set 1 2
get 1
get 2

Output:

2  
-1

Input Test case 2:

22 4
set 7 1905
get 16
get 4
set 20 1738
get 14
set 12 320
set 4 1382
set 11 1049
set 8 1372
get 11
set 7 937
set 9 654
set 11 1727
get 1
set 13 1945
get 5
get 15
set 6 1668
set 8 270
set 1 604
get 20
get 5`

Output:

-1
-1
-1
1049
-1
-1
-1
1738
-1

In the actual output, I see -1 instead of 1738 for the second-to-last line of output.

Side notes, you are still using some "C" style syntax elements. struct Node { } typedef Node;}, the typedef should not be there. Also storing iterators for later use is not a good idea in general (lot of containers can invalidate iterators). Consider using a std::vector and store indices. C++ idiom, "it is almost always std::vector" (only use list if you have a lot of inserts at random places) — Pepijn Kramer
– Pepijn Kramer, Commented Sep 16 at 7:18
Are you sure that that is the expected output? If the capacity is 4, the 20 -> 1738 entry should have been thrown out of the cache long before it's looked up. — molbdnilo
– molbdnilo, Commented Sep 16 at 8:29
Side note: you say you don't want a solution using a linked list, but what do you think std::list is? — molbdnilo
– molbdnilo, Commented Sep 16 at 8:32
@ArifMahmood "Giving inputs to this program is most time consuming thing" -- Hence, the input should be eliminated from your minimal reproducible example. Make it so that someone can easily copy the code, compile it, then run it to reproduce the error. Eliminating the input (by hardcoding the problematic case) makes it easier to reproduce the error. — JaMiT
– JaMiT, Commented Sep 16 at 12:53

Aman Sharma · Accepted Answer · 2025-09-16 13:12:01Z

1

Other than your code using C instead of C++ syntax for defining structs, the two errors I can see are
- In LRUCache::removeback you need to be erasing l.end()->key, but are removing the key just smaller than this. You want to remove l.end()->key since this is what stores the iterator of the last entry in the list.
- In LRUCache::get you need to call movetohead if you do find the key you are looking for to comply with the behaviour you are looking for. The implementation would be something like this:

int get (int k){
    auto it = mp.find(k);
    if (it!=mp.end()) {
        movetohead(it->second, it->second->value);
        return mp[k]->value;
    }
        
    return -1;
}

I tried running your code with these two changes and it is giving the output you are expecting.

answered Sep 16 at 13:12

Aman Sharma

475 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Arif Mahmood Oct 31 at 13:14

What is difference between l.end() and l.back() for this specific example? Why l.end() gives right answer, but not l.back()? I mean l.back() seems to be equal to --l.end(). I see c# has a l.back() equivalent l.Last, but not l.end() equivalent. What to do in that case?

Collectives™ on Stack Overflow

Implementing LRU cache using std::map and std::list in C++. Can't get required output

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related