C++之模拟实现vector

摘星

发布于 2023-04-28 09:06:10

3190

发布于 2023-04-28 09:06:10

文章被收录于专栏：C/C++学习

前言

因为学习了vector的相关知识，了解了vector大部分接口的底层实现原理，所以我决定自己模拟实现一个mini版的vector类，用来加深对vector各方面知识的理解。如果有错误或不足之处，还望各位读者小伙伴们指出。

一、包含的相关头文件

#include<iostream>
#include<assert.h>
#include<vector>//要使用vector类，要记得包含这个头文件
using namespace std;

二、构造和析构

1.构造函数

1.无参

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

2.n个T型元素进行初始化

1.普通

		vector(size_t n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			//for (size_t i = 0; i < n; ++i)
			//{
			//	push_back(value);
			//}
			while (n--)
			{
				push_back(value);
			}
		}

2.特殊

因为，编译器会匹配最优匹配的函数进行调用。为了避免将用n个Int型元素构造一个vector型的对象的函数调用匹配到下面的用T类型的迭代器初始化vector型的对象的构造函数（会发生错误的间接寻址），我们就得重载一个用n个Int数据初始化vector的构造函数

		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

3.T型迭代器

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

2.拷贝构造

现代写法的优点在模拟实现string中已经介绍过，此处不再赘述。

		//拷贝构造(现代写法)
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			vector<T> temp(v.begin(), v.end());
			Swap(temp);
		}

自己实现的Swap可以避免深拷贝，提高效率

		void Swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endOfStorage, v._endOfStorage);
		}

3.赋值运算符重载

		//赋值运算符重载
		vector<T>& operator= (vector<T> v)
		{
			Swap(v);
			return *this;
		}

4.析构函数

		//析构
		~vector()
		{
			delete[] _start;
			_start = _finish = _endOfStorage = nullptr;
		}

三、iterator

Vector的迭代器是一个原生指针

		typedef T* iterator;
		typedef const T* const_iterator;

1.普通对象

返回迭代器

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

2.const对象

返回const迭代器

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

四、modify

1.push_back

尾插

		void push_back(const T& x)
		{
			if (_finish == _endOfStorage)//插入前要判断空间是否满了
			{
				size_t newcapacity = (capacity() == 0) ? 4 : 2 * capacity();//要坚持是否第一次扩容
				reserve(newcapacity);
			}
			*_finish = x;
			_finish++;
		}

2.pop_back

尾删

		void pop_back()
		{
			assert(!empty());//如果空间中没有元素就不能再尾删了
			_finish--;
		}

3.insert（含迭代器失效问题）

某个位置插入元素 这里有一个迭代器失效的问题，要小心处理

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			//assert(pos < _finish);
			assert(pos <= _finish);
			if (_finish == _endOfStorage)//如果插入操作进行了扩容，则原pos指针会失效（异地扩容会改变地址）
			{
				size_t len = pos - _start;
				size_t newcapacity = (capacity() == 0) ? 4 : 2 * capacity();
				reserve(newcapacity);
				//更新pos
				pos = _start + len;
			}
			iterator end = _finish;//挪动元素
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = x;//插入元素
			_finish++;
			return pos;//pos是传值传参，因此函数内pos的更新不会使函数外的pos被更新（即，函数外的pos仍然失效）因此为了继续在函数外使用pos，我们把更新后的pos作为返回值传回去，更新函数外的pos
		}

具体如何处理下文的测试函数部分有介绍。

4.erase（含迭代器失效问题）

某位置删除一个元素 此处的迭代器意义发生改变，即迭代器失效

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			//iterator begin = pos + 1;
			//while (begin < _finish)
			//{
			//	*(begin - 1) = *begin;
			//	begin++;
			//}
			iterator begin = pos;
			while (begin < _finish - 1)
			{
				*begin = *(begin + 1);
				begin++;
			}
			--_finish;
			return pos;
		}

具体如何处理下文的测试函数部分有介绍。

5.clear

		void clear()
		{
			_finish = _start;
		}

五、capacity

1.size

容器的元素个数

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

2.capacity

容器的容量

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

3.empty

判空函数

		bool empty()
		{
			return _start == _finish;
		}

4.resize

改变元素个数

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

5.reserve

改变容量

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* temp = new T[n];
				if (_start)
				{
					//memcpy(temp, _start, sizeof(T)* len);
					//这里不能使用memcpy，因为它进行的是浅拷贝，会导致原空间与新空间的内容指向同一空间，当原空间被销毁时，析构函数会将它所指的空间也销毁，导致新空间指向为野指针，导致程序崩溃
					for (size_t i = 0; i < oldsize; ++i)//只能一个元素一个元素的赋值（赋值运算符重载进行深拷贝）
					{
						temp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = temp;
				_finish = _start + oldsize;
				_endOfStorage = _start + n;
			}
		}

六、access

1.普通对象的接口（可读可写）

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

2.const对象的接口（只读）

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

七、私有属性

	private:
		iterator _start; // 指向数据块的开始
		iterator _finish; // 指向有效数据的尾
		iterator _endOfStorage; // 指向存储容量的尾

八、测试

主函数：

//test.cpp
#include"vector.h"
int main()
{
	//Jinger::Test1();
	//Jinger::Test2();
	//Jinger::Test3();
	//Jinger::Test4();
	Jinger::Test5();
	return 0;

测试：

	void Test1()
	{
		vector<int> v;
		v.resize(10, -1);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

运行结果：

	void Test2()
	{
		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(4);
		vector<int>::iterator it = find(v.begin(), v.end(), 3);
		if (it != v.end())
		{
			it = v.insert(it, 30);
		}
		// insert以后 it还能否继续使用 -- 不能，可能发生扩容导致迭代器失效（野指针）
		//如果要继续使用it就需要对it进行更新，insert函数的返回值就是更新后的it值。
		(*it)++;
		*it *= 100;
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void Test3()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		// it失效还是不失效？ ——失效，因为it位置的内容被删除，所有it的含义被改变了（此时，it会指向被删除元素的下一个元素)
		vector<int>::iterator it = find(v.begin(), v.end(), 4);
		if (it != v.end())
		{
			v.erase(it);
		}
		// 读 
		cout << *it << endl;
		// 写
		(*it)++;
		cout << *it << endl;
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	//erase操作会导致it迭代器失效。再次使用时要进行更新它（erase函数的返回值就是更新后的it迭代器，此时它指向刚刚被删除元素的下一个元素)
	//虽然部分编译器（linux的g++下不报错）中erase后的迭代器还能继续使用，但不能保证所有编译器下它都不报错，因此我们同意认为erase后的迭代器会失效，如果再次使用它必须要更新它
	void Test4()
	{
		// 要求删除所有偶数
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(4);
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				it++;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void Test5()
	{
		vector<vector<int>> vv;
		vector<int> v(5, 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;
	}