Why doesn't this implementation of LRU cache work?

Question

I encountered this problem on LeetCode, which needs us to implement the LRU cache functions "get" and "put" in O(1) average time complexity.

I tried the similar method here, in which it implements LRU cache, and my code is like this

#include <list>
#include <unordered_map>
#include <iostream>
using namespace std;

class LRUCache {
public:
    list<int> cache_list;
    unordered_map<int,list<int>::iterator> um;
    int cache_size;

    LRUCache(int capacity) {
        cache_size = capacity;
        um = unordered_map<int,list<int>::iterator>();
        cache_list = list<int>();
    }
    
    int get(int key) {
        if(!um.count(key))return -1;//the key is not present in cahce_list
        int val = *um[key];//if the key has corresponding iterator in unordered map, retrieve the value
        cache_list.erase(um[key]);//remove the corresponding iterator
        cache_list.push_front(val);//push the value to the front of cache_list
        um[key] = cache_list.begin();//store "cache_list.begin()" iterator in the unordered_map 
        return val;
    }
    
    void put(int key, int value) {
        if(!um.count(key)){//the key is not in the cache_list
            if(cache_size){//the cache is not full yet
                cache_size--;
            }
            else{//the cache is full, so remove the least recently used element
                um.erase(cache_list.back());
                cache_list.pop_back();
            }
        }
        else cache_list.erase(um[key]);//the key is in the cache_list, so remove the corresponding
                                       //iterator from the cache_list
        cache_list.push_front(value);//push the value to the front of cache_list
        um[key] = cache_list.begin();//store "cache_list.begin()" iterator in the unordered_map 
    }
};

int main()
{
    LRUCache cache(5);
    std::cout << cache.get(0) << "\n";
    cache.put(10,20);
    cache.put(30,40);
    cache.put(50,60);
    cache.put(60,70);
    cache.put(70,80);
    std::cout << cache.get(10) << "\n";
    std::cout << cache.get(40) << "\n";
    std::cout << cache.get(30) << "\n";
    std::cout << cache.get(60) << "\n";
    std::cout << cache.get(70) << "\n";
    std::cout << cache.get(50) << "\n";
    cache.put(0,0);
    std::cout << cache.get(0) << "\n";
    std::cout << cache.get(10) << "\n";
    std::cout << cache.get(40) << "\n";
    std::cout << cache.get(30) << "\n";
    std::cout << cache.get(60) << "\n";
    std::cout << cache.get(70) << "\n";
    std::cout << cache.get(50) << "\n";
}

This implemenation would give Runtime Error(heap-use-after-free) when "key != value" in the "put" function.

After seeing the solution section, I tried to store <key,value> pair's iterator in the unordered_map, the rest are the same, and the implementation was accepted. The code is as follows

class LRUCache {
public:
    list<pair<int, int>> cache_list;
    unordered_map<int, list<pair<int, int>>::iterator> um;
    int cache_size;

    LRUCache(int capacity) {
        cache_size = capacity;
    }

    int get(int key) {
        if (!um.count(key))
            return -1;
        int val = um[key]->second;
        cache_list.erase(um[key]);
        cache_list.push_front({key, val});
        um[key] = cache_list.begin();
        return val;
    }

    void put(int key, int value) {
        if (!um.count(key)) {
            if (cache_size) {
                cache_size--;
            }
            else{
                um.erase(cache_list.back().first);
                cache_list.pop_back();
            }
        }
        else cache_list.erase(um[key]);
        cache_list.push_front({key, value});
        um[key] = cache_list.begin();
    }
};

However, I still can't figure out why the first implementaion is not viable, do I use the iterators in the wrong way or something?

Answer 1

um.erase(cache_list.back()) removes the last value from the map rather than the last key, this'll lead to an inconsistency between your map and list leading to a crash at some point in the future when you try to dereference an invalid iterator. You could fix it by searching for the iterator:

auto to_remove = cache_list.end();
to_remove--;
for (auto it = um.begin(); it != um.end(); ++it)
{
  if (it->second == to_remove) {
    um.erase(it);
    break;
  }
}
cache_list.pop_back();

but its probably better to just store the keys in the cache list as you've done.