vector的简单模拟

 本编文章对 vector 进行简单的模拟实现，了解 vector 的基本原理，简单实现 vector

目录

vector 是什么？

vector 的简单使用

初始化

三种遍历

扩容--reserve

扩容--resize

缩容--shrink_to_fit

insert--指定位置插入

erase--指定位置删除

find--查找

sort--排序

模拟实现

基本成员

迭代区间构造

拷贝构造和赋值重载

指定初始化的个数和参数

begin 和 end

size 和 capacity

reserve--开辟空间不初始化

解决野指针问题

解决深浅拷贝问题

insert--指定插入

erase--指定删除

尾插和尾删

[] 重载

---

vector 是什么？

vector 是表示大小可以更改的数组的序列容器。我们理解为它相当于数组的封装。

vector 的简单使用

初始化

vector 相当于类型名，而 vector 中存储的类型通常用 vector<类型> 来描述

三种遍历

下标、迭代器、范围for

扩容--reserve

reserve 提前开辟好空间，避免空间不足时频繁扩容，不会初始化

扩容--resize

提前开辟好空间，会自动初始化

没有指定的初始化数据时，会根据数据的类型自动生成默认值：

缩容--shrink_to_fit

将容量调整到和size相等--少用慎用

insert--指定位置插入

insert（指定位置迭代器，插入的值）

erase--指定位置删除

find--查找

查找指定的数据，返回对应位置的迭代器，支持修改。需要用到算法头文件 algorithm

sort--排序

用到仿函数--头文件functional

模拟实现

vector 相当于一个数组容器，存储的数据类型不定，因此使用模板参数来确定 vector 的类型，参考源码对迭代器进行封装，完成对 vector 的简单模拟。

基本成员

_start 是 vector 起始位置的指针

_finish 是 vector 最后一个数据下一个位置的指针

_endofstoage 是 vector 容量末尾下一个位置的指针

namespace myvector
{
    template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
 
        //构造函数
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{}
 
 
        //析构函数
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstoage = nullptr;
			}
		}
 
	private:
		iterator _start;
		iterator _finish;
		iterator _endofstoage;
	};
}

迭代区间构造

使用的是时候，我们了解到可以传递迭代器区间进行初始化，但是不确定是什么类型的迭代器，在这里可以用模板参数来代替具体的迭代器类型。

        //带参构造
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

拷贝构造和赋值重载

用现代写法来进行拷贝构造，tmp使用上面的迭代器区间进行初始化，交换对应的指针，令tmp的指针指向未初始化的内容，最后tmp出了作用域被释放。

注意赋值重载时的参数，是一个传值传参，会调用构造函数生成一个临时对象，令要构造的对象和其进行交换，最后释放临时对象。

		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}
 
		//拷贝构造--现代写法
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		}
 
 
		//赋值
		vector& operator=(vector v)
		{
			swap(v);
			return *this;
		}

指定初始化的个数和参数

有这个函数，我们可以指定初始化时不同类型数据的个数；

这里要注意的是：重载的此函数

如果没有 int 这个类型的重载的话，当我们要初始化5个int 类型的值时，会出现：

原因是 10个 是 int 类型 ，数据 2 也是int 类型，两个相同的类型，会调用有相同类型的参数的函数，这就导致了函数调用的错误；

因此我们在此函数下，重载一个 int 类型的函数，因为整数是会优先匹配int类型。

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

begin 和 end

返回的分别是 vector 起始位置的迭代器与最后一个数据的下一个位置的迭代器

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

size 和 capacity

这两个函数分别返回 vector 中有效数据的个数和空间容量

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

reserve--开辟空间不初始化

当要开辟的空间大于原容量大小的时候，才允许空间开辟

解决野指针问题

当开辟新空间时，_start、_finish、_endofstoage 都指向原来的旧空间；

将旧空间的数据拷贝至新空间后，及时更新，避免野指针问题

解决深浅拷贝问题

一开始使用 memcpy 来完成原始数据到新空间的拷贝是没问题的，但如果出现 vector 内存储的是其他 vector 类型的指针，使用 memcpy 就会出现浅拷贝的问题，析构的时候同一块地址空间会析构两次，报错，这里用赋值操作进行深拷贝。

		void reserve(size_t n)
		{
			//解决野指针问题--提前将大小算出来保存
			size_t sz = size();
 
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)         //判断空，不是空才能拷贝数据和释放
				{
					//memcpy(tmp, _start, size()*sizeof(T)); //开辟新空间将旧的数据拷贝进去
					for (size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
 
				_start = tmp;
 
				//这里_start已经更新，这两行计算size和capacity会引起野指针问题
				//_finish = _start + size();
				//_endofstoage = _start + capacity();
 
				_finish = _start + sz;
				_endofstoage = _start + n;
			}
 
		}

insert--指定插入

插入时首先判断空间是否足够，是否需要扩容；

pos为插入数据的位置，记得更新pos，若不更新pos，则pos还指向原空间，访问时会出现野指针的问题。

更新后，插入位置以后的值从后往前依次往后挪动以为，将pos位置腾出来插入新的数据，最后_finish 自增1，返回 pos 位置的值

为何 insert 要有返回值？

那为何第一个参数不用引用？

一般传参时，第一个参数也可以传函数，比如 begin ，返回的时是起始位置的迭代器，函数的返回值是临时对象，具有常性，传过去是权限的扩大

那给参数加 const 不行吗？

不行，我们的 pos 是要更新的，不能加 const

		iterator insert(iterator pos,const T& x)
		{
			assert(pos >= _start && pos <= _finish); //判定范围
 
			if (_finish == _endofstoage)   //要扩容--会出现迭代器失效的问题
			{
				size_t rpos = pos - _start;
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + rpos;
			}
 
			//挪数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
 
			*pos = x;
			_finish++;
 
			return pos;
		}

erase--指定删除

判断要删除位置是否在有效区间内；

将要删除位置之后的所有数据，从前往后依次向前覆盖一位，最后 _finish 自减1

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

尾插和尾删

复用 insert 和 erase

		void push_back(const T& x)
		{
 
			insert(end(), x);
		}
 
		void pop_back()
		{
 
			erase(end()-1);
		}

[] 重载

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