C++详解stl迭代器 （vector迭代器失效问题）

C++剖析stl迭代器

• 迭代器
• • 是什么？：
  • 迭代器 和 指针
• 迭代器失效
• • 迭代器失效情况
  • 详解`vector`迭代器失效

迭代器

  Iterator（迭代器）模式又称游标（Cursor）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

 由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展Iterator。

是什么？：

定义：
🥦 迭代器是指向元素范围（如数组或容器）中的某个元素的任何对象，它能够使用一组运算符（至少具有自增（++） 和解引用 （*） 运算符）循环访问该范围的元素。

🍊 迭代器最明显的形式是指针：指针可以指向数组中的元素，并且可以使用增量运算符 （++） 循环访问这些元素。

但其他类型的迭代器也是可能的。

例如，每个容器类型（如list ）都有一个特定的迭代器类型，旨在循环访问其元素。

                  迭代器根据其实现的功能分为五类

     
迭代器的作用：

🥦 用于指向顺序容器和关联容器中的元素
🍊 通过迭代器可以读取它指向的元素
🍉 通过非const迭代器还可以修改其指向的元素

     
其实简单地讲就是可以让程序员🙉可以在使用元素过程中不用知道底层数据结构的实现，使访问更加的简单，方便。

     
demo:

#include 
#include 
using namespace std;

int main()
{
	vector<int> v{ 1, 2, 3, 4, 5, 6, 7 }; //C++ 11语法
	vector<int>::iterator my_it = v.begin;
	//auto my_it = v.begin();

	// 迭代器遍历输出
	while (my_it != v.end()){
		cout << *my_it << endl;
		++my_it;
	}
	return 0;
}

stl源码中vector迭代器的定义

 

迭代器 和 指针

🥦 迭代器所表现出的功能很像指针，但并不能和指针划等号； 迭代器并不是指针，而是类模板，表现的像指针。

  他只是模拟了指针的一些功能，重载了指针的一些 *** 作符，–>、++、–等。

迭代器封装了指针，是一个"可遍历STL( Standard Template Library)容器内全部或部分元素"的对象，本质是封装了原生指针 (T*)，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等 *** 作。

🍊迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

指针是迭代器的一种形式，迭代器和指针有类似的元素 *** 作功能
相同点：
🍒 都可以进行整数 *** 作的加减运算； 都可以同类型相减得到元素个数

区别：
迭代器：
🥑 迭代器不是指针是类模版，表现像指针。

迭代器是指针的抽象和泛化，它模拟了一些指针的功能， 通过重载指针的一些 *** 作符。

本质是封装了原生指针，相当于指针的一种升级。

🥑 迭代器返回的是对象引用而不是对象的值
🥑 指针能指向函数；而迭代器只能指向容器。

🥑 指针只能用于某些特定的容器；迭代器是指针的抽象和泛化。

     
 

     
     

迭代器失效

 
🥦 其实迭代器底层对应指针所指向的空间被销毁了，而使用非法的空间造成错误， 可能会导致程序崩溃的后果。

          		vs2013 中的迭代器失效

     

迭代器失效情况

     

用容器迭代器erase失效情形如下。

🥦 对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

🍊 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

（解决方式）

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

     
     
     
     

详解vector迭代器失效

以 vector 为例， 对于 vector 可能会导致迭代器失效的 *** 作有：

1. 会引起其底层空间改变的 *** 作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back…

与VS相同的代码在Linux中“正常执行”，没有出现崩溃。

(因为在 windows 中 VS是PJ版本STL，而在Linux g++是SGI版本STL)两种STL版本不同也导致迭代器失效的结果不同，VS较Linux中检查较严格，更容易直接报出错误， 而在Linux中在出现较严重的非法访问时也会出现Segmentation fault
（结果如下图）

解决方式：在以上 *** 作完成之后，如果想要继续通过迭代器 *** 作vector中的元素，只需给my_it重新赋值即可

int main()
{
	vector<int> v{ 1, 2, 3, 4, 5, 6, 7 }; //C++ 11语法
	vector<int>::iterator my_it = v.begin();
	
	//可能导致容量改变，导致原空间被回收
	//v.insert(v.begin(), 0);
    //v.resize(50, 0);
	//v.reserve(100);
	//v.assign(100, 8);
	v.push_back(8);
	while (my_it != v.end()){
		cout << *my_it << endl;
		++my_it;
	}
	return 0;
}

2. 任意位置元素的删除 *** 作–erase

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。

因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

int main()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a)/sizeof(int));
	// 使用find查找3所在位置的iterator
	auto pos = find(v.begin(), v.end(), 2);
	// 删除pos位置的数据，导致pos迭代器失效。


	v.erase(pos);
	cout << *pos << endl; // 此处会导致非法访问
	return 0;
}
_________________________________________________________________________

int main()
{
	vector<int> v{ 1, 2, 3, 4, 5, 6, 7 }; //C++ 11语法
	vector<int>::iterator my_it = v.begin();

	while (my_it != v.end()){
		my_it = v.erase(my_it);
		++my_it;
	}
	return 0;
}