C++系列-Vector的模拟实现

🌈个人主页：羽晨同学 

💫个人格言:“成为自己未来的主人~”   

类模版的使用

在实现Vector（顺序表）的过程中，我们为了保证顺序表对于所有类型数据的普遍使用性，所以，我们将定义一个类模板和类，以保证Vector可以用于各种类型的数据。

template<class T>
	class vector

然后接下来，我们实现一个对于最终要的一个部分，迭代器的部分

迭代器的实现

	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		const_iterator begin() const
		{
			return _start;
		}
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator end() const
		{
			return  _finish;
		}

析构函数的实现

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

若开始不为空，那么删除那一块空间，并且将所有自定义变量设置为0

空间开辟部分功能的实现

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];
				if (_start)
				{
					memcpy(tmp, _start, sizeof(T) * size());
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_end_of_storage = _start + n;
			}
		}
		size_t capacity()
		{
			return _end_of_storage - _start;
		}
		size_t size()
		{
			return _finish - _start;
		}

这里其实有一个需要注意的点，那个oldsize的使用 ，对于下面的标识符更新而言，如果没有oldsize，那么删除原先空间的时候，便会把size()删除，那么_finish便会无法得到更新，所以我们选择将size存在oldsize里面，便于标识符的更新。

下标索引和插入功能的实现

		T& operator[](size_t i)
		{
			assert(i < size());
			return _start[i];
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}

这里其实复用了其他的函数，比如insert，比如[]

删除功能的实现

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

insert功能的实现

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

			return pos;
		}

在这个insert功能实现当中，我们先对空间进行判断，若是没有多余空间进行插入，则我们需要重新拓展空间，然后重新定位Pos位置，然后将插入位置之后的数据往后移动一位，插入数值。

删除目标位置

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

测试1

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

 测试2

void test_vector2()
{
	bit::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	v1.insert(v1.begin(), 0);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	v1.erase(v1.begin());
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	int x;
	cin >> x;
	bit::vector<int>::iterator it = find(v1.begin(),v1.end(),x);
	if (it != v1.end())
	{
		it=v1.insert(it, 1000);
		cout << *it << endl;
	}
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

}