deque 和列表之间的差异行为

问：

我可以使用列表和（哈希）映射成功实现 LRU 缓存。我想知道为什么当我使用 deque 而不是列表时会出现错误的行为。让我简要解释一下我的方法。

1. 使用地图中的键查找值。映射返回保存其值的列表或 deque 的迭代器。
2. 迭代器应更新 2.1. 从映射和列表或 deque 中删除现有节点。 2.2. 将一个新节点推到列表的前面，映射还会将新节点的键和迭代器作为值保存。

所以我的问题是：为什么当我使用 deque 而不是列表时，我得到了错误的结果？我猜 deque 内部有一个块列表，它会造成问题。但是，我不确定根本原因。

这是一个可重现的代码。预期结果是“9 29 9”，使用列表时我可以看到正确答案。但是使用deque时返回错误的结果“9 29 29”。

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

using pii = pair<int, int>;
#if 1
using List = deque<pii>;
#else
using List = list<pii>;
#endif
using ListIter = List::iterator;
using Map = unordered_map<int, ListIter>;

class LRUCache {
  size_t capacity;
  List lru_list;
  Map map;

public:
  LRUCache(size_t capacity) : capacity(capacity) {}

  void put(int key, int value) {
    Map::iterator miter = map.find(key);
    promote(key, value, miter != map.end() ? miter->second
      : (lru_list.size() == capacity) ? --lru_list.end() : lru_list.end());
  }
  int get(int key) {
    Map::iterator miter = map.find(key);
    if (miter == map.end()) return -1;
    pii v = *(miter->second);
    promote(v.first, v.second, miter->second);
    return v.second;
  }

  void promote(int key, int value, ListIter iter) {
    if (iter != lru_list.end()) lru_list.erase(iter);
    lru_list.push_front({key, value});
    map[key] = lru_list.begin();
  }
};

void run(LRUCache& cache, vvi& vv) {
  for (auto& e : vv) {
    if (e.size() > 1) cache.put(e[0], e[1]);
    else cout << cache.get(e[0]) << endl;
  }
}

void test1() {
  LRUCache cache(10);
  vvi vv {
    {10,27}, {8,10}, {6,29}, {1,9},
    {1}, {6}, {1}
  };
  run(cache, vv);
}

int main() {
  test1();

  return 0;
}