C++中利用迭代器删除元素

2019-07-31 425 words One minute

Contents

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

关联容器

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

传给erase的只是it的一个副本，it++才是下一个有效的迭代器

序列容器

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<int> val = {1,2,3,4,5};
vector<int>::iterator it;
for(it = val.begin();it != val.end();)
{
    if(3 == *it)
    {
        it = val.erase(it);
    }
    else
    {
        ++it;
    }
}