迭代器作为映射值出错

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 中的类似问题，只是您并不总是手头有指向现有地图元素的迭代器。处理此问题留作 reader.

的练习。

迭代器作为映射值出错

Iterator as map value goes wrong

c++

address-sanitizer