C/C++ vector模拟实现

模拟实现：

框架

namespace yx
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
 
 
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

这里我们声明定义不分离

reverse()

新开一个空间，拷贝数据，然后释放旧空间

代码：

void reserve(size_t n)//满了要扩容
{
	if (n > capacity())
	{
		T* tmp = new T[n];//new 开空间 + 初始化
		memcpy(tmp,_start,sizeof(T) * size());//一个一个字节的拷贝下来
		delete[] _start;
		_start = tmp;
	}
	_finish = _start + size();
	_end_of_storage = _start + n;
}

capacity()

size_t capcaity() const
{
	return _end_of_storage - _start;
}

size()

size_t size() const
{
	return _finsh - _start;
}

operator[]

俩版本，一个可读可写，一个只读

T& operator[](size_t i)
{
	assert(i < size());
 
 
	return _start[i];
}

const T& operator[](size_t i) const 
{
	assert(i < size());
 
 
	return _start[i];
}

push_back()

分析

void push_back(const T& x)
{
	if (_finish == _end_of_storage)//扩容
	{
		size_t newcapacity = capacity() == 0 ? 4 : capcaity * 2;
		reverse(newcapacity);
	}
	*_finish = x;
	++_finish;
	
}

这时我们来运行一下

意外的出错了，为什么呢？

我们来调试一下

我们发现_finish竟然等于0，

其实问题出现在size(),size = _finish - _start ,  但这不是正好吗？

我们来看一个图，start还是不是原来的start，当然不是了，这是start已经被更新了 ，start = tmp，相当于旧的finish 减新的start,size已经不是我们要的哪个size了。

修改方法

第一种

我们先修改一下start的位置

在reserve中

void reserve(size_t n)//满了要扩容
{
	if (n > capacity())
	{
		T* tmp = new T[n];//new 开空间 + 初始化
 
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
			delete[] _start;
		}
		_finish = tmp + size();
 
		_start = tmp;
		_end_of_storage = _start + n;
	}
	
}

测试成功，但这强依赖顺序了，不太好。

第二种

oldsize方法提前存储

void reserve(size_t n)//满了要扩容
{
	if (n > capacity())
	{
		size_t oldsize = size();//oldsize提前存储
		T* tmp = new T[n];//new 开空间 + 初始化
 
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
			delete[] _start;
		}
		
		_start = tmp;
		_finish = tmp + oldsize;
		_end_of_storage = _start + n;
	}
	
}

~vector()

~vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finish = _end_of_storage;
	}
}

迭代器iterator

下面写的只是一种方式

typedef T* iterator;
 
iterator begin()
{
	return _start;
}
 
iterator end()
{
	return _finish;
}

我们来用范围for遍历测试一下

测试通过

三种遍历方式

for (size_t i = 0; i < v1.size(); i++)
{
	cout << v1[i] << " ";
}cout << endl;
 
for (auto e : v1)
{
	cout << e << " ";
}cout << endl;
 
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
	cout << *it << " ";
	++it;
}cout << endl;

const迭代器

typedef const T* const_iterator;
 
const_iterator begin() const
{
	return _start;
}
 
const_iterator end() const
{
	return _finish;
}

pop_back()

pop_back()
{
	assert(size() > 0);
 
	--_finish;
}

insert()

头插

代码：

//头插，在x前插入
void insert(iterator pos, const T& x)
{
	//检查是否需要扩容
	if (_finish == _end_of_storage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
 
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;
}

我们测试一下

为什么是个随机值呢？

insert迭代器失效

此时_finish = _end_of_storage ，出现了扩容，

导致出现了迭代器失效，pos变为野指针

扩容后，start，finish _end_of_storage都去了新空间，旧空间释放了，而pos还在旧空间里，pos为野指针，所以导致了随机值。

修改方法，算出pos与start的距离

修改后代码：

void insert(iterator pos, const T& x)
{
	//检查是否需要扩容
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
 
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);//扩容完后pos为野指针
 
		pos = _start + len;//pos找到新空间位置
	}
 
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;
}

