STL 使用 erase 删除元素时 iterator 失效

STL中的容器按存储方式分为两类：一类是序列容器（如：vector，deque），另一类是关联容器（如：list，map，set）。

在使用erase方法删除元素时，有几点需要注意：

1） 对于关联容器（如map， set，multimap，multiset），删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。

2）对于序列式容器（如vector，deque），删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor，deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。还好erase方法可以返回下一个有效的iterator。

3）对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

错误的使用方法：

[cpp] view plain copy

print?

1. std::map<int, string> mapIntStr;  
2. std::map<int, string>::iterator iter = mapIntStr.begin();  
3. for ( ; iter != mapIntStr.end(); iter++ )  
4. {  
5.     if ( iter->second == "test" )  
6.     {  
7.         mapIntStr.erase( iter );  
8.     }  
9. }  

正确的使用方法（一）：

[cpp] view plain copy

print?

1. std::map<int, string> mapIntStr;  
2. std::map<int, string>::iterator iter = mapIntStr.begin();  
3. for ( ; iter != mapIntStr.end(); )  
4. {  
5.     if ( iter->second == "test" )  
6.     {  
7.         mapIntStr.erase( iter++ );  
8.     }  
9.     else  
10.     {  
11.         iter++;// Use Pre Increment for efficiency.   
12.     }  
13. }  

因为iter传给erase方法的是一个副本，iter++会指向下一个元素。

正确的使用方法（二）：

[cpp] view plain copy

print?

1. std::map<int, string> mapIntStr;  
2. std::map<int, string>::iterator iter = mapIntStr.begin();   
3. for ( iter; iter != mapIntStr.end(); )   
4. {  
5.     if ( iter->second == "test" )   
6.     {  
7.         iter = mapIntStr.erase( iter );  
8.     }  
9.     else  
10.     {  
11.         ++iter; // Use Pre Increment for efficiency.   
12.     }  
13. }