调用erase()后std::map::iterator出现问题

Question

调用erase()后std::map::iterator出现问题

20

// erasing from map
#include <iostream>
#include <map>
using namespace std;

int main ()
{
  map<char,int> mymap;
  map<char,int>::iterator it(mymap.begin());

  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;

  it=mymap.find('a');
  mymap.erase (it);                   // erasing by iterator

  // show content:
  for (; it != mymap.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;
  return 0;
}

为什么这个代码会产生如此输出？

a => 10
b => 20
c => 30
d => 40
e => 50
f => 60

为什么"a => 10"不管怎样都应被删除，但如果我在for循环中声明it = mymap.begin()，一切就完美了。为什么呢？

程序修改自：http://www.cplusplus.com/reference/stl/map/erase/

- 0x0

类似于：https://dev59.com/qXNA5IYBdhLWcg3wPbSe - karlphillip

5个回答

3

调用erase()会使迭代器失效。在这种情况下，迭代器指向内存中留下的残余值（但不要依赖于这种未定义的行为！）。在循环之前使用it=mymap.begin()重置迭代器以获得期望的结果。

http://codepad.org/zVFRtoV5

这个答案展示了如何在遍历std::map时删除元素：

for(map<T, S*>::iterator it = T2pS.begin(); it != T2pS.end(); T2pS.erase(it++)) {
    // wilhelmtell in the comments is right: no need to check for NULL. 
    // delete of a NULL pointer is a no-op.
    if(it->second != NULL) {
        delete it->second;
            it->second = NULL;
    }
}

- moinudin

那么在for循环内部使用迭代器并根据某些条件删除元素是不可能的吗？换句话说，如果我有一个包含1000个元素的映射，并且我想要删除满足某个用户定义条件的元素，那么每次我删除一个元素时，我都应该中断循环并重新开始吗？ - 0x0

2

很遗憾，使用 std::map，答案是肯定的。删除一个元素会重新构建树来保持平衡，因此您甚至不能像其他 std 容器(如 std::list)那样依赖于删除元素右侧的所有元素仍然在原始位置上。@Sunil - moinudin

2

@Sunil 看看sth的帖子；如果你在调用erase时后置递增迭代器，你的迭代器仍然有效。只要确保在for循环中，你不会意外地将迭代器增加两次。@marcog 不完全正确。虽然节点可能会重新平衡，但它们在内存中的实际地址并不会改变；至少对于红黑树来说，只有它们的左/右/父指针会改变。sth的答案是可行的。 - Dawson

@工具箱：将其增加两次是问题，你不觉得吗？因为这样做时，在for循环中下一次检查条件时会再次增加迭代器。这意味着每次删除一个项目时都会跳过其旁边的项目。 - 0x0

2

@Sunil 请参考这个答案来正确地遍历std::map并同时删除元素。 - moinudin

@Sunil 你必须更改循环才能使其工作。将其变为while循环，其中你可以选择1）erase（it ++）或2）++ it。@marcog 我运行了你的代码并得到了相同的输出 - 但是有什么问题吗？你删除了“b”，然后将迭代器重置为begin（），并获得了预期的结果。至于那个线程，it ++通过复制它来避免该问题，增加原始值，然后将副本传递给erase。这避免了失效。 - Dawson

1

it在mymap.erase(it)之后不再有效。这意味着它可以随意操作。

- Oswald

1

这与map的实现方式有关。假设它是某种树形结构，例如：

class map_node {
    char key;
    int  value;
    map_node* next;
    ...
};

当你使用erase()函数删除迭代器时，你会将节点从树中移除并释放其空间。但在该内存位置被覆盖之前，节点的内容仍然存在于内存中。这就是为什么你不仅可以获取值，还可以获取树中的下一个元素。因此，你得到的结果完全是预期的。

- chrisaycock

0

"

"it"仍然指向相同的位置，擦除操作不会自动更新迭代器，您需要通过重置迭代器来完成。实际上，“it”指向已从向量中删除但仍包含旧数据的旧位置。

"

- Akhil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sth · Accepted Answer

从 map 中删除一个元素会使指向该元素的迭代器失效（在该元素被删除之后）。您不应该重复使用该迭代器。

C++11 以后的 erase() 返回一个指向下一个元素的新迭代器，可以用于继续迭代：

it = mymap.begin();
while (it != mymap.end()) {
   if (something)
      it = mymap.erase(it);
   else
      it++;
}

在C++11之前，您需要在删除元素之前手动将迭代器推进到下一个元素，例如：

mymap.erase(it++);

这段代码之所以能够正常工作，是因为it++的后置自增副作用会在erase()删除元素之前发生。虽然这可能不是显而易见的，但应该优先选择上面的C++11变体。