c++ vector模拟实现

一、vector是什么？

vector是表示可变大小数组的序列容器，它也采用连续存储空间来存储元素，因此可以采用下标对vector的元素进行访问，它的大小是动态改变的，vector使用动态分配数组来存储它的元素；

二、容器特性

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;

2.动态数组

支持对序列中的任意元素进行快速直接访问，甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;

3.能够感知内存分配器的

容器使用一个内存分配器对象来动态地处理它的存储需求;

三、vector的模拟实现

• 定义一个类：

template<class T>
class Vector
{
	T* _start; //首元素地址
	T* _finish; //最后一个元素地址的下一个地址
	T* _endOfStorage; //空间的尾地址
public：
//成员函数
};

• 构造函数

Vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{}
 
Vector(size_t n, const T& value = T())
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	reserve(n);
	while (n--)
	{
		push_back(value);
	}
}
Vector(InputInterator first, InputInterator last)
		:_start(nullptr)
		, _finish(nullptr)
		, _endOfStorage(nullptr)
	{
		while (first != last)
		{
			pushBack(*first);
			++first;
		}
	}

• 数据大小、空间大小

size_t size() const
{
	return _finish - _start;
}
 
size_t capacity() const
{
	return _endOfStorage - _start;
}

• 尾插

void pushBack(const T& value)
	{
		if (_finish == _endOfStorage)
		{
			size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
			reverse(value);
		}
		*_finish = value;	
		++_finish;
	}

• 扩容

有资源进行拷贝时，使用深拷贝；类型为自定义类型时，发生浅拷贝，调用自定义类型析构函数，释放资源，导致资源二次释放，所以自定义类型的拷贝有资源时进行深拷贝；

深浅拷贝的区别以及应用
https://blog.csdn.net/weixin_52270223/article/details/115605455

void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t sz = size();
			T* arr = new T[n];
			if (_start)
			{
				memcpy(arr, _start, sizeof(T) * sz);
				delete[] _start;
			}
			//update
			_start = arr;
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}
	}

• 改变数据大小

void resize(size_t n, const T& val = T())
	{
		if (n > capacity())
		{
			reserve(n);
		}
		else if (n > size())
		{
			while (_finish != _start + n)
			{
				*_finish = val;
				_finish++;
			}
		}
			_finish = _start + n;
	}

• 位置插入值

void insert(iterator pos, const T& val)
	{
		size_t sz = pos - _start;
		//检查位置
		if (pos >= _start && pos <= _finish)
		{
			//检查容量
			if (_finish == _endOfStoage)
			{
				size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();				
				reserve(n);
				//更新迭代器
				pos = _start + sz;
			}
			//移动元素
			iterator end_u = _finish;
			while (end_u != pos)
			{
				*end = *(end_u - 1);
				--end_u();
			}
			//插入元素
			*pos = val;
			//更新位置
			++_finish;
		}
	}

• 删除数据

iterator erase(iterator pos)
	{
		//检查位置
		if (pos < _finish && pos >= _start)
		{
			//移动元素
			iterator start = pos + 1;
			while (start!=_finish)
			{
				*(start - 1) = *start;
				start++;
			}
			//更新
			--_finish;
		}
		return pos;
	}
	//返回删除数据的下一个元素的位置

• operator[] 重载

T& operator[](size_t pos)
	{
		if (pos >= 0 && pos < size())
			return _start[pos];
	}

• operator= 重载

	Vector<T>& operator=(const Vector<T>& v)
	{
		if (this != &v)
		{
			delete[]_start;
			size_t n = v.capacity();
			_start = new T[n];
			for (size_t i = 0; i < v.capacity(); ++i)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_finish = _start + n;
		}
		return *this;
	}

• 迭代器

//vector迭代器：T*
typedef T* iterator;
typedef const T* const_iterator;
 
iterator begin()
{
	return _start;
}
 
iterator end()
{
	return _finish;
}
 
const_iterator begin() const
{
	return _start;
}
 
const_iterator end() const
{
	return _finish;
}

• 析构函数

~Vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finish = _endOfStorage = nullptr;
	}
}