跳至主要內容

迭代器失效的底层核心原理

张威大约 8 分钟c/c++运算符重载迭代器

迭代器失效的底层核心原理

迭代器失效问题

对容器的操作，称为。

迭代器失效情况

  1. 当容器调用**erase()方法后，到**的所有迭代器全部失效。

  2. 当容器调用**insert()方法后，到**的所有迭代器全部失效。

  3. 如果容器**，在其他地方重新又开辟了一块内存。原来容器底层的内存上所保存的迭代器**了。

  4. 不同容器的迭代器，是不能进行比较运算的。

失效问题1：把vec容器中所有的偶数全部

先使用库中的vector来看看什么是失效问题

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

	//把vec容器中所有的偶数全部删除
	auto it = vec.begin();
	for (; it!=vec.end(); ++it)
	{
		if (*it % 2 == 0)
		{
			vec.erase(it);//insert(it,val) erase(it)
			break;//只删除第一个偶数
		}
	}

	return 0;
}

当我们调用vec.erase时加上break时候，程序执行成功。

但如果我们去掉break时候：，第一次调用erase后，迭代器it就失效了，再对其进行++运算符重载函数调用就崩溃了。

失效问题2：给vec容器中所有的偶数前面一个小于偶数值1的数字

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

	//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
	auto it = vec.begin();
	for (; it!=vec.end(); ++it)
	{
		if (*it % 2 == 0)
		{
			vec.insert(it, *it-1);
			break;
		}
	}
}

当我们调用vec.insert时加上break时候，程序执行成功。

但如果我们去掉break时候：。这里的迭代器在第一次insert之后，iterator就失效了，再执行运算符重载函数调用就崩溃了。

如何解决迭代器失效问题

解决方案：对插入/删除点的迭代器进行更新操作。

在这里插入图片描述
在这里插入图片描述

解决失效问题1：解决删除问题

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

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

