C++多图迭代器失效

Question

我想弄清楚如何std::multimap迭代器的工作，因此我创建了一个简单的例子，显示我的问题的实质。如果取消注释情况1，我希望迭代器指向第一个具有键1的元素，但实际上它会打印与键0相关的所有值（如没有被擦除），并且有时会崩溃，可能是因为迭代器无效。但是，如果取消注释情况2，则键1的所有值都将被正确删除。

是否有任何方法可以在擦除后知道multimap的下一个有效迭代器？ （例如std::vector.erase(...)回报之一）

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

问题

的原因。当你在一个元素调用m.erase(0)在您例如，it点与关键0 - 所以it无效。 m.erase(1)的作品，因为当它第一次被调用时，it没有指向具有密钥1的元素，因此它不受影响。在以后的迭代中，没有保留关键字1的元素，所以不会删除任何元素，也不会影响迭代器。

解决方案

multimap没有一个erase - 方法返回下一个有效的迭代器。一种替代方法是在删除后调用it = m.upper_bound(deleted_key);。这是对数，但是，对于您的方案而言可能太慢（erase(x)和upper_bound会是两次对数运算）。

假设你想删除你的迭代器当前指向键，你可以做这样的事情（否则，erase是好的，当然，未测试）：

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

它使用一个线性操作，其余的都是不变的时间。如果你的地图非常大，并且你只有少数项目的密钥相同，这可能会更快。但是，如果你有同键许多项目，寻求区间的结束，可能是使用upper_bound（O(log n)，而不是O(n)搜索间隔结束时）做得更好。

Answer 2

先回答

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

呜呜....

第二个答案，再：编辑问题

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

要特别小心当你在迭代它时改变一个容器（任何容器），就像你一样可能会使您依赖的迭代器失效。

所谓“基于节点的容器”（list，set，map ...）是最强大的容器WRT迭代器失效：他们只迭代器失效到删除的元素（有没有办法让这些迭代器不无效）。

在这种情况下，您应该检查您即将删除的元素实际上不是*it。

我不太清楚你正在尝试怎样处理你的循环。

Answer 3

当你擦除迭代器变得无效。而不是记住下一个元素，然后删除：

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

从看你的代码，我认为你++是造成问题的原因。您正在将其分配给可能已被删除的地方。在if语句和测试之后将其移动到最后。像这样：

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

（编辑）

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

除了it迭代器失效由于m.erase取决于multimap内容（已经覆盖在另一个答案）可能会始终存在取消引用问题m.end()迭代器在您每次运行程序时执行if((*it).second == 3)循环的for循环的最后一次循环中。

我建议运行和调试调试版本。我几乎可以肯定，每个理智的标准库实现应该包含断言来检测end()解引用。

Answer 6

上面已经有一些人已经回答了你是一个玩火。

另外，我想你忘记了，多重映射是有序的地图，让您从最小的键从最大的迭代。因此，在第一种情况下，您在打印其中的一些文件后将其移除，但在第二种情况下，您在去之前将其移除。