【C++】vector的模拟实现（SGI版本）

namespace wyn
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
               ……
               ……
       private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{}

template<class InputIterator>
vector(InputIterator first, InputIterator last)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first < last)
	{
		push_back(*first);
		first++;
	}
}

//vector<int> v1(10, 1);
//1.两个都是int，则v1优先匹配的是两个参数均为同类型的模板class InputIterator，不会是下面的构造，因为10需要进行隐式类型转换
//1也需要进行类模板的显示实例化，优先级并没有同类型参数的函数模板高，函数模板只需要一次推导参数类型即可匹配成功。
//2.但是如果匹配了函数模板，则解引用int类型就会发生错误，非法的间接寻址。
// 
//vector<char> v1(10, 'A');一个是int一个是char，没有选择，只能选择下面的构造函数进行v1的构造。

//所以可以将构造函数的第一个参数类型改为int，但库在实现的时候，默认用的就是size_t，我们改成int就不太好。
//那该怎么办呢？答案就是看源代码。利用重载构造解决问题。
vector(size_t n, const T& val = T())//引用和指针在赋值时，有可能出现权限问题。这里需要用常量引用，否则无法接收常量值。
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);
	while (n--)
	{
		push_back(val);
	}
}
vector(int n, const T& val = T())//引用和指针在赋值时，有可能出现权限问题。这里需要用常量引用，否则无法接收常量值。
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);
	while (n--)
	{
		push_back(val);
	}
}
void test_vector8()
{
	std::string s("hello world");
	vector<int> v(s.begin(), s.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//vector<int> v1(10, 1);//报错非法的间接寻址
	vector<char> v1(10, 'A');//这样的情况都不会出现问题，但是这样的情况，构造函数第二个参数需要加const修饰，以免权限放大
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	//编译错误：注释代码排除寻找出现问题的代码部分
	//运行错误：进行调试
}

vector& swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);

	return *this;
}
// v2(v1)---v1拷贝构造v2
vector(vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//1.普通的传统写法就是开空间和拷贝数据
	//_start = new T[v.capacity()];
	//2.进阶的传统写法
	reserve(v.capacity());
	for (auto& e : v)
	//遍历v，将遍历所得的迭代器里面的值依次赋值给e，如果T是自定义类型，这里会发生多次的拷贝构造，所以最好加引用。
	{
		push_back(e);
	}
}
vector(const vector<T>& v)//打工人依旧是带参数的构造函数
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	//string时候的拷贝构造调用的是带参的构造函数，依次来创建出tmp，构造函数就是打工人
	vector<T> tmp(v.begin(), v.end());
	swap(tmp);//交换的时候就可以体现出拷贝构造函数初始化列表的好处了。
}

// v1 = v2;
// v1 = v1;//极少数情况才会出现自己给自己赋值，况且自己给自己赋值也不报错，所以我们容忍这种情况的出现。
vector<T>& operator=(vector<T> v)//返回引用，符合连续赋值的含义
{
	swap(v);
	return *this;
}

//迭代器失效：野指针问题
void insert(iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos < _finish);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;//记录一下原空间pos和_start的相对位置。
		size_t new_capacity = capacity() == 0 ? 4 : 2 * capacity();
		//扩容导致了迭代器pos失效，因为进行了异地扩容，pos位置指向的是已释放空间的迭代器
		reserve(new_capacity);
		pos = _start + len;
		//所以如果发生扩容，则需要更新pos的位置
	}
	//挪动数据，对于vector来说，就不存在pos等于0时的越界问题，但没有下标的问题，又会产生指针的问题
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = val;
	++_finish;
}
void test_vector4()//测试迭代器失效
{
	string s;
	vector<int> v;
	//v.reserve(10);//如果提前开辟好空间，就不会产生迭代器失效的问题。实际就是因为异地扩容导致的迭代器失效
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator it = find(v.begin(), v.end(), 3);
	if (it != v.end())
	{
		v.insert(it, 30);
	}
	//insert以后，it不能继续使用，因为迭代器可能失效（野指针），虽然在insert内解决了迭代器失效的问题，但那只是修改了内部的pos
	//it是外部的，依旧不可以使用，传值传递，外部的问题依旧没有被解决。
	(*it)++;//这里一定是一个野指针，因为发生了异地扩容，it指向的是旧空间的位置，但野指针的访问并没有被编译器报错，这很危险。
	//所以一定要小心对于野指针的使用，如果it指向的旧空间被分配给某些十分关键的金融数据，则野指针访问会修改这些关键数据，非常危险
	//如果野指针的使用影响到其他的进程就完蛋了，公司里出现这样的问题直接废球了。

	//1.为什么不用传引用来解决这里的问题呢？因为对于地址这样的常量不能作为变量进行传递，无法从int*转换为int*&
	//2.所以在insert之后不要继续使用it，因为他很有可能失效，就算在vs上不失效，但你能保证在其他平台下也不失效吗？比如g++呢？
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator begin = pos + 1;
	while (begin < _finish)
	{
		*(begin - 1) = *(begin);
		begin++;
	}
	--_finish;

	return pos;
}
void test_vector5()//测试迭代器失效
{
	
	std::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	// it是失效还是不失效呢？
	std::vector<int>::iterator it = find(v.begin(), v.end(), 3);
	if (it != v.end())
	{
		v.erase(it);
	}
	//读
	cout << *it << endl;//PJ版实现的非常复杂，相对于SGI版本。能够检查出来越界访问
	//写
	//++(*it);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector6()//这里我们用自己实现的erase来更新失效之后的迭代器
{
	// 要求删除所有的偶数
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(9);
	
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);
			//所以正确的使用方式就是利用erase的返回值进行迭代器的使用，这样不管你怎么用，迭代器都不会失效。
			//因为在erase之后我们统一认为迭代器it失效了，所以需要erase的返回值来更新迭代器，代码在VS和g++下面都可以跑。
		}
		//it++;//更新迭代器之后，不要继续it++了，因为erase的返回值已经帮你把it挪到下一个元素的位置了，所以你就不要再++了，
		else
		{
			++it;
		}
		//vs结果还是一样的，erase之后it++，vs认为迭代器失效。所以不要尝试使用erase之后的迭代器。
		//统一认为erase之后的迭代器失效。
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}
//insert扩容迭代器失效和erase后统一认为迭代器失效。如果想用，那就不要去直接访问迭代器，而是利用返回值更新一下迭代器。

