C++迭代器二：详解迭代器失效的底层核心原理

文章目录一、迭代器失效问题二、如何解决迭代器失效问题三、迭代器失效底层原理一、迭代器失效问题迭代器的失效问题：对容器的操作影响了元素的存放位置，称为迭代器失效。失效情况：1.当容器调用erase()方法后，当前位置到容器末尾元素的所有迭代器全部失效。2.当容器调用insert()方法后，当前位置到容器末尾元素的所有迭代器全部失效。3.如果容器扩容，在其他地方重新又开辟了一块内存。原来容...

硕～

3907人浏览 · 2020-03-12 11:43:21

硕～ · 2020-03-12 11:43:21 发布

文章目录

一、迭代器失效问题

迭代器的失效问题：对容器的操作影响了元素的存放位置，称为迭代器失效。
失效情况：
1.当容器调用erase()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
2.当容器调用insert()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
3.如果容器扩容，在其他地方重新又开辟了一块内存。原来容器底层的内存上所保存的迭代器全都失效了。
4.不同容器的迭代器，是不能进行比较运算的。
在这里插入图片描述
失效问题1：我们先使用库中的vector来看看什么是失效问题：把vec容器中所有的偶数全部删除

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的奇数
在这里插入图片描述

三、解决迭代器失效底层原理

主要功能实现：
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;

测试结果：测试成功，迭代器失效。
在这里插入图片描述

四、源代码

源代码：这里只实现了一部分最核心的功能，有兴趣的小伙可以查找资料剖析一下vector的源码。

//容器的空间配置器
template <typename T>
struct Allocator
{
	T* allocate(size_t size)//只负责内存开辟
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void *p)//只负责内存释放
	{
		free(p);
	}
	void construct(T *p, const T &val)//已经开辟好的内存上，负责对象构造
	{
		new (p) T(val);//定位new，指定内存上构造val，T(val)拷贝构造
	}
	void destroy(T *p)//只负责对象析构
	{
		p->~T();//~T()代表了T类型的析构函数
	}
};

template <typename T, typename Alloc = Allocator<T>>
class vector//向量容器
{
public:
	vector(int size = 10)//构造
	{
		//_first = new T[size];
		_first = _allocator.allocate(size);
		_last = _first;
		_end = _first + size;
	}
	~vector()//析构
	{
		//delete[]_first;
		for (T *p=_first; p!=_last; ++p)
		{
			_allocator.destroy(p);//把_first指针指向的数组的有效元素析构
		}
		_allocator.deallocate(_first);//释放堆上的数组内存
		_first = _last = _end = nullptr;
	}
	vector(const vector<T> &rhs)//拷贝构造
	{
		int size = rhs._end - rhs._first;//空间大小
		//_first = new T[size];
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;//有效元素
		for (int i=0; i<len; ++i)
		{
			//_first[i] = rhs._first[i];
			_allocator.construct(_first+i, rhs._first[i]);
		}
		_last = _first + len;
		_end = _first + size;
	}
	vector<T>& operator=(const vector<T> &rhs)//赋值运算符重载
	{
		if (this == &rhs)
		{
			return *this;
		}

		//delete[]_first;
		for (T *p=_first; p!=_last; ++p)
		{
			_allocator.destory(p);//把_first指针指向的数组的有效元素析构
		}
		_allocator.deallocate(_first);//释放堆上的数组内存

		int size = rhs._end - rhs._first;//空间大小
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;//有效元素
		for (int i=0; i<len; ++i)
		{
			_allocator.construct(_first+i, rhs._first[i]);
		}
		_last = _first + len;
		_end = _first + size;
		return *this;
	}
	void push_back(const T &val)//尾插
	{
		if (full())
		{
			expand();
		}
		//*_last++ = val;
		_allocator.construct(_last, val);//_last指针指向的内存构造一个值为val的对象
		_last++;
	}
	void pop_back()//尾删
	{
		if (empty()) return;
		verify(_last - 1, _last);
		//erase(it); verift(it._ptr, _last);
		//insert(it,val); verift(it._ptr, _last);
		//--_last;
		//不仅要把_last指针--，还需要析构删除的元素
		--_last;
		_allocator.destroy(_last);
	}
	T back()const//返回容器末尾元素值
	{
		return *(_last - 1);
	}
	bool full()const
	{
		return _last == _end;
	}
	bool empty()const
	{
		return _first == _last;
	}
	int size()const//返回容器中元素个数
	{
		return _last - _first;
	}
	T& operator[](int index)
	{
		if (index < 0 || index >= size())
		{
			throw "OutOfRangeException";
		}
		return _first[index];
	}
	//迭代器一般实现成容器的嵌套类型
	class iterator
	{
	public:
		friend class vector <T, Alloc>;
		//新生成当前容器某一个位置元素的迭代器
		iterator(vector<T, Alloc> *pvec = nullptr
			, T *ptr = nullptr)
			:_ptr(ptr), _pVec(pvec)
		{
			Iterator_Base *itb = new Iterator_Base(this, _pVec->_head._next);
			_pVec->_head._next = itb;
		}
		bool operator!=(const iterator &it)const
		{
			//检查迭代器的有效性
			if (_pVec == nullptr || _pVec != it._pVec)//迭代器为空或迭代两个不同容器
			{
				throw "iterator incompatable!";
			}
			return _ptr != it._ptr;
		}
		void operator++()
		{
			//检查迭代器有效性
			if (_pVec == nullptr)
			{
				throw "iterator incalid!";
			}
			_ptr++;
		}
		T& operator*()
		{
			//检查迭代器有效性
			if (_pVec == nullptr)
			{
				throw "iterator invalid!";
			}
			return *_ptr;
		}
		const T& operator*()const
		{
			if (_pVec == nullptr)
			{
				throw "iterator invalid!";
			}
			return *_ptr;
		}
	private:
		T *_ptr;
		//当前迭代器是哪个容器对象
		vector<T, Alloc> *_pVec;//指向当前对象容器的指针
	};
	iterator begin()
	{
		return iterator(this,_first);
	}
	iterator end()
	{
		return iterator(this,_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;
			}
		}
	}

	//自定义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);
	}

	//自定义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);
	}
private:
	T *_first;//起始数组位置
	T *_last;//指向最后一个有效元素后继位置
	T *_end;//指向数组空间的后继位置
	Alloc _allocator;//定义容器的空间配置器对象

	//容器迭代器失效增加代码
	struct Iterator_Base
	{
		Iterator_Base(iterator *c = nullptr, Iterator_Base *n =nullptr)
			:_cur(c), _next(n){}
		iterator *_cur;
		Iterator_Base *_next;
	};
	Iterator_Base _head;

	void expand()//扩容
	{
		int size = _end - _first;
		//T *ptmp = new T[2*size];
		T *ptmp = _allocator.allocate(2*size);
		for (int i=0; i<size; ++i)
		{
			_allocator.construct(ptmp+i, _first[i]);
			//ptmp[i] = _first[i];
		}
		//delete[]_first;
		for (T *p=_first; p!=_last; ++p)
		{
			_allocator.destroy(p);
		}
		_allocator.deallocate(_first);
		_first = ptmp;
		_last = _first + size;
		_end = _first + 2*size;
	}
};

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

所有评论(0)

查看更多评论

硕～

@qq_42441693

已为社区贡献3条内容