<
迭代器失效
>

没有上一篇咯 下一篇

两个链表的第一个公共结点

迭代器失效的主要原因和几种情况

迭代器的定义

迭代器（iterator）是一个可以对其执行类似指针的操作（如：解除引用（operator*()）和递增（operator++()）的对象。迭代器完成的行为就像一个指针，但它是一个对象。

百度百科:
迭代器（iterator）是一种对象，它能够用来遍历标准模板库容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口，所谓迭代器是一种概念上的抽象：那些行为上像迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有机的统一起来。
迭代器提供一些基本操作符：*、++、==、!=、=。这些操作和C/C++“操作array元素”时的指针接口一致。不同之处在于，迭代器是个所谓的复杂的指针，具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此，每一种容器型都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同，型号却不同。这直接导出了泛型程序设计的概念：所有操作行为都使用相同接口，虽然它们的型别不同。

迭代器失效

这里有一个简单的vector迭代器失效的例子，移除数组中的奇数：

	int arry[100] = { 616, 34, 399, 165, 716, 45, 125, 8, 23, 13 };
	vector<int> vec(arry, arry + 9);
	vector<int>::iterator iter = vec.begin();
	for (; iter != vec.end(); iter++){
	 	if (*iter % 2 != 0)
	 	{
		  	vec.erase(iter);//迭代器失效               
		 }
	}
	for (int s = 0; s < vec.size(); s++){
	 	cout << vec[s] << endl;
	}

运行结果
报错了，我们下断点看一下。
运行结果 在遍历前两个数据 “616” 和 “34” 的时候并没有问题，在移除399之后的当次遍历，iter++了之后理应指向165进行下一次循环，就在这里程序报错。为什么？

根本原因是erase()使所有的iterator和reference无条件失效，而对一个失效的迭代器进行解引用或者是++操作都是一个未定义行为，所产生的任何后果都是理所应当、合情合理的。

在C++中是这样描述erase()的:
iterator erase(const_iterator first,const_iterator last);
Effects:Invalidates iterators and references at or after the point of the erase

在erase() “399” 的时候，当前的iter就失效了，对其++对编译器来说是错误的、未定义的行为。而对于vector,deque序列容器来说，erase()会使其后的所有迭代器失效，但是会让其后的所有迭代器前移，并返回下一个有效的迭代器。以此，似乎可以写出正确的移除迭代器的方法了：

	for (; iter != vec.end();){
	 	if (*iter % 2 != 0)
	 	{
		  	iter = vec.erase(iter);
		}
 		else
  		{
   			iter++;
  		}
	}

运行结果
没错，在erase()时，使用iter接住其返回的正确迭代器达成++的目的。

从存储方式分析vector迭代器的失效原理

首先vector在内存中是顺序存储的，并且vector在push_back()的时候，会申请一块新的存储空间，将原有的数据和新添加的数据拷贝进来，然后释放旧的存储空间，当出现这种情况的，一定会使vector的所有迭代器失效。
可以看出，上述的vector操作效率是非常低下的，因此在具体实现的时候，vector不可能每个元素都这么操作，为了提高效率，vector每次扩容时申请的存储空间会大一些，vector里使用capacity成员记录容器在必须分配新存储空间之前可以存储的元素总数，刚开始是0，然后是1，乘指数递增。不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

可以参见vector扩容原理。

一、vector的几种失效情况

  1. 在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）。
  2. 当删除元素时，指向被删除元素以后的任何元素的迭代器都将失效。
  3. 当把超过capacity()-size()个元素插入vector中时，内存会重新分配，所有的迭代器都将失效；否则，指向当前元素以后的任何元素的迭代器都将失效。

二、deque的失效情况

  1. 增加任何元素都将使deque的迭代器失效。
  2. 在deque的中间删除元素将使迭代器失效。
  3. 在deque的头或尾删除元素时，只有指向该元素的迭代器失效。

    关于deque的迭代器失效问题是相当有争议的，主要争议在于push-back()和push_front()：
    c++ primer中是这么写的：
    1.在deque容器首部或者尾部插入元素不会使得不论什么迭代器失效。
    2.在其首部或尾部删除元素则仅仅会使指向被删除元素的迭代器失效。
    C++11中描述有所区别：
    all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1] Erasure: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]
    Resizing: as per insert/erase [23.3.3.4/1]

插入会导致所有迭代器和引用都无效，除非插入的成员位于deque的末尾(前面或后面)(在这种情况下，所有迭代器都无效，但对元素的引用不受影响)[23.3.3.4/1]
删除：删除最后一个元素只使迭代器无效和对删除元素和过去结束迭代器的引用无效；
删除第一个元素只使迭代器无效和对删除元素的引用无效；
删除任何其他元素使所有迭代器和引用(包括过去-结束迭代器)无效[23.3.3.4/4]
调整大小：依据插入/删除[23.3.3.4/1]

注意加粗部分就是争议所在，在push头部和尾部的时候，迭代器究竟会失效吗？
在VS2013环境下的尝试结果如下：
运行结果 运行结果 不难看出，错误提示：deque iterators incompatible，但是指向原始头部的指针并未失效，因此个人支持C++11的原理。（若有新发现，请指正^_^）

三、list的失效情况

  1. 增加任何元素都不会使迭代器失效。
  2. 删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。

四、set,map的失效情况

  1. 如果迭代器所指向的元素被删除，则该迭代器失效。
  2. 其它任何增加、删除元素的操作都不会使迭代器失效。
  3. multiset,hash_set,hash_multiset,multimap,hash_map,hash_multimap都与set,map相同。

不同容器的迭代器有区别吗？

当然有,刚才提到：

  1. 对于vector，deque序列容器来说，erase()会使其后的所有迭代器失效，但是会让其后的所有迭代器前移，并返回下一个有效的迭代器。其他容器呢？
  2. 对于关联容器map，set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器。所以在erase()之前需要记下下一个迭代器。
  3. 而对于List来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，所以哪种使用方法都是可以的。

安全的使用方式

由于在插入(insert)或者删除(erase)操作调用迭代器时，有可能会导致迭代器失效，所以在使用插入、删除操作时，应当获取新的有效的迭代器以保证下一步操作的正确性和安全性：

iter = vec.insert(iter);  
iter = vec.erase(iter);

2019/7/25 星期四 17:41:02

Top
Foot