c++ - 迭代器作为映射值出错

Question

很长时间没有使用 C++，非常感谢!

这是一个简单的 LRU 缓存演示，我打算使用 std::list<std::pair<int, int>>::iterator跟踪 std::list 中的数据项, 但似乎出了点问题所以 -fsanitizer告诉我heap-use-after-free警告。

class SimpleLRU {
 public:
  SimpleLRU(int cap) : cap_(cap) {}

  int get(int key) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
      int val = it->second->second;  <--- line 13
      list_.erase(it->second);
      list_.emplace_front(key, val);
      cache_.emplace(key, list_.begin());
      return val;
    }
    return -1;
  }

  void put(int key, int value) {
    auto it = cache_.find(key);
    if (it != cache_.end()) {
      list_.erase(it->second);
    } else if (cache_.size() == cap_) {
      cache_.erase(list_.back().first);
      list_.pop_back();
    }
    list_.emplace_front(key, value);
    cache_.emplace(key, list_.begin());
  }

 private:
  int cap_;
  std::list<std::pair<int, int>> list_;
  std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_;
};

error

==1903037==ERROR: AddressSanitizer: heap-use-after-free on address 0x60300000eff4 at pc 0x56488c0f9ff2 bp 0x7ffebf9a0ba0 sp 0x7ffebf9a0b98
READ of size 4 at 0x60300000eff4 thread T0
    #0 0x56488c0f9ff1 in SimpleLRU::get(int) test.cc:13

Answer 1

在SimpleLRU::get中，由于key已经存在于cache_中，调用cache_.emplace(key, list_ .begin()) 是一个空操作 - 它不会用新值替换现有值。结果，cache_ 最终持有无效的迭代器。做到这一点

it->second = list_.begin();

---

SimpleLRU::put 中有类似的问题，只是您并不总是手头有指向现有 map 元素的迭代器。处理这个问题留给读者作为练习。