STL vector map遍历失效，顺序容器和关联容器遍历时的erase()注意事项2 遍历3 删除为何vector和map删除元素是操作不同总结

104 阅读 0 评论 69 点赞

我是靠谱客的博主现代万宝路，最近开发中收集的这篇文章主要介绍STL vector map遍历失效，顺序容器和关联容器遍历时的erase()注意事项2 遍历3 删除为何vector和map删除元素是操作不同总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1 区别

关联容器(Associative Container)：通过键(key)存储和读取元素的（vector,list,deque,stack,queue,heap,priority_queue,slist.）

顺序容器(Sequential Container)：通过元素在容器中的位置顺序存储和访问元素。（set，map，multiset,multimap底层机制都是以RB-tree）

2 遍历

用最熟悉的vector和map举例，只用到迭代器遍历

for(vector<int>::iterator it=v.begin();it!=v.end();++it)
{
cout<<*it<<endl;
}

for(map<int,int>::iterator it=m.begin();it!=v.end();++it)
{
cout << it->first << " : " << it->second << endl;
}

3 删除

for(map<int,int>::iterator it=m.begin();it!=v.end();)
{
cout << it->first << " : " << it->second << endl;
if(it->second %2 == 0)//偶数
{
m.erase(it++);//it指向下一个地址
}
else
{
++it;
}
}

for(vector<int>::iterator it=v.begin();it!=v.end();++it)
{
if(*it == 1)
{
it = v.erase(it);//erase返回下一个元素的地址
}
else
{
++it;
}
}

为何vector和map删除元素是操作不同

vector是一个顺序容器，在内存中是一块连续的内存，当删除一个元素后，内存中的数据会发生移动，以保证数据的紧凑。所以删除一个数据后，其他数据的地址发生了变化，之前获取的迭代器根据原有的信息就访问不到正确的数据。

对于关联容器(如map, set,multimap,multiset)，这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

总结

总结：迭代器失效分三种情况考虑，也是非三种数据结构考虑，分别为数组型，链表型，树型数据结构。

数组型数据结构：该数据结构的元素是分配在连续的内存中，insert和erase操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(*iter)(或erase(iter))，然后在iter++，是没有意义的。解决方法：erase(iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);

链表型数据结构：对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(iter)会返回下一个有效迭代器的值，或者erase(iter++).

树形数据结构：使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

————————————————
参考链接 https://blog.csdn.net/lujiandong1/article/details/49872763