为什么这个LRU缓存的实现不起作用？

Question

我在LeetCode上遇到了这个问题，需要我们以O(1)的平均时间复杂度实现LRU缓存函数“get”和“put”。

我尝试了类似的方法这里，它实现了LRU缓存，我的代码是这样的

#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";
}

当“put”函数中的“key != value”时，此实现会给出运行时错误（heap-use-after-free）。

看到解决方案部分后，我尝试将对的迭代器存储在unordered_map中，其余相同，并且实现被接受。代码如下

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();
    }
};

但是，我仍然不明白为什么第一个实现不可行，我是否以错误的方式使用迭代器或其他什么？

Answer 1

um.erase(cache_list.back())

从映射中删除最后一个值，这将导致映射和列表之间不一致，从而在将来的某个时刻当您尝试取消引用无效迭代器时导致崩溃。您可以通过搜索迭代器来修复它：

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();

但最好像您所做的那样将密钥存储在缓存列表中。