为何我的LRU Cache C++实现会触发堆使用后释放错误？

问题背景 #

我在LeetCode上遇到LRU缓存实现问题，要求get和put操作的平均时间复杂度为O(1)。编写第一版代码后，发现当put操作中key≠value时，会触发Runtime Error(heap-use-after-free)。改用存储<key,value>对的方式实现后代码被成功接受，但不清楚第一版问题出在哪。

第一版错误代码 #

#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;//缓存中不存在该键
        int val = *um[key];//从哈希表中获取对应迭代器指向的值
        cache_list.erase(um[key]);//删除该迭代器对应的元素
        cache_list.push_front(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());
                cache_list.pop_back();
            }
        }
        else cache_list.erase(um[key]);//缓存中存在该键，删除对应元素
        cache_list.push_front(value);//将新值移到链表头部
        um[key] = cache_list.begin();//更新哈希表中的迭代器
    }
};

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

修正后的可通过代码 #

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

错误原因解析 #

第一版代码的核心问题是完全混淆了key和value的存储关联逻辑，导致哈希表与链表的绑定关系彻底错误：

1. 链表仅存储value，哈希表的key是缓存key，但value是指向链表中value的迭代器——这种设计无法建立缓存key与对应条目的正确关联。
2. 缓存满时执行um.erase(cache_list.back())是致命错误：你试图用链表尾部的value作为key去删除哈希表条目，但哈希表的key是缓存的key，不是value。比如put(10,20)后，链表存20，哈希表key=10对应指向20的迭代器；当删除尾部时，cache_list.back()是20，用它当key删哈希表，会删除key=20的条目（如果存在），而非对应缓存key=10的条目。
3. 上述错误会导致哈希表中残留大量悬空迭代器：比如key=10对应的迭代器指向的20被从链表删除后，哈希表中key=10的迭代器变成无效状态，后续访问*um[key]就会触发heap-use-after-free（访问已释放的内存）。
4. 此外，若多个key对应同一个value，get操作移动value到链表头部后，所有关联该value的key的迭代器都会指向同一个链表节点，一旦其中一个key触发删除操作，其他key的迭代器都会失效，进一步引发内存错误。

本质上，LRU需要跟踪的是缓存条目（key-value对）的使用顺序，而非单独的value顺序。必须将key和value绑定存储在链表中，才能在删除最久未使用条目时，通过链表中的key找到哈希表对应条目删除，同时保证哈希表的迭代器始终指向有效的缓存条目。

内容的提问来源于stack exchange，提问作者吳承宇