STL容器的迭代器失效问题

1 引言

常见的STL容器都能使用迭代器访问容器内元素,迭代器相同于一个指向容器内元素的指针,可以通过移动迭代器实现遍历容器。
但是在使用迭代器时需要考虑STL容器的失效问题;迭代器失效主要出现在对容器进行了增删操作之后,迭代器不再指向原本的元素。
这时如果再通过迭代器访问容器就有可能出现异常。

2 map容器

内部数据结构 :红黑树
插入操作 :插入操作会申请新的节点空间,然后加入都红黑树中,原来的迭代器指向的内存空间都未改变,故不会出现迭代器失效。
删除操作 :删除操作只会引起被删除节点的迭代器失效。

3 vector容器

内部数据结构 :数组(一段连续内存空间)
插入操作 :由于vector使用的是一段有长度限制的连续空间,插入( push_back / insert )操作在vector中加入新的元素时需要分情况考虑。

  • 当vector中元素总数仍不大于capacity,这时插入位置后的元素都被依次移动到下一个位置,所以插入位置之后的迭代器都会失效。
  • 当vector中元素总数大于capacity,这个时候会重新开辟更大的内存空间,将原来的vector中的内容复制到新的vector中,回收原先vector的内存空间。由于新的vector的地址已完全改变,所以原先的所有迭代器都会失效。

删除操作 :删除( pop_back / erase )操作在vector中删除元素,删除位置后的元素都被依次复制到前一个位置,所以删除位置之后的迭代器都会失效。
示例代码:

4 list容器

内部数据结构 :双向环状链表
插入操作 :插入操作会申请新的节点空间,然后加入到链表中,原来的迭代器指向的内存空间都未改变,故不会出现迭代器失效。
删除操作 :删除操作只会引起被删除节点的迭代器失效。

5 小结

在操作STL容器时,对容器增删( erase / insert )之后应该注意接收返回值,这样可以有效避免迭代器失效的产生。
对容器进行遍历删除操作时,另一种语法技巧是在 erase 接口中对迭代器进行后自增(it++),这种写法也能够保证遍历正常进行。理解这种写法需要参考运算符重载的相关知识,后自增操作会产生一个临时变量用于函数返回。

Comments

Comments powered by Disqus