【C++】手撕 Vector类

目录

1，vector类框架

2，vector ()

3，pinrt()

4，vector(int n, const T& value = T())

5，vector(const vector& v)

6，vector(InputIterator first, InputIterator last)

7，~vector()

8，iterator begin()

9，iterator end()

10，size() const

11，capacity() const

12，reserve(size_t n)

13，resize(size_t n, const T& value = T())

14，push_back(const T& x)

15，pop_back()

16，insert(iterator pos, const T& x)

17，erase(iterator pos)

18，empty()

19，operator[](size_t pos)

20，operator= (vector v)

21，总结

---

上面我们认识了 vector 类，有了一个大概的理解，下面我们来实现一下 vector 类的框架，来更好的熟悉 vector 类，也让我们对其有着更深的理解； 

1，vector类框架

我们先写一个 vector 类的基本框架；

namespace newVector
{
	template
	class vector
	{
	public:
		// Vector的迭代器是一个原生指针
		typedef T* iterator;
	private:
		iterator _start = nullptr; // 指向数据块的开始
		iterator _finish = nullptr; // 指向有效数据的尾
		iterator _endOfStorage = nullptr; // 指向存储容量的尾
	};
}

vector 类里面是可以包含很多类型的，所以我们用模板来表示，以应用各种场景，vector 类里面多用迭代器的方式来表示，vector 的迭代器其实就是一个原生指针；

_start 指向数据块的开始，_finish 指向有效数据的尾，_endOfStorage 指向存储容量的尾；

2，vector ()

vector()
{}

因为我们在构造框架的时候已经给了缺省值，所以可以不用在写了；

可以看到这里已经初始化了；

3，pinrt()

就是打印输出嘛，方便后续测试；

		void pinrt()
		{
			for (size_t i = 0; i < size(); i++)
			{
				cout << _start[i] << " ";
			}
		}

4，vector(int n, const T& value = T())

我们都会用，初始化 n 个 value；

		vector(int n, const T& value = T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(value);
			}
		}

有人不知道缺省值给个 T（）是什么意思，首先 T（）是匿名对象，默认就是编译器对内置类型的初始化； 

测试一下：

int main()
{
	newVector::vector v1(5, 8);
	v1.pinrt();
	return 0;
}

现在我们不给初始化的值试试：

int main()
{
	newVector::vector v1(5);
	v1.pinrt();
	return 0;
}

 默认初始化为0；

5，vector(const vector& v)

拷贝构造（深拷贝）

		vector(const vector& v)
		{
			reserve(v.capacity());
			//memcpy(_start, v._start, sizeof(T)*v.size());
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
		}

为什么不用 memcpy 呢，上面那个明显要便捷一点，因为 memcpy 是浅拷贝，如果遇到 T是string类的时候就会因为析构函数多次析构同一块空间而报错，而下面这个挨个赋值是深拷贝，他们两个 _start 不会指向同一块空间；

int main()
{
	newVector::vector v1(5,8);
	newVector::vector v2(v1);
	v2.pinrt();
	return 0;
}

可以看到也是 OK 的；

6，vector(InputIterator first, InputIterator last)

这个要配合模板使用，这代表一个范围，只要是同类型的都可以；

		template
		vector(InputIterator first, InputIterator last)
		{
			reserve(last - first + 1);
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

先扩容嘛，像这种区间都是左闭右开的，然后再挨个尾插即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	v1.pinrt();
	return 0;
}

只要是同类型的都可以，像这种的数组都行；

7，~vector()

析构函数

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

delete 后面一定要带 [ ] ，因为析构的是一段连续的空间，就看做是数组即可，然后再将各个迭代器置空即可；

int main()
{
	newVector::vector v1(5,8);
	v1.~vector();
	v1.pinrt();
	return 0;
}

8，iterator begin()

指向第一个元素的迭代器

		iterator begin()
		{
			return _start;
		}

直接返回 _start 即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << *v1.begin();
	return 0;
}

9，iterator end()

指向最后一个元素下一个元素的迭代器

		iterator end()
		{
			return _finish;
		}

直接返回 _finish 即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << *v1.end();
	return 0;
}

直接随机数了；

换个思路，试一下：

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << *(v1.end()-1);
	return 0;
}

