在遍历中使用 iterator/reverse_iterator 进行 Erase 的用法

本文转载自 罗朝晖的博客 http://blog.csdn.net/kesalin/article/details/24265303

众所周知，在使用迭代器遍历 STL 容器时，需要特别留意是否在循环中修改了迭代器而导致迭代器失效的情形。下面我来总结一下在对各种容器进行正向和反向遍历过程中删除元素时，正确更新迭代器的用法。本文源码：https://code.csdn.net/snippets/173595

首先，要明白使用正向迭代器（iterator）进行反向遍历是错误的用法，要不干嘛要有反向迭代器呢（reverse_iterator）。其次，根据容器的特性，遍历删除操作的用法可以分为两组，第一组是 list 和 vector，第二组是 map 和 set。

接下来，看看具体怎么个用法。

第一种情形：正向遍历删除元素

对 list 和 vector 来说，它们的 erase 函数会返回下一个迭代器，因此在遍历时，只需要 it = c.erase(it); 即可。

对 map 和 set 来说，它们的 erase 函数返回的 void，而在进行 erase 之后，当前迭代器会失效，无法再用于获取下一个迭代器。因此需要 erase 之前就获取指向下一个元素的迭代器。如： 

[cpp]  view plain copy print ?

1. tmpIt = it;  
2. ++it;  
3. c.erase(tmpIt);  

[cpp]  view plain copy print ?

1. c.erase(it++);  

list 正向遍历删除元素示例（vector 用法相同）：

[cpp]  view plain copy print ?

1. list<int>::iterator it;  
2. for (it = l.begin(); it != l.end();)  
3. {  
4.     if (0 == (*it) % 2) {  
5.         it = l.erase(it);  
6.     }  
7.     else {  
8.         ++it;  
9.     }  
10. }  

[cpp]  view plain copy print ?

1. map<int, int>::iterator mit;  
2. for (mit = m.begin(); mit != m.end();)  
3. {  
4.     if (0 == mit->first % 2) {  
5.         m.erase(mit++);  
6.     }  
7.     else {  
8.         ++mit;  
9.     }  
10. }  

由于所有的 erase 函数都只接受正向迭代器 iterator，所以在进行反向遍历删除元素时，首先需要将 reverse_iterator 转换为 iterator，然后再考虑更新迭代器的问题。

先来分析如何将 reverse_iterator 转换为 iterator。如上图所示，我们想要删除元素3，而 ri.base() 所得到的正向迭代器 i 指向的其实 4 了，因而为了正确地删除元素 3，需要将ri往前（反向的）挪一个位置。也就是说，这一步的删除用法应为：

[cpp]  view plain copy print ?

1. c.erase((++rit).base());  

[cpp]  view plain copy print ?

1. c.erase(--(rit.base();  

对 map/set 来说，因为在进行删除操作 l.erase((++rit).base()) 时，迭代器已经更新过了，真是一举两得啊。从这里也可以看出，使用这种先递增后 base() 的转换删除法，代码更清晰。

至此，理论分析完毕，下面我们来看具体的实例。

list 反向遍历删除元素示例（vector 用法相同）：

[cpp]  view plain copy print ?

1. // erase with reverse_iterator  
2. list<int>::reverse_iterator rit;  
3. for (rit = l.rbegin(); rit != l.rend();)  
4. {  
5.     if (0 == (*rit) % 2) {  
6.         rit = list<int>::reverse_iterator(l.erase((++rit).base()));  
7.     }  
8.     else {  
9.         ++rit;  
10.     }  
11. }  

map 反向遍历删除元素示例（set 用法相同）：

[cpp]  view plain copy print ?

1. // erase with reverse_iterator  
2. map<int, int>::reverse_iterator rit;  
3. for (rit = m.rbegin(); rit != m.rend();)  
4. {  
5.     if (0 == rit->first % 2) {  
6.         m.erase((++rit).base());  
7.     }  
8.     else {  
9.         ++rit;  
10.     }  
11. }