《STL容器篇》-Vector模拟实现

一、本篇接口实现介绍

iterator begin()
const_iterator begin()const
iterator end()
const_iterator end()const
vector()
template<class InputIterator>
vector(InputIterator first, InputIterator last)
vector(const vector<T>& v)//传统写法
vector(const vector<T>& v)//现代写法
void swap(vector<T>& v)
~vector()
vector<T>& operator=(const vector<T>& v)//传统写法
vector<T>& operator=(vector<T> v)//现代写法
void reserve(size_t n)
void resize(size_t n, const T& x = T())
void push_back(const T& x)
T& operator[](size_t pos)
const T& operator[](size_t pos)const
size_t capacity()const
size_t size()const
bool empty()const
void clear()
iterator insert(iterator pos, const T& x)
iterator earse(iterator pos)

本篇不为造更好的轮子，只为让我们了解一点底层实现，更好的掌握vector的使用，上述接口有许多和string篇的相似，因此，这里只挑选部分值得我们注意的点进行解析。

二、接口全实现

https://gitee.com/zxlfx/c-code-warehouse/tree/master/2022_7_20/2022_7_20

三、部分接口解析

3.1插入数据后，迭代器会失效

        iterator insert(iterator pos, const T& x)
		{
			assert(pos>=_start && pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t n = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + n;
			}

			T* end = _finish - 1;
			T* start = pos;
			while (end >= start)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = x;
			_finish++;
			return pos;
		}

对于vector来说，在pos位置之前要插入数据，就得不断挪动数据，对于vector的扩容，原空间会被销毁，同时将原空间的数据拷贝至新空间，如果扩容了，那么pos还会指向原空间，此时pos就是野指针，属于迭代器失效的一种情况，解决办法，通过返回新空间的pos让原pos接受。第二种，如果没有扩容，举个例子，vector中有1 、2、3、4，pos指向3，在3前面插入30之后，pos还是会指向原空间，此时pos指向的是30，它指向的内容变了，属于意义变了，这是迭代器失效的第二种情况。

~提问环节~

如果让你在偶数的前面插入该偶数*10的数字，以下写法正确吗？

void test()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	while(it!=v.end())
	{
		if (*it % 2 == 0)
		{
			v.insert(it, *it * 10);
		}
		it++;
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

在调用test()之后，程序崩溃了？这是为什么呢？

跟随程序的执行流可知，当it指向2时，需要插入20，那么将挪动数据2、3、4、5、6，让20插入到2原来的位置，然后++it，++it之后还是指向2，将陷入无穷的循环，导致程序崩溃。

这属于迭代器的意义变了，如果出现扩容，it同时也会变成野指针（指向原空间），解决办法是：利用insert的返回值，该返回值指向的是最新插入元素的位置。

更改代码后：

void test()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.insert(it, (*it) * 10);
			it += 2;
		}
		else
		{
			it++;
		}
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

这里用it = v.insert(it, (*it) * 10)。可以避免it是野指针的问题，同时it+=2，可以跳至该偶数的下一个数。

同理，erase也会出现迭代器失效的问题，因为erase删除数据也是通过挪动数据实现的。

~提问环节~

vector中所有的偶数，以下代码正确吗？

void test()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
		it++;
	}
}

乍一看，这代码好像没什么问题，遍历一遍vector即可，如果是偶数就删除，不是偶数就++，逻辑似乎很正确，但站在erase实现的角度来看，这里会出现迭代器失效的问题。

因为erase删除数据是通过挪动数据覆盖实现的，如果it指向2，那么删除2之后，it指向的就是3了，然后++，那么3就没判断了，而是it直接指向了4，然后删除4之后，it指向5，++之后，it指向6，删除6，it等于end（），++之后，it指向end()之后的值，永远不可能与end()的相等了，陷入死循环。

如果vector为1、2、3、4、5，那么程序又能删除偶数了。

这里我改使用gcc编译器，因为vs2019能够检测到erase迭代器失效的问题。

 

但是我们都知道，在删除2之后，it指向3，之后++it，那么就会跳过3的判断，如果这里把3改为2，vector为1 2 2 4 5，那么我们可预测结果会为1、2、5.。

如何解决迭代器失效呢？利用erase的返回值，同样的，erase的返回值指向的是原删除元素的下一个位置。

 修改代码后：

void test()
{
	vector<int> v{ 1,2,2,4,5,6 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);
		}
		else
		{
			it++;
		}
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

 有的人可能有疑惑，返回值好像并没有什么用呀，因为it还是指向原位置呀，是的it还是指向原位置，但保不齐调用erase之后发生了缩容，这是erase的实现者决定的，如果发生了缩容，那么it就是野指针，接受erase的返回值可避免野指针的出现。经过实验，vs2019、g++的erase都没有采取缩容，因为缩容是一种时间换空间的做法，对于当代计算机而言，空间不是特别的缺（根据摩尔定律）。

对于vector，值得探究的还有个反向迭代器的适配（涉及迭代器萃取、模板的特化），这里我准备在list中引入，如有错误或者疑惑的地方，欢迎读者与我交流~。