LRU缓存实现：用deque出错，list却正常的原因？

我在实现LeetCode的LRU缓存问题时，用list写的代码运行正常，但换成deque、逻辑完全一致的情况下却得到错误结果。查了不少deque和list对比的帖子，还是没找到原因，想知道为什么两者会有这种差异？

正常运行的list版本代码 #

class LRUCache 
{
public:
    list<int> dq;
    unordered_map<int, pair<int, list<int>::iterator>> mp;

    int size{};

    LRUCache(int capacity) 
    {
      size = capacity;  
    }
    

    int get(int key) 
    {
       int returnvalue{-1};
       
       if(mp.find(key) != mp.end())
       {
         returnvalue = mp[key].first;
         dq.erase(mp[key].second);
         dq.push_front(key);
         mp[key].second = dq.begin();
       }

      return returnvalue; 
    }
    
    void put(int key, int value) 
    {
       if(mp.find(key) != mp.end())
       { 
         dq.erase(mp[key].second);
         dq.push_front(key);
         mp[key] = {value,dq.begin()};
       }

       else
       {
         if(dq.size() < size)
         {
            dq.push_front(key);
            mp[key] = {value,dq.begin()};
         }
         else
         {
            mp.erase(dq.back());
            dq.pop_back();
            dq.push_front(key);
            mp[key] = {value,dq.begin()};         
         } 
       } 

    }
};

核心原因：迭代器有效性的差异 #

这俩容器的本质差异在于元素存储结构和迭代器失效规则，直接导致你的LRU逻辑在deque上失效：

• list的迭代器特性：list是双向链表，每个元素存在独立的节点中，节点之间通过指针连接。执行erase操作时，只会让被删除元素的迭代器失效，其他所有迭代器（包括未被删除元素的迭代器、begin()/end()）都保持有效；执行push_front时，只是在头部新增一个节点，不会影响任何现有迭代器的有效性。这完全适配LRU逻辑中需要保存、复用迭代器的需求。
• deque的迭代器特性：deque是分段连续的数组结构，元素存储在多个固定大小的数组段中。
  • 执行erase操作时，会导致被删除位置及之后的所有迭代器失效——因为删除元素后，后续元素会移动填补空缺，原来的迭代器指向的内存位置已经不是原来的元素了。
  • 执行push_front时，如果触发扩容（需要分配新的数组段），会导致所有迭代器全部失效；即使不扩容，首迭代器begin()也会失效。

你的LRU逻辑依赖unordered_map保存每个key对应的迭代器，当用deque时，每次erase或push_front都会导致一批迭代器失效，后续再使用这些失效的迭代器（比如下一次调用erase）就会触发未定义行为，表现为程序输出错误结果。

内容的提问来源于stack exchange，提问作者NB_1907