CD43.vector模拟实现(2)-CSDN博客

vector(const vector<value_type>& x)
	:start(0), finish(0), end_of_storage(0)
{
	start = new T[x.capacity()];
	memmove(start, x.start, x.size()*sizeof(value_type));
	finish = start + x.size();
	end_of_storage = start + x.capacity();
}

注:new的参数可以为capacity,也可以为size,这个C++标准没有规定,空间可以不一样,但是有效元素必须一样

写法2

复用reserve和memmove函数

这个代码有问题:

vector(const vector<value_type>& x)
	:start(0), finish(0), end_of_storage(0)
{
	reserve(x.capacity());
	memmove(start, x.start, x.size() * sizeof(value_type));
}

测试代码

void const_vector_print(const mystl::vector<int> v)
{
	for (size_t i = 0;i < v.size(); i++)
		std::cout << v[i] << " ";
}

void test6()
{
	mystl::vector<int> v;
	v.push_back(1); 
	v.push_back(2);
	v.push_back(3); 
	const_vector_print(v);
	return;
}

运行结果:什么都没有打印

调试找bug

什么都没有打印,可以判定没有进入循环,

下断点到循环,看看情况:

start和finish的地址一样,v.size()计算出来为0,没有进入循环,可以断定拷贝构造函数出了问题,

下断点到拷贝构造函数,再次调试:

x.capacity()计算出来是4,进入reserve函数内部:

对空的vector进行reserve,看以下分析图:

解决方法:修改拷贝构造函数

reserve没有更新finish,那就手动更新finish

vector(const vector<value_type>& x)
	:start(0), finish(0), end_of_storage(0)
{
	reserve(x.capacity());
	finish = start + x.size();
	memmove(start, x.start, x.size() * sizeof(value_type));
}

而且标准库也是这样实现的:

运行结果:

同理,reserve函数也要修改:

void  reserve(size_type n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		size_t len = size();//delete前先保存元素的个数!
		bool flag = false;
		if (size() == 0)
		{
			flag = true;
			len = n;
		}
		memmove(tmp,start , size()* sizeof(value_type));
		delete[] start;
		if (flag)//如果vector在什么元素都没有
		{
			start = finish = tmp;
		}
		else
		{
			start = tmp;
			finish = start + len;
		}
		end_of_storage = start + n;
	}
}

测试代码

void test4()
{
	mystl::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	mystl::vector<int> v2(v1);
	for (auto& a:v2)
		std::cout << a << " ";
}

运行结果:

2.operator[ ]

参数保持一样的类型:

注意到返回类型被重定义过,因此先进行重定义:

typedef value_type& reference;
typedef const value_type& const_reference;

必须保证提供的n是合法的,换句话说,n<size(),可以使用assert断言

reference operator[] (size_type n)
{
	assert(n < size());
	return *(start + n);//也可以写成start[n]
}

const_reference operator[] (size_type n) const
{
	assert(n < size());
	return *(start + n);//也可以写成start[n]
}

测试代码

1.没有const修饰

void test5()
{
	mystl::vector<int> v;
	v.push_back(1); v[0]++;
	v.push_back(2); v[1]++;
	v.push_back(3); v[2]++;
	for (auto& a : v)
		std::cout << a << std::endl;
	return;
}

运行结果:

2.有const修饰

void const_vector_print(const mystl::vector<int> v)
{
	for (size_t i = 0;i < v.size(); i++)
		std::cout << v[i] << " ";
}

void test6()
{
	mystl::vector<int> v;
	v.push_back(1); 
	v.push_back(2);
	v.push_back(3); 
	const_vector_print(v);
	return;
}

运行结果:

3.insert

参数保持一样的类型,为了简单起见,这里只实现第一个

首先要断言,position必须合法:

assert(position >= start && position <= finish);

插入前先看看是否需要扩容,可以直接借用CD42.vector模拟实现(1)文章的push_back函数的代码:

if (finish == nullptr)
	reserve(4);
if (finish == end_of_storage)
	reserve(capacity() * 2);

和CD38.【C++ Dev】string类的模拟实现(2)文章类似的思路,先移动再插入

迭代器失效问题

如果insert的返回值是void,

void insert(iterator position, const value_type& val)
{
	assert(position >= start && position <= finish);
	if(finish == nullptr)
		reserve(4);
	if (finish == end_of_storage)
		reserve(capacity() * 2);
	iterator i = finish-1;
	while (i >= position)
	{
		*(i+1) = *i;
		i--;
	}
	*position = val;
	finish++;
}

头插:

void test7()
{
	mystl::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.insert(v.begin(), 3);
	return;
}

尾插:

void test7()
{
	mystl::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.insert(v.end(), 3);
	return;
}

中间位置插入:

void test7()
{
	mystl::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.insert(v.begin() + 1, 4);
	return;
}

貌似没有问题,但是如果是这个测试代码:

void test7()
{
	mystl::vector<int> v;
	v.push_back(1);
	auto pos = v.begin();
	for (size_t i = 2; i <= 8; i++)
		v.insert(pos, i);
	return;
}

运行结果会出问题:

引出迭代器失效问题

pos记录的是原来v的start的值,如果v扩容,start的值会改变,但pos的值没有更新,而且原先的内存空间被释放会导致非法访问,因此再执行v.insert(pos, i);就会出问题(即pos为野指针)

解决方法:扩容后更新pos的值,STL的解决方法:返回值为iterator

iterator insert(iterator position, const value_type& val)
{
	assert(position >= start && position <= finish);
	if(finish == nullptr)
		reserve(4);
	if (finish == end_of_storage)
		reserve(capacity() * 2);

	iterator i = finish-1;
	while (i >= position)
	{
		*(i+1) = *i;
		i--;
	}
	*position = val;
	finish++;
	return start;
}

注:position不能引用传参,有可能insert的第一个参数会做算术运算,例如:

v.insert(pos+20, i);

测试代码:

void test7()
{
	mystl::vector<int> v;
	v.push_back(1);
	auto pos = v.begin();
	for (size_t i = 2; i <= 8; i++)
		pos=v.insert(pos, i);
	return;
}

验证pos是否更新:
原先:

扩容更新后:

运行结果:退出代码为0

当然CD42.vector模拟实现(1)文章的push_back可以复用insert的代码

1.如果不接收insert的返回值,扩容要慎重,修改可能会报错,因为不一定扩容,所以不一定失效;

2.insert以后就不要使用原本定义的迭代器