//把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it!=vec.end())
{
	if (*it % 2 == 0)
	{
		it = vec.erase(it);//insert(it,val) erase(it)
        //更新当前删除位置迭代器
	}
	else
	{
		++it;
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

解决失效问题2：解决增加问题

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

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (; it!=vec.end(); ++it)
{
	if (*it % 2 == 0)
	{
		it = vec.insert(it, *it-1);//更新当前增加位置迭代器
		++it;	//在当期遍历前一个位置插入，插入后要返回下一个位置
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

return 0;

解决迭代器失效底层原理

主要功能实现： 1.在iterator私有成员下添加一个指向当前对象的指针，让迭代器知道当前迭代的容器对象，不同容器之间不能相互比较。

vector<T, Alloc> *_pVec;//指向当前对象容器的指针

2.容器迭代器失效增加代码，它是一个结构体维护了一个链表。cur是指向某一个结构体的指针，又定义了一个指向下一个Iterator_Base节点的地址，还定义了一个头节点。记录了用户从中获取的哪一个元素的迭代器，记录在Iterator_Base链表中，哪一个迭代器增加或删除要让其失效并重新更新。

在这里插入图片描述
在这里插入图片描述
//容器迭代器失效增加代码
struct Iterator_Base
{
	Iterator_Base(iterator *c = nullptr, Iterator_Base *n =nullptr)
			:_cur(c), _next(n){}
	iterator *_cur;
	Iterator_Base *_next;
};
Iterator_Base _head;

3.构造函数中添加了接收外面传进容器对象的地址，将迭代器成员变量初始化。构造函数即新生成当前元素某一个位置的迭代器。

//新生成当前容器某一个位置元素的迭代器
iterator(vector<T, Alloc> *pvec
	, T *ptr = nullptr)
	:_ptr(ptr), _pVec(pvec)
{
	// 下面这两行相当于头插法
    Iterator_Base *itb = new Iterator_Base(this, _pVec->_head._next);
	_pVec->_head._next = itb;
}

4.!=运算符号重载前要检查迭代器的有效性，即两个迭代器比较之前检查是否失效，或者是否是同一类型容器的迭代器。

bool operator!=(const iterator &it)const
{
	//检查迭代器的有效性
	if (_pVec == nullptr || _pVec != it._pVec)//迭代器为空或迭代两个不同容器
	{
		throw "iterator incompatable!";
	}
	return _ptr != it._ptr;
}

5.++运算符重载前检查有效性。

void operator++()
{
	if (_pVec == nullptr)
	{
		throw "iterator incalid!";
	}
	_ptr++;
}

6.* 运算符重载前检查有效性。

T& operator*()
{
	//检查迭代器有效性
	if (_pVec == nullptr)
	{
		throw "iterator invalid!";
	}
	return *_ptr;
}
const T& operator*()const
{
	if (_pVec == nullptr)
	{
		throw "iterator invalid!";
	}
	return *_ptr;
}

7.pop_back中加入了verfiy，pop_back从当前末尾删除，verify检查有效性。在我们增加或删除后，把我们当前节点的地址到末尾的地址，全部进行检查，在存储的迭代器链表上进行遍历，哪一个迭代器指针指向的迭代器迭代元素的指针在检查范围内，就将相应迭代器指向容器的指针置为空，即为失效的迭代器。

void pop_back()//尾删
{
	if (empty()) return;
	verify(_last - 1, _last);
	//不仅要把_last指针--，还需要析构删除的元素
	--_last;
	_allocator.destroy(_last);
}
void verify(T *first, T *last)
{
	Iterator_Base *pre = &this->_head;
	Iterator_Base *it = this->_head._next;
	while (it != nullptr)
	{
		if (it->_cur->_ptr > first && it->_cur->_ptr <= last)
		{
			//迭代器失效，把iterator持有的容器指针置nullptr
			it->_cur->_pVec = nullptr;
			//删除当前迭代器节点，继续判断后面的迭代器节点是否失效
			pre->_next = it->_next;
			delete it;
			it = pre->_next;
		}
		else
		{
			pre = it;
			it = it->_next;
		}
	}
}

8.自定义insert实现(未考虑扩容与ptr合法性)。

//自定义vector容器insert方法实现
iterator insert(iterator it, const T &val)
{
	//1.这里我们未考虑扩容
	//2.还未考虑it._ptr指针合法性，假设它合法
	verify(it._ptr - 1, _last);
	T *p = _last;
	while (p > it._ptr)
	{
		_allocator.construct(p, *(p-1));
		_allocator.destroy(p - 1);
		p--;
	}
	_allocator.construct(p, val);
	_last++;
	return iterator(this, p);
}

9.自定义erase实现。

//自定义vector容器erase方法实现
iterator erase(iterator it)
{
	verify(it._ptr - 1, _last);
	T *p = it._ptr;
	while (p < _last-1)
	{
		_allocator.destroy(p);
		_allocator.construct(p, *(p+1));
		p++;
	}
	_allocator.destroy(p);
	_last--;
	return iterator(this, it._ptr);
}

测试1:比较it1与it2

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

auto it1 = vec.end();
auto it2 = vec.end();
cout << (it1 != it2) << endl;

测试结果：测试成功，它们都在vec.end。

测试2：加上pop_back

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

auto it1 = vec.end();
vec.pop_back();//verify(_last-1, _last)
auto it2 = vec.end();
cout << (it1 != it2) << endl;

测试结果：测试成功，此时迭代器失效。

测试3：使用insert并对迭代器更新

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

//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (; it!=vec.end(); ++it)
{
	if (*it % 2 == 0)
	{
		it = vec.insert(it, *it-1);//更新当前增加位置迭代器
		++it;
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

测试4：使用insert未对迭代器更新

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

//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (; it!=vec.end(); ++it)
{
	if (*it % 2 == 0)
	{
		vec.insert(it, *it-1);//更新当前增加位置迭代器
		++it;
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

测试结果：测试成功，迭代器失效

测试5.使用erase并对迭代器更新

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

//把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it!=vec.end())
{
	if (*it % 2 == 0)
	{
		it = vec.erase(it);//insert(it,val) erase(it)
		//break;//只删除第一个偶数
	}
	else
	{
		++it;
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

测试结果：删除成功。

测试6.使用erase未对源代码进行更新

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

//把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it!=vec.end())
{
	if (*it % 2 == 0)
	{
		vec.erase(it);//insert(it,val) erase(it)
		//break;//只删除第一个偶数
	}
	else
	{
		++it;
	}
}

for (int v : vec)
{
	cout << v << " ";
}
cout << endl;

测试结果：测试成功，迭代器失效。

Copyright © 2024 张威