测试通过

it会不会失效呢？失效后的迭代器还能访问吗？

实参传给形参，形参的改变不会影响实参。但如果出现了扩容呢？insert函数内的pos可以解决野指针问题，但it解决不了。我们就不敢访问这个迭代器了。因为出现了野指针。

我们访问一下迭代器，出现野指针了吧。

迭代器失效后的建议是不要访问。

如果我们给pos加个引用呢？

测试一下

我们发现begin传不过去了，为什么？

v1.begin()，begin() 返回一个迭代器，而且是传值返回，c++规定，传值返回返回的不是_start，返回的是其拷贝，生成临时对象，临时对象具有常性，所以非不要不访问。

erase()

头删

void erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
 
	iterator it = pos + 1;
	while (it != _finish)
	{
		*(it - 1) = *it;
		++it;
	}
	--_finish;
}

测试

erase的迭代器失效

报错了，为什么？

erase迭代器失效

我们界定erase以后，这个it失效了。为什么？

第一种情况：缩容

如果删除后的数据小于容量capacity的一半，就开始缩容

旧的空间释放掉，导致it变为野指针

第二种情况：越界

如果我们删除5呢。

这里出现了越界（非法访问）。迭代器it也失效了

所以erase it 以后，it就失效。

在vs中不会缩容，那它如何判断的呢？vs下的iterator是一个很复杂的类型，不是一个原生指针实现的

我们可以这样理解，erase  it以后，就把it的类型改了，我们再访问的时候就会报错。 

如何修改呢？

给其一个返回值

我们来删除所有偶数

void test6()
{
	std::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
 
 
	//删除所有偶数
	std::vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			v1.erase(it);
		}
		else
		{
			++it;
		}
	}
	
	for (auto e : v1)
	{
		cout << e << " ";
	}cout << endl;
 
}

程序对不对呢？

当然不对，erase it 一次以后，it就失效了，程序报错。调试一下

删除完2后，it失效，程序报错，如何修改呢？

拷贝构造

我们没有写拷贝构造，编译器会默认生成一个拷贝构造。是浅拷贝，完成的是值的拷贝

void test7()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
 
	vector<int> v2(v1);
	for (auto e : v2)
	{
		cout << e << " ";
	}cout << endl;
}

我们测试一下

会导致析构两次，报错。

我们没有写默认构造，拷贝构造也是构造，构造函数的定义是，只要你写了任意构造，编译器默认就不生成

这里我们强制编译器生成默认构造

//强制编译器生成默认的构造
vector() = default;
 
//拷贝构造v2(v1)，拷贝构造也是构造
vector(const vector& v)
{
	for (auto e : v)
	{
		push_back(e);
	}
}

测试通过

 swap()

void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

operator=

v1 = v3，直接传值传参v就是v3的拷贝构造，v1就是this，tihs和v交换，this不要的数据给v，v出了作用域会析构，写法对于所有深拷贝都适合

//赋值 v1 = v3，v1之前的空间要释放，v1要和v3有一样大的空间一样的值
vector operator=(vector v)//直接传值传参v就是v3的拷贝，
{
	this->swap(v);
	return *this;
}

 测试通过

 迭代器区间初始化

迭代器区间初始化

类模板的成员函数
函数模板，支持任意容器的迭代器初始化

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

迭代器区间初始化可以更好的控制初始化范围。

那么再这里写函数模板到底是为了什么？

任意类型的迭代器都能用。

char和转化为int，类型提升，用的ascii码

n个value值构造函数

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

我们看到val的值为T()，这里是匿名对象，

那val能不能给0呢？答案是不可以的，为什么？

当T的为int时，当然可以；但当T为string呢？T为vector呢？是不是就不行了。

当然，当T()匿名对象的T为int的时候是不是就不对了呢？

这个在C语言中是不对的，但在C++中是正确的。

void test9()
{
	int i = 0;
	int j(1);
	int k = int();
	int x = int(2);
 
}

C++对内置类型进行了升级。C++的内置类型也有了构造，为了兼容模板。

