STL迭代器的理解

迭代器简介绍

迭代器就像是一个”指针”，指向容器（比如vector、list）中的某个元素。通过迭代器，我们不仅可以访问和修改容器中的元素，还能在容器中自由移动（前进或后退）。
简而言之，迭代器充当着容器与算法之间的纽带，让你无需了解容器内部实现细节，就能方便地遍历和操作容器元素。
迭代器可以透明地访问容器内部的元素的值。
STL中提供的一些迭代器：

• const_iterator:常量的正向迭代器，只能读，不能通过该迭代器修改值
• iterator:普通的正向迭代器
• const_reverse_iterator:常量的反向迭代器，只能读，不能写
• reverse_iterator:普通的反向迭代器

以下是迭代器使用的样例代码：

vector <int> vec;
for (int i = 0; i < 20; i++)
{
	vec.push_back(rand() % 100 + 1);
}

//普通的正向迭代器
vector<int>::iterator it1= vec.begin();
for (; it1 != vec.end(); ++it1)
{
	cout << *it1 << " ";
	if (*it1 % 2 == 0)
	{
		*it1 =0;
	}
	
}
cout << endl;
//const_iterator是iterator的基类
vector<int>::const_iterator it2 = vec.begin();
for (; it2 != vec.end(); ++it2)
{
	cout << *it2 << " ";
}
cout << endl;

vector<int>::reverse_iterator it3 = vec.rbegin();
for (;it3!=vec.rend();++it3)
{ 
	cout << *it3 << " ";
	if (*it3 == 0)
	{
		*it3 = 1;
	}
}
cout << endl;
//const_reverse_iterator也是reverse_iterator的基类
vector<int>::const_reverse_iterator it4 = vec.rbegin();
for (; it4 != vec.rend(); ++it4)
{
	cout << *it4 << " ";
}

自定义实现迭代器

迭代器一般嵌套实现在容器内部，在上一篇实现容器配置器中我们实现了自定义的vector,本节我们继续在此基础上探索迭代器的实现。

//迭代器一般实现在容器的嵌套类型
class iterator
{
public:
	//迭代器的四要素
	//1,构造函数
	iterator(T* p=nullptr) :_p(p) {}
	//2.!=运算符重载
	bool operator!= (const iterator& it) const
	{
		return _p != it._p;
	}
	//3.前置运算符重载
	//前置++不会产生临时量，效率相对来说更高
	void operator++()
	{
		++_p;
	}
	//4.解引用方法重载
	//提供解引用的两个版本，普通方法和常方法
	T& operator*() { return *_p; }
	const T& operator*()const { return *_p; };
private:
	T* _p;//根据容器的变量定义
};
//返回容器底层首元素的迭代器表示
iterator begin() { return iterator(_first); }
//返回容器末尾元素的迭代器表示
iterator end() { return iterator(_last); }

将上述的iterator添加到自定义的vector内部后 ，就可以通过迭代器遍历自定义的vector内部元素了。

int main()
{
	vector <int> vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	//[]（中括号运算符重载）方式遍历，针对连续内存使用
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	//迭代器方式遍历
	vector<int>::iterator it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	for (int val : vec)//其底层就是通过容器的迭代器来实现遍历的
	{
		cout << val << " ";
	}
	cout << endl;
}

迭代器失效

迭代器为什么会失效？

• 当容器调用erase方法后，当前位置到容器末尾的所有迭代器全部失效了
• 当调用insert方法后，分为两种情况
  • 如果没有扩容操作，当前插入点到末尾的所有迭代器全部失效
  • 如果有扩容操作，容器全部失效

迭代器失效部分的代码比较复杂，我这里就使用stl中的vector进行记录

插入操作导致的迭代器失效：

vector<int> vec;
vec.reserve(10); //预留10个int元素大小
for (int i = 1; i <= 10; i++)
{
	vec.push_back(i);
}
for (auto it = vec.begin(); it != vec.end(); ++it)
{
	if (*it % 5 == 0)
	{
		vec.insert(it, *it - 1);//程序在这执行了一次插入操作后，迭代器就已经失效了
	}
}

执行这里代码是异常退出的；

删除操作导致的迭代器失效：

vector<int> vec;
vec.reserve(10); //预留10个int元素大小
for (int i = 1; i <= 10; i++)
{
	vec.push_back(i);
}
for (auto it = vec.begin(); it != vec.end(); ++it)
{
	if (*it % 2 == 0)
	{	
		//第一次调用erase以后，迭代器it就失效了
		vec.erase(it);
	}
}

解决迭代器失效问题的方法
当容器（如vector、list、map等）在进行插入或删除操作时，会导致迭代器失效。那如何解决上述提到的迭代器失效问题呢？
其实erase函数和insert函数返回了对应的一个迭代器，当进行插入或者删除后，会返回下一个元素的迭代器。以下是详细分析：

1. erase函数的正确用法
   • 标准库中的erase函数会返回被删除元素的下一个有效迭代器

vector<int> vec;
	vec.reserve(10); //预留10个int元素大小
	for (int i = 1; i <= 10; i++)
	{
		vec.push_back(i);
	}
	for (auto it = vec.begin(); it != vec.end(); )
	{
		if (*it % 2 == 0)//删除容器中的偶数
		{	
			//返回删除元素的下一个有效迭代器
			it=vec.erase(it);
		}
		else
		{
			++it;
		}
	}
	for (auto it = vec.begin(); it != vec.end(); ++it)
	{
		cout << *it << " " ;
	}	

2. insert函数的正确用法
   • insert函数同样会返回新插入元素的迭代器

vector<int> vec;
vec.reserve(10); //预留10个int元素大小
for (int i = 1; i <= 10; i++)
{
	vec.push_back(i);
}
//在5的倍数前插入1
for (auto it = vec.begin(); it != vec.end(); ++it)
{
	if (*it % 5 == 0)
	{	
		//返回已插入元素的下一个有效迭代器
		it=vec.insert(it,1);//这里1是插入5的前面,返回插入元素的下一个有效迭代器实际是指向5
		++it; //所以这里需要后移一位，移动元素5的下一个位置，即6；
	}
}
for (auto it = vec.begin(); it != vec.end(); ++it)
{
	cout << *it << " " ;
}	

总结

迭代器失效看起来很复杂，但只要记住几个简单的规则，就能轻松避开这个坑：

vector: 插入或删除元素后，该位置及其后面的迭代器都会失效；如果重新分配内存，所有迭代器都会失效。
list/forward_list: 只有被删除元素的迭代器会失效。
map/set/multimap/multiset: 只有被删除元素的迭代器会失效。
unordered_map/unordered_set: 插入操作可能导致所有迭代器失效（rehash）；删除操作只会导致被删除元素的迭代器失效。

迭代器失效：99%的C++程序员都会踩的坑 !