STL容器迭代器失效分析

连续内存序列容器(vector, string, deque)

对于连续内存序列STL容器,例如vector,string,deque,删除当前iterator会使得后面所有的iterator都失效,因为它们使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置,保证元素的连续性。当上述容器的erase方法可以返回下一个有效的iterator,即erase方法的返回的iterator指向紧接在被删除元素之后的元素的有效迭代器,因此,可以根据这个返回值继续访问后面的元素。

连续内存序列容器删除特定元素示例:

vector<int> vc;
for(vector<int>::iterator it != vc.begin(); it != vc.end(); )
{
    if(need_delete())
       it = vc.erase(it);
    else
       ++it;
}

关联容器(set, multiset, map, multimap)

对于关联容器,删除当前iterator指向的元素,仅仅使得当前iterator失效,只要在erase时,递增当前iterator,获得下一个元素iterator即可。只是因为map之类的关联容器,使用红黑树实现,插入,删除一个结点不会对其他结点造成影响。关联容器的erase方法不能返回下一个有效迭代器(C++98),被删除的iterator失效,所有删除当前元素之前必须确保可以得到下一个iterator,可以使用”后置递增迭代器“技术。

关联容器删除特定元素示例:

map<int,int> m;
for(map<int,int>::iterator it = m.begin(); it!= m.end(); )
{
    if(need_delete())
       m.erase(it++);
    else
       ++it; 
}

因为传递给erase方法的it参数是iterator的一个副本,it++会指向下一个元素,所以erase得到了当前迭代器,在erase内部工作之前it已经++,指向下一个迭代器,正好满足需要。

非连续内存序列容器(list)

对于list来说,它使用了不连续的内存,并且它的erase方法也会返回下一个有效的iterator,因此上述两种删除特定元素的方法都可以使用。

原文地址:https://www.cnblogs.com/zhouLee/p/4735553.html