vector模拟实现

vector模拟实现：Gitee

reserve

//开空间
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				//动态申请n个T类型的空间
				T*tmp = new T[n];
				//从_start位置开始向后复制sizeof(T)*size()字节的数据到tmp的内存位置
				memcpy(tmp, _start, sizeof(T)*size());
				_start = tmp;
				_finish = _start + size();
				_endofstorage = _start + n;
			}
		}

运行上面的代码，会发现挂了——why?

size()算原来旧空间的数据，旧空间的话——_finish和_start都是0,零减零应该还是0

调试显示_finish是0，而_start是已经指向新空间了，所以相减为负了

改造：把size()提前存好
//开空间
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				//动态申请n个T类型的空间
				T*tmp = new T[n];
				//从_start位置开始向后复制sizeof(T)*size()字节的数据到tmp的内存位置
				memcpy(tmp, _start, sizeof(T)*size());
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}

resize

//开空间+初始化
		void resize(size_t n, const T& val = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else//n>size()
			{
				//空间容量不够
				if (n > capacity())
				{
					reserve(n);
				}
				//size()<n<capacity()
				while (_finish < _start + n)//指针
				{
					*_finish = val;
					_finish++;
				}
			}
		}

迭代器失效

insert

namespace std
{
	void test_vector1()
	{
		vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.insert(pos, 20);//2的前面插入20
		}
		//在insert以后pos就失效了
		cout << *pos << endl;//访问
		*pos = 100;//修改
	}
}

调试出现报错：

在insert以后pos就失效了——增容导致的（扩容之后pos还指向旧空间）

反观下面这段代码，先增容后，没有报错：
namespace std
{
	void test_vector1()
	{
		std::vector<int>v;

		v.reserve(8);//先增容

		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		std::vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.insert(pos, 20);//2的前面插入20
		}
		cout << *pos << endl;//访问
		*pos = 100;//修改
		pos++;
	}
}
在insert过程空间足够，没有增容，pos还是指向原来的位置

访问不会报错，那么我们依旧认为pos失效了

这里的失效指的是pos的意义变了，pos不再指向原来的值！

总结insert的失效2中情况：

第一种：由于insert扩容，导致pos失效，pos指向的空间释放，pos本质上是一个野指针

第二种：insert插入数据，没有扩容，我们也认为pos失效了，因为pos的意义变了，不再指向原来的数据

erase

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		std::vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.erase(pos);
		}
		cout << *pos << endl;
		*pos = 100;
	}
}

调试出现报错：不能解引用！

erase导致pos失效了，pos没有野指针，只是意义变了，但是vs版本下进行了强制检查，都不能访问

下面这段代码同样会报错：

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//要求删除v中所有偶数
		std::vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}
			it++;
		}
	}
}

正确的写法：erase返回删除数据的下一个数据的位置

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//要求删除v中所有偶数
		std::vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				//erase返回删除数据的下一个数据的位置
				it = v.erase(it);
			}
			else
			{
				it++;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

总结：insert和erase以后的迭代器都失效了，一定不要直接去访问或解引用insert或erase后的迭代器

【C++初阶】vector(中)

vector模拟实现

reserve

resize

迭代器失效

insert

erase