在C++ STL map中遍历时擦除元素导致运行时错误

Question

以下这段 C++ 代码会导致运行时错误，但如果移除掉 mymap.erase(v) 操作它就能够正常工作：

map<int,int> mymap = {{1,0},{2,1},{9,2},{10,3},{11,4}};
for(auto it=mymap.rbegin();it!=mymap.rend();){
    int v=it->first;
    ++it;
    mymap.erase(v);
}

演示

在删除值 v 之前，迭代器 it 被改变了，所以我认为迭代器 it 应该没有受到影响。

- Pratap Singh

---

对我来说可以运行，参见这里，你能提供一个最小可重现示例吗？ - Thomas

@user4581301 你对 mymap.rend() 进行了解引用操作。 - Paul Sanders

未来请不要将演示作为评论添加，而是直接编辑帖子以包含它。我这次已经这样做了。 - cigien

@Paul，那可能会发生，但程序没有执行到那一步。不过可能是时间旅行 UB（未定义行为）。没有打印语句的情况下也会出现同样的错误：https://ideone.com/o2FLkR - user4581301

我认为问题出在反向迭代器上，当使用begin/end而不是rbegin/rend时，它可以正常工作。 - Greg

Answer 1

当你调用erase(v)时，你会使下一个reverse_iterator（从++it开始）使用的基础iterator无效。因此，你需要从被删除的值之前的基础iterator创建一个新的reverse_iterator。

另外，与其删除reverse_iterator所引用的值，不如直接删除基础iterator，因为您已经知道要删除哪个元素了。没有必要让map再去查找该值。

这对我有用：

map<int,int> mymap = {{1,0},{2,1},{9,2},{10,3},{11,4}};
for(auto it = mymap.rbegin(); it != mymap.rend(); ){
    auto v = --(it.base());
    v = mymap.erase(v);
    it = map<int,int>::reverse_iterator(v);
}

演示

另一方面，这个循环本质上只是从mymap中 erase() 删除所有元素，所以更好的选择是使用mymap.clear()。

- Remy Lebeau

Answer 2

确实，std::map::erase:

被删除元素的引用和迭代器将失效，而其他引用和迭代器不受影响。

但是，对于std::reverse_iterator

对于由迭代器 i 构造的反向迭代器 r，关系式 &*r == &*(i-1) 总是成立的（只要 r 可进行解引用）；因此，构造一个从“尾后”迭代器构造出的反向迭代器会解引用到序列的最后一个元素。

也许你可以看一下 cppreference 页面上的图片以更清楚地理解。

关键部分是“反向迭代器存储了一个指向它所实际引用的下一个元素的迭代器”。

由此，你的代码稍作修改：

auto& element = *it;       // fails in the next iteration, because...
int v = element.first;
++it;                      // now it stores an iterator to element
mymap.erase(v);            // iterators to element are invalidated 

你正在删除下一次迭代中由it使用的元素。

- 463035818_is_not_a_number

---

“there is literally no difference to going forwards” - 从技术上讲，这个循环只是从map中删除所有元素，因此更好的选择是使用mymap.clear()。 - Remy Lebeau

@RemyLebeau 我其实没有意识到这点 :) - 463035818_is_not_a_number

@RemyLebeau 上下文非常复杂，我只是发布了我的具体问题。我不得不按相反的顺序删除一些元素。 - Pratap Singh

@PratapSingh 当你在迭代时需要擦除元素时，erase-remove idiom 通常是你最好的朋友。 - user4581301

@PratapSingh 这个答案只是解释了问题，修改是为了更小的范围演示它。但是没有提供修复方法，这就是为什么你的代码仍然有运行时错误的原因。 - Remy Lebeau