【C++】vector模拟实现的补充知识

羚羊角

发布于 2024-11-15 08:24:50

960

文章被收录于专栏：羚羊角的特别专栏羚羊角的特别专栏

本篇以模拟实现vector为背景，来补充一些更深入的知识。

1.迭代器区间初始化

vector里面有一个支持迭代器区间的构造，大家还记得吗？

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{

}

vector本就是一个类模板，这个构造函数又是一个函数模板，所以类模板的成员函数，还可以继续是函数模板。

为什么要这样写？不直接写成iterator类型，而是用模板？

因为，如果类型写成iterator，这个迭代器就只能是vector的迭代器，但是写成函数模板，他就可以是任何类型的迭代器。里面的代码逻辑如下。

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)//不是小于，因为如果是链表，空间是不连续的
	{
		push_back(*first);
		++first;
	}
}

测试一下。

void test8()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.vector_print(v1);
	vector<int> v2(v1.begin(), v1.begin() + 3);//迭代器区间初始化
	v2.vector_print(v2);
}

不仅如此，因为我们写的迭代器可以是任意类型，所以我们还可以用list去初始化。

list<int> li;
li.push_back(10);
li.push_back(10);
li.push_back(10);
li.push_back(10);
vector<int> v(li.begin(), li.end());
v.vector_print(v);

这就能实现一种容器去初始化另一种容器，但是要求类型是匹配的。

2.n个val初始化

构造函数里面还有一个n个val初始化的接口。

vector(size_t n, const T& val = T())
{

}

函数内部代码实现如下。

vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

假如我们现在vector里面存string，然后用10个“xxx”初始化。

vector<string> vs(10, "xxx");
vs.Container_print(vs);

3.初始化接口选择错误？

3.1 接口匹配错误

vector<string> vs(10, "xxx");
vs.Container_print(vs);

vector<int> v1(10);
v1.Container_print(v1);

vector<int> v2(10, 1);
v2.Container_print(v2);

前两个初始化没问题，后面那个出错了，而且报错在迭代器区间初始化的push_back(*first)这行。为什么会报错在这里？v2我们应该是想用10个1初始化，怎么调用了迭代器区间初始化？

他们会优先选择参数类型最匹配的，所以前两个vs和v1初始化在两中初始化接口中都选择了n个val的接口， int到size_t类型转换一下就好了。但是v2有两种选择，如果选择n个val初始化， int到size_t类型转换，T推导出为int类型，类型有点不太匹配；如果选择迭代器区间初始化，它的两个参数类型是一样的，而v2的两个参数类型也是一样的，需要推导，所以v2选择了要推导的接口，就是迭代器区间初始化，对他来说是更匹配的。10和1就被当成了两个指针，在push_back(*first)这行解引用，就出错了。

3.2 解决方法

1.加一个第一个参数类型是int的n个val初始化接口，就能匹配。

vector(int n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

2.在10后面加个u，直接选择n个val初始化接口。

vector<int> v2(10u, 1);
v2.Container_print(v2);

4.对reserve的终极改造

现在我们在拿vector里面存string举例。

vector<string> vs;
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.Container_print(vs);

存四个string没问题。存5个呢？空间不够了要开新空间。

vector<string> vs;
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.push_back("xxxxx");
vs.Container_print(vs);

vs.push_back("xxxxx");
vs.Container_print(vs);

我们会发现程序直接就是一个大崩溃。原因如下。

问题就出在memcpy，因为memcpy是按字节拷贝，是浅拷贝。T是内置类型的时候是没问题的，自定义类型就不可以。

delete之后什么都没了。

所以在这里我们要写一个深拷贝，代码如下。

void reserve(size_t n)
{
	if (n > capacity()) //n大于capacity扩容
	{
		size_t old_size = size();
		T* t = new T[n];//开辟新空间
		//memcpy(t, _start, size() * sizeof(T));//拷贝旧空间的数据到新空间
		for (size_t i = 0; i < old_size; i++)
		{
			t[i] = _start[i]; //赋值，因为空间已经new好了
		}
		delete[] _start; //释放旧空间
		_start = t; //指向新空间
		_finish = t + old_size;//用old_size更新数据
		_end_of_storage = _start + n;//更新数据
	}
	//其他不变
}

现在代码就没问题了。测试一下前面那个没通过的例子。