C++_vector类

欢迎来到本期节目- - -

vector类

本期直接先上代码，然后以代码为例介绍需要注意的问题.

---

模拟实现：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace my_room
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend() const{return _finish;}
//---------------------------------------------------------------------------------------------//构造和析构//无参默认构造vector()	{//由于给了缺省值，所以可以给空}//带参构造vector(size_t n, const T& value = T())	{reserve(n);while (n--){push_back(value);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last)		{size_t size = last - first;reserve(size);		//提前开好空间，减少扩容次数while (first != last){push_back(*first);first++;}}//拷贝构造vector(const vector<T>& v)			{vector<T> tmp(v.cbegin(), v.cend());//直接复用swap(tmp);}//赋值重载拷贝vector<T>& operator=(vector<T> v)	{swap(v);return *this;}~vector(){delete[] _start;	//为空也不影响_start = _finish = _endOfStorage = nullptr;}//----------------------------------------------------------------------------------------------//核心函数void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){reserve(n);if (n <= size()){_finish = _start + n;}else{while (_finish != _start + n){*(_finish++) = value;}}}iterator insert(iterator pos, const T& x){assert(pos <= end());size_t old_posi = pos - begin();if (_finish == _endOfStorage){size_t n = capacity() == 0 ? 4 : capacity() * 2;reserve(n);}iterator tail = end();pos = begin() + old_posi;while (tail > pos){*tail = *(tail - 1);tail--;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos < end());iterator begin = pos+1;while (begin != _finish){*(begin-1) = *begin;begin++;}_finish--;return pos;}//----------------------------------------------------------------------------------------------//简单函数size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty()const{return _start == _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};
}

核心函数

reserve

首先我们看看reserve函数
当我们在实现vector时，我们都知道，实现异地扩容都要经历这个流程：

注意

在这其中，拷贝数据就需要注意，在以往的顺序表中，我们可能会用memcpy来拷贝数据，当然在内置类型的情况下，memcpy不仅不会出错，而且比赋值拷贝高效；

但是这里是类模板，数据类型T可以是自定义类型,就有可能需要深拷贝，而memcpy本质上是浅拷贝，不满足需求，所以使用赋值重载拷贝完成自定义类型的拷贝.

除此之外，还需要注意的是更新属性问题，

_finish = _start+size();	//size()返回的是 (_finish - _start)的值

此时_finish指向旧空间，_start指向新空间，返回的值根本不是有效数据的个数；

所以需要在扩容之前记录一个old_size记录数据个数，使_finish指向有效数据的末尾.

 void reserve(size_t n){if (n > capacity()){size_t old_size = size();			//记录old_size是为了不影响有效数据末尾的正确计算T* tmp = new T[n];for (size_t i = 0; i < old_size; i++)		{tmp[i] = _start[i];				//使用赋值拷贝是为了满足有深拷贝的自定义类型对象}delete[] _start;_start = tmp;_finish = _start + old_size;_endOfStorage = _start + n;}}

resize

接下来瞧瞧resize
resize只需要注意，该函数会改变有效数据的个数以及有可能会扩容.

void resize(size_t n, const T& value = T())
{reserve(n);		//管他容量够不够，直接让reserve去判断.if (n <= size()){_finish = _start + n;	//直接删除数据}else{while (_finish != _start + n)	{*(_finish++) = value;		//添加数据}}
}

insert

接下来瞅瞅insert
在实现insert函数时，核心逻辑就是移动数据.

iterator insert(iterator pos, const T& x)
{assert(pos <= end());		//注意可以尾插，所以取等size_t old_posi = pos - begin();			//由于可能需要扩容，所以会导致迭代器指向旧空间，提前记录相对位置if (_finish == _endOfStorage){size_t n = capacity() == 0 ? 4 : capacity() * 2;reserve(n);}iterator tail = end();pos = begin() + old_posi;		//更新迭代器while (tail > pos){*tail = *(tail - 1);		//从后往前挨个 向后移动tail--;}*pos = x;		//插入数据_finish++;return pos;
}

erase

最后瞄一下erase

iterator erase(iterator pos)
{assert(pos < end());		//_finish没有数据，不能取等iterator begin = pos+1;while (begin != _finish){*(begin-1) = *begin;			//从前往后挨个  向前移动begin++;}_finish--;return pos;
}

---

迭代器

迭代器：

迭代器屏蔽了底层的实现细节，使得设计人员无需关心容器对象的内存分配就可以直接使用相应接口，达到类似指针的效果.

也就是说迭代器可能是指针，也可能是指针的封装.

上图中迭代器支持的行为是向下兼容的，
假设p1,p2是迭代器，i是常量

Iterator	描述	行为
随机迭代器	支持随机访问的迭代器	p1++，p1- -，p1+i，p1-i，p1==p2，p1>p2，p1<p2
双向迭代器	可以向前或者向后移动的迭代器	p1++，p1- -，p1==p2
前向迭代器	只能向前移动的迭代器	p1++，p1==p2
输入迭代器	只能向前移动并读取的迭代器	p1++，p1==p2
输出迭代器	只能向前移动并写入的迭代器	p1++ ，p1==p2

很明显咱们的vector的迭代器是随机迭代器.

迭代器失效

什么是迭代器失效？
迭代器所指向的节点无效了，既该节点被删除了.

vector迭代器失效场景

• 场景1：扩容

void test()
{my_room::vector<int> arr;for(int i = 0; i < 10; i++)	//存入1到10{arr.push_back(i+1);}my_room::vector<int>::iterator old_back = arr.end()-1;	//指向最后一个元素10arr.reserve(1000);cout<< *old_back <<endl;	//程序崩溃----error代码，请勿模仿
}

扩容之后，old_back指向的空间已经被释放了，此时相当于使用野指针.

事实上，不一定只能通过直接显示调用reserve导致迭代器失效，也可以间接调用reserve发生扩容行为导致迭代器失效;

例如: 使用resize函数可能会扩容,使用insert,push_back函数也可能扩容

总的来说，就是底层涉及扩容的行为，就需要注意迭代器失效的问题.

• 场景2：删除

void test()
{my_room::vector<int> arr;for(int i = 0; i < 10; i++)	//存入1到10{arr.push_back(i+1);}my_room::vector<int>::iterator  start = arr.begin();	//指向第一个元素1while(start != arr.end())	//预期删除所有元素{arr.erase(start);	//------error代码，请勿模仿}cout << arr.size();	//看看有没有删完,但实际上在vs中直接报错.
}

本来预期的是start一开始指向第一个元素,删除之后,剩下的元素往前移,然后继续删，直到删完.

但是实际上删除行为同样也有迭代器失效的风险.

迭代器失效解决方案

我们知道在使用vector时，当接口涉及扩容问题或者删除问题时，会有迭代器失效的问题.
解决办法就是使用之前对迭代器重新赋值.

void test()
{my_room::vector<int> arr;for(int i = 0; i < 10; i++){arr.push_back(i+1);}my_room::vector<int>::iterator old_back = arr.end()-1;	arr.reserve(1000);old_back = arr.end()-1;cout<< *old_back <<endl;	//程序正常运行
}

void test()
{my_room::vector<int> arr;for(int i = 0; i < 10; i++)	{arr.push_back(i+1);}my_room::vector<int>::iterator  start = arr.begin();while(start != arr.end()){start = arr.erase(start);	}cout << arr.size();	//程序正常运行
}

希望本片文章对您有帮助，请点赞支持一下吧😘💕