什么会导致此 LRU 实现（哈希映射和双向链表）中的运行时错误？

Question

我在 LeetCode 上遇到运行时错误，但这在我的 Linux 系统上运行良好，最大测试用例的用户时间为 0.046。输出与 LeetCode 上的预期输出完全匹配。我的解决方案使用哈希图和双向链表。 hashmap 将迭代器存储到链表节点（除了 key->value 对），以便可以更新列表 O(1) 而不是 O(n)。让它适用于多个测试用例，但我在缓存大小为 512 和 2019 条指令的测试用例上遇到运行时错误。

class LRUCache {
public:
    LRUCache(int _capacity) { capacity = _capacity; }    
    int get(int key) {
        if(hmap.find(key) == hmap.end()) return -1;
        addq(key);
        return hmap[key].first;
    }    
    void put(int key, int value) {
        list<int>::iterator ptr = addq(key);
        hmap[key] = make_pair(value, ptr);
    }
private:
    list<int> q;
    unordered_map<int, pair<int,list<int>::iterator>> hmap;
    int capacity;
    list<int>::iterator addq(int key) {
        if(hmap.find(key) == hmap.end()) {
            if(q.size() == capacity) {
                int to_pop = q.back();
                hmap.erase(to_pop);
                q.pop_back();
            }                        
        }
        else q.erase(hmap[key].second);
        return q.insert(q.begin(), key);
    }
};

Answer 1

您的 get (int key) 功能有问题。当您访问缓存时，您必须使条目无效并更新迭代器。您可以使用 addq 函数执行此操作，但永远不会更新 hmap 中的相应条目。因此会发生运行时错误，因为您随后访问了一个已被 addq 函数使无效的迭代器。

查看以下代码段：

if(hmap.find(key) == hmap.end()) return -1;
addq(key);
return hmap[key].first;

addq returns 一个迭代器，但您从不更新映射中的迭代器，所以这应该是：

hmap[key].second = addq(key);

什么会导致此 LRU 实现（哈希映射和双向链表）中的运行时错误？

What could cause runtime error in this LRU implementation (hashmap and doubly-linked list)?

c++

runtime-error

linked-list

hashmap

lru