erase 迭代器失效,stl 迭代器失效

　　以下资料是从网络作品中整理出来的。

　　STL中的容器按照存储方式可以分为两种，一种是以数组形式存储的容器(比如vector和Deque)；另一种是存储在不连续节点中的容器(如list、set、map)。使用erase方法删除元素时，有一些问题需要注意。

　　当使用list、set或map遍历来删除一些元素时，可以这样使用：

　　正确使用方法1

　　STD:List int List；

　　STD:list int:iterator it list；

　　for(it list=list . begin()；itList！=list . end()；)

　　{

　　if(WillDelete(*itList))

　　{

　　it list=list . erase(it list)；

　　}

　　其他

　　itList

　　}

　　或者

　　正确使用方法2

　　STD:List int List；

　　STD:list int:iterator it list；

　　for(it list=list . begin()；itList！=list . end()；)

　　{

　　if(WillDelete(*itList))

　　{

　　list . erase(it list)；

　　}

　　其他

　　itList

　　}

　　这里有两种错误的使用方法：

　　错误方法1

　　STD:List int List；

　　STD:list int:iterator it list；

　　for(it list=list . begin()；itList！=list . end()；itList)

　　{

　　if(WillDelete(*itList))

　　{

　　list . erase(it list)；

　　}

　　或者

　　错误方法2

　　STD:List int List；

　　STD:list int:iterator it list；

　　for(it list=list . begin()；itList！=list . end()；)

　　{

　　if(WillDelete(*itList))

　　{

　　it list=list . erase(it list)；

　　}

　　其他

　　itList

　　}

　　正确方法1:通过erase方法的返回值获取下一个元素的位置。

　　正确方法2:在调用erase方法之前，使用" "获取下一个元素的位置。

　　错误方法1:调用erase方法后，使用“”获取下一个元素的位置。由于这个元素的位置在调用erase方法后已经被删除，如果根据这个旧位置获取下一个位置，就会出现异常。

　　错误方法二：同上。

　　这里的“”运算符正好与我们通常的理解相反。erase( itList)是先获取下一个元素的位置，然后删除；Erase( itList)是删除后下一个元素的位置。

　　当使用vector和deque遍历被删除的元素时，也可以通过erase的返回值获得下一个元素的位置：

　　正确使用方法

　　STD:vector int Vec；

　　STD:vector int:iteratoritVec；

　　for(it vec=vec . begin()；itVec！=vec . end()；)

　　{

　　if(WillDelete(*itVec))

　　{

　　it vec=vec . erase(it vec)；

　　}

　　其他

　　itList

　　}

　　注意：vector和deque不能像上面“正确使用方法2”的方法那样遍历和删除。原因请参考有效STL第9条。摘录如下：

　　1.对于关联容器(如map、set、multimap、multiset)，删除当前迭代器只会使当前迭代器失效，只要当前迭代器在擦除时递增即可。这是因为map等容器是用红黑树实现的，插入或删除一个节点不会影响到其他节点。

　　for(ITER=cont . begin()；它！=cont . end()；)

　　{

　　(* ITER)-do something()；

　　if(shouldDelete(*iter))

　　cont . erase(ITER)；

　　其他

　　iter

　　}

　　因为iter传递了copy to erase方法，所以iter会指向下一个元素。

　　2.对于顺序容器(比如vector，deque)，删除当前迭代器会使后面所有元素的迭代器失效。这是因为vetor，deque使用连续分配的内存，删除一个元素会导致后面所有的元素向前移动一个位置。幸运的是，erase方法可以返回下一个有效的迭代器。

　　for(ITER=cont . begin()；iter！=cont . end()；)

　　{

　　(* it)-do something()；

　　if(shouldDelete(*iter))

　　ITER=cont . erase(ITER)；

　　其他

　　iter

　　}

　　3.对于list，它使用的是不连续分配的内存，它的erase方法也会返回下一个有效的迭代器，所以以上两种方法都可以使用。

　　迭代器失败：

　　(1)矢量

　　内部数据结构：数组。

　　对每个元素的随机访问需要恒定的时间。

　　在末尾添加或删除元素所需的时间与元素个数无关，而在中间或开头添加或删除元素所需的时间随元素个数线性变化。

　　元素可以动态增减，内存管理自动完成，但是程序员可以使用reserve()成员函数来管理内存。

　　vector的迭代器在内存重新分配时会失效(它所指向的元素在这次操作前后不再相同)。当超过capacity()-size()的元素被插入到vector中时，内存将被重新分配，所有迭代器都将失败；否则，指向当前元素之后任何元素的迭代器都将无效。当删除一个元素时，指向被删除元素后任何元素的迭代器都将失效。

　　(2)得缺

　　内部数据结构：数组。

　　对每个元素的随机访问需要恒定的时间。

　　开头和结尾添加元素所需时间与元素个数无关，中间添加或删除元素所需时间随元素个数线性变化。

　　可以动态添加或减少元素，自动完成内存管理，不提供内存管理的成员函数。

　　添加任何元素都会使deque的迭代器失效。删除deque中间的元素会使迭代器失效。当一个元素在deque的头部或尾部被删除时，只有指向该元素的迭代器是无效的。

　　(3)列表

　　内部数据结构：双向循环链表。

　　您不能随机访问元素。

　　它可以双向穿越。

　　在开始、结束和中间的任何地方添加或删除元素所需的时间是恒定的。

　　可以动态地添加或减少元素，并且自动完成内存管理。