测试

v2初始化为了xxx

当我们再写一个v3初始化为1时，出现编译错误，为什么？

由于此时有两个构造，它会选择更适合自己的模板，所以选择了第一个，*first出现了错误。

如何修改呢？

第一种

在10后面加个u，表示无符号整型

第二种

重载了一个构造函数，size_t修改为int

对于初始化{}

单参数和多参数对象隐式类型转换

	class A
	{
	public:
		A(int a1)
			:_a1(a1)
			, _a2(0)
		{
 
		}
 
		A(int a1,int a2)
			:_a1(a1)
			, _a2(a2)
		{
 
		}
 
	private:
		int _a1;
		int _a2;
	};

单参数和多参数对象隐式类型转换

*****************

单参数用括号，多参数必须用花括号{ }

 
A aa1(1, 1);
A aa2 = { 2,2 };
A aa2{ 2,2 };
const A& aa8 = { 1, 2};
 
A aa3(1);
A aa4 = 1;

const A& aa8 = { 1, 2};

aa8引用的是{1，2}中间产生的临时对象，具有常性

c++11规定单参数也可以用花括号{}来初始化

 
A aa5(1);
A aa6 = { 1 };
A aa7{ 1 };

 结果是一样的，但单参数不建议这样写。

我们来看一下下面代码是不是隐式类型转换

	vector<int> v1 = { 1,2,3,4,5,6 };
	for (auto e : v1)
	{
		cout << e << " ";
	}cout << endl;

这里当然不是，上面描述的有单参数的和两个参数，本质上都去调自己的构造去了。

这里不是隐式类型转换，上面参数固定，这里参数不固定，可以是3个可以是5个等。

为什么会这样呢？

因为c++11里支持initializer_list，新增的一个类型，方便初始化 ，

	vector<int> v1 = { 1,2,3,4,5,6 };

这里的1 ，2  ，3 ，4 ，5 ，6 的类型为initializer_list

它的底层其实是俩指针，一个指向开始，一个指向最后一个数据的下一位，所以这里我们可以用范围for遍历。

vector v2 = {1,2,3,4,5,6} 这里的{1，2，3，4，5，6}类型为initializer_list，生成临时对象，拷贝构造给v2，优化为构造。

我们在这里还需要写一个initializer_list的构造

vector(initializer_list il)
{
	reserve(il.size());
	for (auto e : il)
	{
		push_back(e);
	}
 
}

测试

我们看一下下面这个怎某构造

vector v3 = {  };

知识点

我先把结论告诉你：vector<>里面的数据类型是一个自定义类型时，要考虑深拷贝。

我们看一下代码

	void test11()
	{
		vector v1;
		v1.push_back("11111111111111");
		v1.push_back("11111111111111");
		v1.push_back("11111111111111");
		v1.push_back("11111111111111");
 
		for (auto e : v1)
		{
			cout << e << " ";
		}cout << endl;
 
	}

测试一下

没问题

如果我们再push一次呢

代码出错了，为什么？？？

我们调试一下

空间不够，需要扩容，然后把数据给给tmp，_start释放。而数据拷贝给新空间的时候是浅拷贝，string没有深拷贝

memcpy是一个字节一个字节的拷贝，对任意类型拷贝都是浅拷贝。

tmp指向的还是原来的哪个地址，而_start空间释放了，它的深拷贝没有发生再vector这一层，而是发生在自定义类型存的数据。

如何解决呢？

对_str进行深拷贝，但我们不能访问_str里的数据

我们直接使用赋值来完成工作

void reserve(size_t n)//满了要扩容
{
	if (n > capacity())
	{
		size_t oldsize = size();//oldsize提前存储
		T* tmp = new T[n];//new 开空间 + 初始化
 
		//if (_start)
		//{
		//	memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
		//	delete[] _start;
		//}
		
		if (_start)
		{
			for (size_t i = 0; i < oldsize; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
 
		_start = tmp;
		_finish = tmp + oldsize;
		_end_of_storage = _start + n;
	}
	
}

本集完