~vector()
{
	delete[] _start;
	_start = _end_of_storage = _finish = nullptr;
}
void reserve(size_t n)
{
	if (n > capacity())//只进行扩容
	{
		size_t oldsize = size();
		T* tmp = new T[n];//不需要检查new失败，因为C++new失败直接抛异常
		if (_start)//空对象扩容时，_start是nullptr，没必要拷贝数据
		{
			//memcpy(tmp, _start, sizeof(T) * size());
			//如果是自定义类型，则浅拷贝后的同一空间释放两次，势必会造成野指针使用问题的出现
			//仅仅只发生vector<int>对象数组的深拷贝是不行的，还需要进行其中每个对象的深拷贝，则需要深层次的深拷贝。

			for (size_t i = 0; i < oldsize; ++i)
			{
				tmp[i] = _start[i];//这里直接调用赋值重载，赋值重载会帮助我们进行对象数组元素的深拷贝
			}
			delete[]_start;
		}
		/*_start = tmp;
		_finish = _start + size();*///如果是空对象，则_finish没改变为空，而start变为tmp的首元素地址了。
		_start = tmp;
		_finish = tmp + oldsize;
		_end_of_storage = _start + n;
	}
}
void resize(size_t n,T val = T())//如果是自定义类型，则将自定义类型的对象先进行初始化，然后在插到vector里面。
{
	if (n > capacity())
	{
		reserve(n);
		while (_finish < _start + n)//要小心这里的条件控制，_finish不能等于_start+n，否则发生越界访问。
		{
			*_finish = val;//如果T是自定义类型，则这里发生赋值重载
			++_finish;
		}
	}
	else
	{
		_finish = _start + n;
	}
}
void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		size_t new_capacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(new_capacity);
	}

	*_finish = x;
	++_finish;
}
void test_vector9()//这里涉及很深的深拷贝问题。
{
	vector<vector<int>> vv;
	vector<int> v(10, 1);
	vv.push_back(v);//第一次是开空间，然后存放数据，并不存在拷贝数据的情况。
	vv.push_back(v);
	vv.push_back(v);
	vv.push_back(v);
	vv.push_back(v);//这个地方会挂，挂在扩容，问题出在拷贝数据上面。

	for (size_t i = 0; i < vv.size(); ++i)
	{
		for (size_t j = 0; j < vv[i].size(); ++j)
		{
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;


	vector<vector<int>> vvret = Solution().generate(5);
	//非静态成员函数的调用必须与某个特定对象相对。1.搞成静态就可以解决了。2.或者利用匿名对象调用非静态成员函数
	//这里出现问题的原因还是因为reserve里的memcpy浅拷贝，因为拷贝构造利用的打工人是迭代器区间为参的构造函数，依旧绕不开
	//push_back和reserve，那么一旦出现对象数组的拷贝构造时，reserve里面的memcpy就会造成野指针问题。
	for (size_t i = 0; i < vvret.size(); i++)
	{
		for (size_t j = 0; j < vvret[i].size(); j++)
		{
			cout << vvret[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
const_iterator begin()const
{
	return _start;
}
const_iterator end()const
{
	return _finish;
}
T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];//把_start当成数组玩就行。解引用比较麻烦
}
const T& operator[](size_t pos)const
{
	assert(pos < size());
	return _start[pos];//把_start当成数组玩就行。解引用比较麻烦
}
size_t size()const//const和非const对象都能调
{
	return _finish - _start;
	//左闭右开的差正好就是这个区间内的元素个数，[0,10)是正好10个元素，左闭右闭算的是间隔数，如果算元素个数还得+1
}
size_t capacity()const
{
	return _end_of_storage - _start;
}
bool empty()const
{
	return _start == _finish;
}
void pop_back()
{
	assert(!empty());//判断为假就报错。
	--_finish;
}