23迭代器失效

迭代器失效

• 容器调用erase方法，当前位到容器末尾元素位置的迭代器失效，前半部分有效
• 容器调用insert方法，当前位到容器末尾元素位置的迭代器失效，前半部分有效
• 扩容会导致内存转移，迭代器全部失效

int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	auto it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		if (*it % 2 == 0)
		{
			//insert是把it位置的元素向后移，当前位置添加新元素
			//第一次insert后迭代器就会失效
			vec.insert(it, *it - 1);
			break;
		}
	}
	it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		if (*it % 2 == 0)
		{
			//第一次erase后迭代器就会失效
			vec.erase(it);
			break;
		}
	}
}

迭代器失效的解决办法

对插入删除点的更新操作

int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	for (auto v : vec)
		cout << v << " ";
	cout << endl;
	auto it = vec.begin();
	/*for (; it != vec.end(); ++it)
	{
		if (*it % 2 == 0)
		{
			vec.erase(it);
		}
	}*/
	//for循环改写为while，记录erase时迭代器的位置
	while (it != vec.end())
	{
		if (*it % 2 == 0)
		{
			//erase时保留当前位置迭代器，并不再进行it++
			it = vec.erase(it);
		}
		else
			++it;
	}
	for (auto v : vec)
		cout << v << " ";
	cout << endl;
	//记录insert时迭代器的位置
	for (it = vec.begin(); it != vec.end(); ++it)
	{
		if (*it % 2 != 0)
		{
			//insert时保留当前位置迭代器，额外进行一次it++
			it = vec.insert(it, *it + 1);
			++it;
		}
	}
	for (auto v : vec)
		cout << v << " ";
	cout << endl;
	return 0;
}

迭代器失效的底层原理

容器底层维护了一个迭代器的链表，每个节点代表着一个迭代器，迭代器节点内包含其指向的元素位置和其所属vector指针，迭代器节点按照其指向的元素位置排序，当检查到的迭代器需要置为失效时，则该节点其所属vector指针置为null，节点被删除。

struct Iterator_Base
{
	Iterator_Base(iterator* c = nullptr, Iterator_Base* n = nullptr)
		:_cur(c), _next(n) {}
	iterator* _cur;
	Iterator_Base* _next;
};

void verify(T* first, T* last)
{
	Iterator_Base* pre = &this->_head;
	Iterator_Base* it = this->_head._next;
	while (it != nullptr)
	{
		if (it->_cur->_p >= first && it->_cur->_p <= last)
		{
			// 迭代器失效，把iterator持有的容器指针置空
			it->_cur->_pVec = nullptr;
			// 删除当前迭代器节点，继续判断后面的迭代器节点是否失效
			pre->_next = it->_next;
			delete it;
			it = pre->_next;
		}
		else
		{
			pre = it;
			it = it->_next;
		}
	}
}
iterator insert(iterator it, const T& val)
{
	// 1.不考虑扩容 2.不考虑it._p的指针合法性
	verify(it._p - 1, _last);
	T* p = _last;
	//从后方开始先依次析构
	while (p > it._p)
	{
		_allocator.construct(p, *(p - 1));
		_allocator.destroy(p - 1);
		p--;
	}
	_allocator.construct(p, val);
	_last++;
	return iterator(this, p);
}
iterator erase(iterator it)
{
	verify(it._p - 1, _last);
	T* p = it._p;
	while (p < _last - 1)
	{
		_allocator.destroy(p);
		_allocator.construct(p, *(p + 1));
		p++;
	}
	_allocator.destroy(p);
	_last--;
	return iterator(this, it._p);
}