STL 的 erase( ) 陷阱-迭代器失效总结

STL中的容器按存储方式分为两类,一类是按以数组形式存储的容器(如:vector 、deque);另一类是以不连续的节点形式存储的容器(如:list、set、map)。在使用erase方法来删除元素时,需要注意一些问题。

1.list,set,map容器

在使用 list、set 或 map遍历删除某些元素时可以这样使用:

1.1 正确写法 1

std::list<int> list;
std::list<int>::iterator it_list;
for (it_list = list.begin(); it_list != list.end();)
{
if (willDelete(*it_list))
{
it_list = list.erase(it_list);
}
else
{
++it_list;
}
}

Note: 以上方法仅适用于standard sequence container, 因为对于standard associative container, erase()的返回类型为void. (查阅Effective STL Item 9)以下为原文:

This works wonderfully, but only for the standard sequence containers. Due to reasoning one might question, erase()'s return type for the standard associative containers is void. For those containers, you have to use the postincrement-the-iterator-you-pass-to-erase technique.

1.2 正确写法2 查阅原版Effctive STL Item 9, 证实, 下面这种写法不能用于标准序列容器, 而适用于标准关联容器, 而List也可以使用这种方法.

std::list<int> list;
std::list<int>::iterator it_list;
for (it_list = list.begin(); it_list != list.end();)
{
if (willDelete(*it_list))
{
list.erase(it_list++); // 必须使用后缀自增, 不能使用前缀自增
}
else
{
++it_list;
}
}
```</int></int>

**1.3 错误写法 1**

std::list< int> List; std::list< int>::iterator itList; for( itList = List.begin(); itList != List.end(); itList++) { if( WillDelete( *itList) ) { List.erase( itList); } }

**1.4 错误写法 2**

std::list< int> List; std::list< int>::iterator itList; for( itList = List.begin(); itList != List.end(); ) { if( WillDelete( *itList) ) { itList = List.erase( ++itList); } else itList++; }

**1.5 分析**

正确方法1: 通过erase()方法的返回值来获取下一个元素的位置;
正确方法2: 在调用erase()方法之前先使用"++" 来获取下一个元素的位置;
错误使用方法1: 在调用erase()方法之后使用"++" 来获取下一个元素的位置, 由于在调用erase()方法之后, 该元素的位置已经被删除, 如果再根据这个旧的位置来获取下一个位置, 则会出现异常;
错误使用方法2: 同上

####**2. vector,deque 容器**
在使用 vector、deque遍历删除元素时,也可以通过erase的返回值来获取下一个元素的位置:

**2.1 正确写法:**

std::vector vec; std::vector::iterator it_vec; for (it_vec = vec.begin(); it_vec != vec.end();) { if (willDelete(*it_vec)) { it_vec = vec.erase(it_vec); } else { ++it_vec; } } ```

2.2 注意

vector, deque 不能像上面的"正确方法2" 的办法来遍历删除. 原因请参考Effective STL条款9。摘录到下面: 1) 对于关联容器(如map, set, multimap, multiset),删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。

for (iter = cont.begin(); it != cont.end();)
{
(*iter)-&gt;doSomething();
if (shouldDelete(*iter))
cont.erase(iter++);
else
++iter;
}

因为iter传给erase方法的是一个副本,iter++会指向下一个元素。

  1. 对于序列式容器(如vector, deque),删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor, deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。还好erase()方法可以返回下一个有效的iterator。

    for (iter = cont.begin(); iter != cont.end();) { (*it)->doSomething(); if (shouldDelete(*iter)) iter = cont.erase(iter); else ++iter; }

3)对于list来说,它使用了不连续分配的内存,并且它的erase()方法也会返回下一个有效的iterator,因此上面两种方法都可以使用。

3. 其他

set 键和值相等。 键唯一。 元素默认按升序排列。 如果迭代器所指向的元素被删除,则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效

map 键唯一。 元素默认按键的升序排列。 如果迭代器所指向的元素被删除,则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。

作成参考地址

Licensed under CC BY-NC-SA 4.0
Built with Hugo
主题 StackJimmy 设计