提防 STL 容器迭代器非法化

对于 deque 或者 list 之类的容器，不少算法会有需求在“迭代的过程中”对容器进行操作。直觉告诉我们，对一个正在被读取的对象做写操作是危险的。不巧今天也在 LRU 的实现上犯了这样的小错误，而且是以一种相对隐蔽的形式出现的。

LRU——“最久未使用”——的设计用途是在小块的存储空间中放下最常用的数据。它的做法和书桌上垒着的书本有异曲同工之处。

• 每当放上一本新书的时候，都是放在整一摞书的最上面。
• 每当取阅一本老书的时候，会把它抽出来，读完之后同样也是放在最上面。

所以不难推论出，整一堆书里越靠底下的书就是越老的书。如果给出一个范围 N，丢掉 N 本以下的书，这就是一个大小为 N 的 LRU 缓存，里面都是最近有被使用过的 N 本书。其他生活中的类比有音乐播放器里的“最近听过的100首歌” (N=100)。

换句话说，访问的时候有两个步骤。

1. 找找这个元素
2. 删除这个元素（没有就不需要删除了）并放到最前面

#include <deque>
#include <utility>

using namespace std;

class LRUCache {
public:
    using key_t = int;
    using value_t = int;
    using pair_t = pair<key_t, value_t>;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    value_t get(key_t key) {
        for(auto iter = container.begin(); iter != container.end(); iter++) {
            if(iter->first == key) {
                value_t v = iter->second;
                container.push_front(*iter);  // 放到最前
                container.erase(iter);        // 删除
                return v;
            }
        }
        return value_t{};  // 没找到
    }
    
    void put(key_t key, value_t value) {
        for(auto iter = container.begin(); iter != container.end(); iter++) {
            if(iter->first == key) {
                iter->second = value;
                container.push_front(*iter);  // 放到最前
                container.erase(iter);        // 删除
                return;
            }
        }
        container.push_front({key, value});   // 放到最前，新元素
        if(container.size() > capacity) {     // 丢弃超出容量的最末尾元素
            container.pop_back();
        }
    }
    deque<pair_t> container;
private:
    int capacity;
};

这个实现会导致一些大的测试案例出现奇怪的错误。并且偶然发现，把 deque 简单地换成 list，错误就会全部消失。诚然这个例子里确实更适合使用双向链表 list，因为它提供了更快的元素删除方法。但是 deque 和 list 的语义十分相似，按照这个逻辑应该也是一个可用的实现。

在多次调试之后发现，调用 erase 出现了问题。最后注意到了 deque 和 list 在 Iterator invalidation (迭代器非法化) 的行为上存在重要差异。对于 deque 来说，push_front 足以让所有的迭代器失效。换句话说，紧接着的 erase 函数是对一个无效迭代器进行了操作，自然变成了一个行为未定义的问题。在 GCC 的 C++ 库中产生了异常的值，在 MSVC 的 C++ 库实现下则直接导致了内存访问违规。

知道问题原因之后，修复就非常简单了。

         for(auto iter = container.begin(); iter != container.end(); iter++) {
             if(iter->first == key) {
                 value_t v = iter->second;
-                container.push_front(*iter);  // 放到最前
+                pair_t p = *iter;             // 拷贝内容
                 container.erase(iter);        // 删除
+                container.push_front(p);      // 放到最前
                 return v;
             }
         }
         return value_t{};  // 没找到
     }

     void put(key_t key, value_t value) {
         for(auto iter = container.begin(); iter != container.end(); iter++) {
             if(iter->first == key) {
                 iter->second = value;
-                container.push_front(*iter);  // 放到最前
+                pair_t p = *iter;             // 拷贝内容
                 container.erase(iter);        // 删除
+                container.push_front(p);      // 放到最前
                 return;
             }
         }

而 list 在头部增加元素并不会影响跑在中间的迭代器，因此不存在这个问题。另外考虑到删除元素的性能，最佳方案就是直接用 list。