当前位置：网站首页>vector的使用和模拟实现:

(constructor)构造函数声明	函数说明
vector()	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x);	拷贝构造
vector (InputIterator fifirst, InputIterator last);	使用迭代器进行初始化构造

② 容量空间:

容量空间	函数说明
size	有多少个有效数据
capacity	vector的总容量
empty	有没有数据
resize	扩容，并初始化
reserve	扩容

resize:

reserve:

③modify:

vector增删查改	函数说明
push_back	尾插
pop_back	尾删
find	查找
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[]	像数组一样访问

push_back\pop_back:

find\ insert;erase:

注:erase 和 insert的参数是迭代器>

insert:

erase:

(2)Vector的模拟实现:

namespace dy
{
	//vector 是可以存储多种类型的顺序表
	template<class T>
	class vector 
	{
	   //vector的迭代器是个原生指针
		typedef T* iterator;
		typedef const T* const_iterator;

	public:

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};
}

①构造:

	    //无参构造
		vector()
			: _start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)
		{}

		//迭代器构造
		template<class templateiterator>
		vector(templateiterator first, templateiterator last) 
	        :_start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)

		{
			while (first != last)
			{
				//复用尾插
				push_back(*first);  //push_back 之后会实现
				first++;
			}
		}

		//默认值初始化
		vector(size_t n, const T& val = T())  //因为缺省值不知道 具体给什么，所以就用匿名对象
			:_start(nullptr),
			_finish(nullptr),
			_endofstorage(nullptr)
		{
			reserve(n);  //开辟n个空间

			while (n--)
			{
				push_back(val);
			}
		}
      
            //析构
        	~vector()
		{
			delete[] _start;
 
			_start = _finish = _endofstorage = nullptr;
		}

capactiy、size、operator[] :

	size_t capacity() const
		{
			return _endofstorage-_start; //起始位置减去 容量位置
		}

		size_t size() const  //最好+上
		{
			return _finish-_start;  //起始位置减去 最后数字的位置
		}

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

拷贝构造:

传统写法:

			//传统写法
        //拷贝构造
		//s2(s1)
		vector(const T& v)
			:_start(new T[v.capacity()]),  //开出同样大的空间
			_finish(nullptr),
			_endofstorage(nullptr)
		{
			//将s1 的数据拷贝给s2
			memcpy(_start, v._start, sizeof(T) * v.size());
			
			//更改_finish _endofstorage
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
		}

	   //赋值运算符
		//s1=s2
		vector<T>& operator=(const vector<T>& v)  //operator(&s1,s2);
		{
			if (this != &v)  //自己和自己不赋值
			{
				delete[] _start; //先释放自己的空间
				_start= new T[v.capacity()];
				//拷贝数值
				memcpy(_start, v._start, sizeof(T) * v.size());

				_finish = _start + v.size();
				_endofstorage = _start + v.capacity();
			}
			return *this;
		}

上面是传统写法，代码较为冗杂,

现代写法：

	   //现代写法:
		void swap(const vector<T>& tmp)
		{
			//局部和全局分离
			::swap(_start, tmp._start);
			::swap(_finish,tmp._finish);
			::swap(_endofstorage, tmp._endofstorage);
		}

        //赋值
		vector<T>& operator=(const vector<T>& v)
		{
			if (*this != &v)
			{
              /*
            swap(_start, tmp._start);
			swap(_finish,tmp._finish);
			swap(_endofstorage, tmp._endofstorage);
                                               */
				//this->swap(tmp)
				swap(tmp)  //当然这三个swap实现的功能 一样 可以抽象出来
			}
			return *this;
		}

现代写法不仅兼顾了理解，且代码量少。

②modify:

push_back\reserve:

尾插框架很简单，就分是否需要扩容:

reserve的一大容易被忽略的点在这里。我们先看看测试:

		//迭代器
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end()const
		{
			return _finish;
		}

运行起来后程序直接崩了:

那么问题出在哪里呢？

所以，就要先保存差值:

        void reserve(size_t n)
 		{
			if (n > capacity())  //解耦
			{
				//新开 n 个空间
				T* tmp = new T[n];
				//避免找不到真正的size
				size_t sz = size();
				//可能_start为空
				if (_start)
				{
					memcpy(tmp, _start, sizeof(T) * sz);
					delete[] _start;
				}

				//更新
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;  //开辟了n个空间
			}
		}

		void push_back(const T& val)
		{
			//需要增容
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;  //2倍扩容
				reserve(newcapacity);
			} 

			*_finish = val; //直接怼_finish 解引用找到最后一数的下一个位置
			_finish++;
		}

resize/pop_back:

