C++ STL --- vector类模拟实现

        下面这幅图就是验证图。

        S对象内存储的是指针，构造Vector时里面有两个S类型的元素，两个s元素中分别有一个指针指向一个有"\0"元素的空间。然后尾插一个元素，导致扩容。

        扩容后使用memcpy按字节将vector中的元素拷贝到新空间中。一切看起来都那么完美。可是旧的vector对象中地址指针(蓝色的地址线)需要释放，释放后新空间中的指针(红色地址线)却依然指向被释放的空间。这不就是野指针吗？这样一来，一旦试图访问这块空间，必然程序崩溃。

  (5)设置有效元素个数

        这里要告诉大家，不要使用memset函数。因为memset函数也是按字节将元素直接放到指定空间中。C 库函数 void *memset(void *str, int c, size_t n) 复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。

        字符的字节是1字节，如果你要用它放n个T类型数据到指向的空间，它是怎么做的？它会把T类型的数据往空间中的前n个字节，每个字节都放一个！

        代码十四：

//代码十四：
void Resize(size_t newSize, const T& val = T()) {
	size_t oldCapacity = Capacity();
	size_t oldSize = Size();
	//要设置的有效元素个数大于现在的有效元素
	if (newSize > oldSize) {
		//要设置的有效元素个数大于现有空间，扩容
		if (newSize > oldCapacity) {
			Reserve(newSize);
		}
		//思考：memeset可以用吗？
		for (size_t i = oldSize; i < newSize; i++) {
			_start[i] = val;
		}
	}
	_finish = _start + newSize;
}

4.元素访问模块

  (1)获取首元素

        代码十五：这里给出两种类型，以便于const对象使用。

//代码十五
T& Front() {
	return _start[0];
}
const T& Front()const {
	return _start[0];
}

  (2)获取尾元素

        代码十六：两种类型，道理同上。

//代码十六
T& Back() {
	return *(_finish - 1);
}
const T& Back()const {
	return *(_finish - 1);
}

  (3)重载[]

        代码十七：也是两种类型。注意assert函数使用时需要包含头文件。

//代码十七
#include 
T& operator[](size_t index) {
	//需要判断是否越界
	assert(-1Size());
	return _start[index];
}
const T& operator[](size_t index)const {
	assert(-1Size());
	return _start[index];
}

5.修改模块

  (1)尾插

        代码十八：尾插可能需要扩容，一旦扩容，就给的空间大一点，尽量减少扩容次数。

//代码十八
void Push_back(const T& val) {
	//判断顺序表是否已经存满了
	if (_finish == _end) {
		Reserve(Capacity() * 2);
	}
	*_finish = val;
	_finish++;
}

  (2)尾删

        代码十九：

//代码十九
void Pop_back() {
	if (Empty()) {
		return;
	}
	_finish--;
}

  (3)任意位置插入   

        代码二十：  需要考虑越界问题

//代码二十
iterators Insert(iterators index, const T& val) {
	//判断迭代器是否越界
	if (index < _start || index > _finish)
		return End();
	//判断空间是否存满
	if (_start == _finish)
		Reserve(Capacity() * 2);
 
	auto it = _finish;
	while (it != index) {
		*it = *(it - 1);
		it--;
	}
	*index = val;
	_finish++;
	return index;
}

  (4)指定位置删除

        代码二十一：需要考虑越界问题

//代码二十一
iterators Erase(iterators index) {
	//判断迭代器是否越界
	if (index < _start || index > _finish)
		return End();
	auto it = index;
	//将index后的元素往前搬移一位
	while (it != _finish) {
		*it = *(it + 1);
		it++;
	}
	_finish--;
	return index;
}

  (5)清空有效元素

        代码二十二：

//代码二十二
void Clear() {
	_finish = _start;
}

6.总体代码

        将代码进行调整后改成整体代码如下：

#include 
#include "iostream"
using namespace std;
 
