对于 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;
    }
    
    int get(int 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 -1;  // 没找到
    }
    
    void put(int key, int 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 -1;  // 没找到
     }

     void put(int key, int 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。