尾删较为简单也就多赘述

	bool empty()
		{
			return _finish = _start;
		}

		void pop_back()
		{
			assert(empty())
				--finish;
		}

	void resize(size_t n, const T& val=T())  //给定缺省值
		{
			//1.缩减
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				//统一是n>size()
				if (n > capacity()) //如果需要的空间大 那么再去申请空间
				{
					reserve(n);
				}

				while (_finish != _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}

	     }

③补充:

insert\erase:

在pos之前的位置，插入(insert)数值:

我们可以借助，库里面find函数，查找pos位置：

void Insert(iterator pos, const T& val)
		{
			assert(pos < _finish);
			//扩容
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;  //2倍扩容
				reserve(newcapacity);
			}

			//挪动pos之后的数据
			//从后往前
			iterator end = _finish - 1;
			while (end != pos)
			{
				*(end + 1) = *end;
				--end;
			}

			//pos位置处 放val
			*pos = val;
			_finish++;
		}

从结果上来看，我们代码与我们预期相同。然而真的是这吗？

此时我们换种情景:程序直接崩溃,而原因又在哪里呢？！

迭代器失效:

1.迭代器野指针:

我们不难猜到，问题最有可能出现的，就是在增容的部分，而恰恰第四次插入，就是需要增容~

所以，我们就需要对pos ，在扩容的时候，进行修正。

我们让gap记录 start 与 pos之间的相对差距。

void Insert(iterator pos, const T& val)
		{
			assert(pos < _finish);
			//扩容
			if (_finish == _endofstorage)
			{
				size_t gap = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;  //2倍扩容
				reserve(newcapacity); 

				pos = _start + gap;
			}

			//挪动pos之后的数据
			//从后往前
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			//pos位置处 放val
			*pos = val;
			_finish++;
		}

2.迭代器代表的位置发生改变:

插入数据不可避免，会改变原先pos位置所指向的值。所以在用这种迭代器时，需要加点心。

erase:

我们根据库里的来模拟，erase除了删除pos位置的数值，还要返回pos位置，下一个的地址。

	iterator erase(iterator pos)
		{
			//pos后的数 往前移动
			iterator begin = pos + 1;
			while (begin <= _finish)
			{
				*(begin - 1) = *begin;
				begin++;

			}
			_finish--;
			return pos;
		}

另:删除顺序表中的偶数

可能多数，认为删除偶数这样的逻辑是行得通的，比较也有结果。

只要找到偶数，就删掉。

换种数据就不行了。

所以，每次it进行判断的时候，每删除一个，还需要进行判断。

	while (it != v1.end())
		{
			if (*it % 2 == 0)
			{
				it=v1.erase(it);  //利用erase的返回值 
			}
			else
			{
				it++;
			}
		}

(3)深层次深拷贝:

大部分vector 重要的函数接口已经完成。

但，这样的vector在存储自定义类，而非内置类型是，会出现问题。

例如:

此时我们插入四个值，还算正常。

但当插入第五个数的时候。

所以问题还是在于，扩容。

但为啥，当数据足够长的时候，会出现乱字呢？！

在linux下，string不管有多长，都会存在“buf”里面，

但是在vs下，做了别的处理，

当串字符足够小，就存在_buf里面，越长则存在_ptr

所以，这里用memcpy显然不合适，如果仅仅处理内置类型是足够的。

所以和memcpy有关的，就需要更改:

         //拷贝构造
		//s2(s1)
		vector(const vector<T>& v)
			:_start(nullptr),  //开出同样大的空间
			_finish(nullptr),
			_endofstorage(nullptr)
		{
			reserve(v.capacity()); //进行增容
			for (auto e : v)
			{
				push_back(e);
			}
		
			 //传统写法
			//_start = new T[v.capacity()];
			将s1 的数据拷贝给s2
			memcpy(_start, v._start, sizeof(T) * v.size());
			//int sz = size();
			深层次考别
			//for (size_t i = 0;i < v.size();i++)!!
			//{
			//	_start[i] = v._start[i];
			//}

			更改_finish _endofstorage
			//_finish = _start + v.size();
			//_endofstorage = _start + v.capacity();
		}


	void reserve(size_t n)
		{
			if (n > capacity())  //解耦
			{
				//新开 n 个空间
				T* tmp = new T[n];
				//避免找不到真正的size
				size_t sz = size();
				//可能_start为空
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * sz);
					for (size_t i = 0;i < sz;i++)
					{
						//复用 赋值运算符 这是深拷贝~
					     tmp[i] = _start[i];
 					}

					delete[] _start;
				}
				//更新
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;  //开辟了n个空间
			}
		}

vector也就告一段落啦！

祝你好运~