我们找他前一个迭代器，果然是最后一个数；

10，size() const

返回有效数据个数

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

直接迭代器相减即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << v1.size();
	return 0;
}

11，capacity() const

返回容量大小

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

直接迭代器相减即可，差值就是容量大小；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << v1.capacity();
	return 0;
}

12，reserve(size_t n)

扩容

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old = size();
				if (_start)
				{
					//memcpy(tmp, _start, old * sizeof(T));
					for (size_t i = 0; i < old; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + old;
				_endOfStorage = _start + n;
			}
		}

当要扩容时才用的着，先判断，然后开辟一段需要的空间，之后就是拷贝赋值了，这里我们还是没有用 memcpy 因为是浅拷贝，然后再释放原空间，再将迭代器重新赋值即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << v1.capacity() << endl;
	v1.reserve(20);
	cout << v1.capacity() << endl;
	return 0;
}

一目了然；

13，resize(size_t n, const T& value = T())

更改有效数据个数，不够则填充，可以指定填充数据；

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

当缩减数据时直接把 _finish 往前移即可，当扩容时先扩容，然后进行填充；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr,arr+5);
	cout << v1.size() << endl;
	v1.resize(10);
	cout << v1.size() << endl;
	v1.resize(15, 6);
	cout << v1.size() << endl;
	v1.pinrt();
	return 0;
}

可以看到，当我们不指定填充时默认填充0；

14，push_back(const T& x)

尾插

		void push_back(const T& x)
		{
			if (_finish == _endOfStorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;
			_finish++;
		}

首先要检查是否需要扩容，然后赋值，将 _finish 往后移一位即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	
	v1.push_back(6);
	v1.push_back(7);
	v1.pinrt();
	return 0;
}

 插入十分成功；

15，pop_back()

尾删

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

像这种数组类型的，直接对其迭代器动手就行，直接 _finish 往前移一位即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	
	v1.pop_back();
	v1.pop_back();
	v1.pinrt();
	return 0;
}

删除非常顺利；

16，insert(iterator pos, const T& x)

指定位置插入

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			size_t old = pos - _start;
			if (_finish == _endOfStorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			pos = _start + old;
			memcpy(pos + 1, pos, (_finish - pos) * sizeof(T));
			*pos = x;
			_finish++;
			return pos;
		}

这里会面临一个迭代器失效的问题，当扩容后，原本的 pos 还是指向旧空间就失效了，所以我们要更新 pos ；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	
	auto pos = find(v1.begin(), v1.end(), 1);
	v1.insert(pos, 9);
	pos= find(v1.begin(), v1.end(), 5);
	v1.insert(pos, 9);
	v1.pinrt();
	return 0;
}

完美插入；

17，erase(iterator pos)

擦除指定位置

		iterator erase(iterator pos)
		{
			assert(pos >= 0 && pos <= _finish);
			memcpy(pos, pos + 1, sizeof(T)*(_finish - pos));
			_finish--;
			return pos;
		}

先断言判断，然后直接往前移一位覆盖即可，再更新一下 _finish ;

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	auto pos = find(v1.begin(), v1.end(), 1);
	v1.erase(pos);
	pos = find(v1.begin(), v1.end(), 5);
	v1.erase(pos);
	v1.pinrt();
	return 0;
}

也是成功擦除了；

18，empty()

判空

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

当为空时返回真，反之亦然；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	cout << v1.empty() << endl;
	newVector::vector v2;
	cout << v2.empty();
	return 0;
}

19，operator[](size_t pos)

返回下标对应的值；

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

直接像数组一样取值返回即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	
	cout << v1[0] << " " << v1[4];
	return 0;
}

写法也是跟数组一样简单；

20，operator= (vector v)

赋值，深拷贝

		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endOfStorage, v._endOfStorage);
		}
		vector& operator= (vector v)
		{
			swap(v);
			return *this;
		}

直接一手交换即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector v1(arr, arr + 5);
	
	newVector::vector v2 = v1;
	v2.pinrt();
	return 0;
}

 

21，总结

我们就先搞一个大概的，其中还有很多分支，比如我们写的是擦除某个数据，其实也可以擦除某个范围，这些就靠大家去摸索，查阅文档了；

vector类的实现就到这里了；

加油！