C++中利用迭代器删除元素会发生什么？

青旅半醒 2022-06-12 01:28 323阅读 0赞

**C++中利用迭代器删除元素会发生什么？**

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

set<int> valset = { 1,2,3,4,5,6 };
    set<int>::iterator iter;
    for (iter = valset.begin(); iter != valset.end(); )
    {
         if (3 == *iter)
              valset.erase(iter++);
         else
              ++iter;
    }

因为传给erase的是iter的一个副本，iter++是下一个有效的迭代器。

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

vector<int> val = { 1,2,3,4,5,6 };
    vector<int>::iterator iter;
    for (iter = val.begin(); iter != val.end(); )
    {
         if (3 == *iter)
              iter = val.erase(iter);     //返回下一个有效的迭代器，无需+1
         else
              ++iter;
    }

**补充：**

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，因此上面两种正确的方法都可以使用。