//Vector类存储的数据是任意类型，所以需要设置模板参数
template<typename T> 
class Vector {
private:
	T* _start;//指向T类型元素的首元素的指针
	T* _finish;//指向最后一个有效元素下一个位置
	T* _end;//指向有效空间的下一个位置。
public:
//构造模块
//
	//无参构造
	Vector() 
		:_start(nullptr)
		,_finish(nullptr)
		,_end(nullptr)
	{}
	//半缺省构造
	Vector(int n, const T& val = T())
		:_start(new T[n])//在初始化时直接从堆上申请空间
	{
		for (int i = 0; i < n; i++) {
			_start[i] = val;
		}
		//_finish指向最后一个有效元素的下一个位置
		_finish = _start + n;
		//_end指向顺序表最后一个位置的下一个位置
		_end = _finish;
	}
	//区间构造
	template<typename Iterator>
	Vector(Iterator first, Iterator last) {
		Iterator it = first;
		size_t num = 0;//统计元素个数
		while (it != last) {
			num++;
			it++;
		}
 
		_start = new T[num];
		_finish = _start;
		while (first != last) {
			*_finish = *first;
			_finish++;
			first++;
		}
		_end = _finish;
	}
	//拷贝构造函数
	Vector(const Vector& v)
		:_start(new T[v.Size()]) //这里用到的Size函数后面会实现的
	{
		size_t num = v.Size();
		for (size_t i = 0; i < num; i++) {
			_start[i] = v._start[i];
		}
		//让对应的指针指向应该指向的位置
		_finish = _start + num;
		_end = _finish;
	}
	//赋值运算符重载
	Vector& operator=(const Vector v) {
		std::swap(_start, v._start);
		std::swap(_finish, v._finish);
		std::swap(_end, v._end);
		return *this;
	}
	//析构函数
	~Vector() {
		if (_start) {
			delete[] _start;
		}
		_start = _finish = _end = nullptr;
	}
//迭代器模块
//
	typedef T* iterators;
	//正向迭代器 
	iterators Begin() {
		return _start;
	}
	iterators End() {
		return _finish;
	}
	
	//反向迭代器
	iterators Rbegin() {
		return End();
	}
	iterators Rend() {
		return Begin();
	}
//容量模块
//
	//有效元素个数
	size_t Size() const{
		return _finish - _start;
	}
	//容量大小
	size_t Capacity()const {
		return _end - _start;
	}
	//判空函数
	bool Empty()const {
		return _start == _finish;
	}
	//扩容函数
	void Reserve(size_t newCapacity) {
		size_t oldCapacity = Capacity();
		size_t oldSize = Size();
 
		T* temp = new T[newCapacity];
		//当要设置的新空间大于旧空间
		if (newCapacity > oldCapacity) {
			//判断首指针是否是空
			if (_start) {
				//进行深拷贝
				//思考：memcpy可以使用吗？
				for (size_t i = 0; i < oldSize; i++) {
					temp[i] = _start[i];
				}
				//释放旧空间
				delete[] _start;
			}
			_start = temp;
			_finish = _start + oldSize;
			_end = _start + newCapacity;
		}	
	}
	//设置有效元素函数
	void Resize(size_t newSize, const T& val = T()) {
		size_t oldCapacity = Capacity();
		size_t oldSize = Size();
		//要设置的有效元素个数大于现在的有效元素
		if (newSize > oldSize) {
			//要设置的有效元素个数大于现有空间，扩容
			if (newSize > oldCapacity) {
				Reserve(newSize);
			}
			//思考：memeset可以用吗？
			for (size_t i = oldSize; i < newSize; i++) {
				_start[i] = val;
			}
		}
		_finish = _start + newSize;
	}
//元素访问模块
//
	//获取首元素
	T& Front() {
		return _start[0];
	}
	const T& Front()const {
		return _start[0];
	}
	//获取尾部元素
	T& Back() {
		return *(_finish - 1);
	}
	const T& Back()const {
		return *(_finish - 1);
	}
	//重载[]
	T& operator[](size_t index) {
		//需要判断是否越界
		assert(-1Size());
		return _start[index];
	}
	const T& operator[](size_t index)const {
		assert(-1Size());
		return _start[index];
	}
//修改模块
//
	//尾插
	void Push_back(const T& val) {
		//判断顺序表是否已经存满了
		if (_finish == _end) {
			Reserve(Capacity() * 2);
		}
		*_finish = val;
		_finish++;
	}
	//尾删
	void Pop_back() {
		if (Empty()) {
			return;
		}
		_finish--;
	}
	//任意位置的插入
	iterators Insert(iterators index, const T& val) {
		//判断迭代器是否越界
		if (index < _start || index > _finish)
			return End();
		//判断空间是否存满
		if (_start == _finish)
			Reserve(Capacity() * 2);
 
		auto it = _finish;
		while (it != index) {
			*it = *(it - 1);
			it--;
		}
		*index = val;
		_finish++;
		return index;
	}
	//任意位置删除
	iterators Erase(iterators index) {
		//判断迭代器是否越界
		if (index < _start || index > _finish)
			return End();
		auto it = index;
		//将index后的元素往前搬移一位
		while (it != _finish) {
			*it = *(it + 1);
			it++;
		}
		_finish--;
		return index;
	}
	//清空有效元素
	void Clear() {
		_finish = _start;
	}
};
 
int main() {
	Vector<int> v(10, 5);
	v.Push_back(9);
	v.Erase(v.End());
}