vector

vecotor的介绍

1.vector是表示可变大小数组的序列容器

2.就像数组一样，vector也采用连续存储空间来存储元素，意味着可以采用下标对vector的元素进行访问。（和数组一样高效）

3.vector使用动态分配数组来存储元素，当新元素插入时，而旧的空间不够时，一般分配一个新的数组，然后把全部元素移到新的数组，再进行新元素的插入。

4.vector会分配一些额外的空间来适应可能的增长，因此存储空间比实际需要的存储空间更大。

库里vector

vector的模拟实现

类的框架

namespace Vect
{template<typename T>//模板参数class vector{
public:成员函数......
private:成员变量......};
}

成员变量

	private:iterator _start;//从0开始iterator _finish;//最后一个成员变量的下一个位置iterator _endofstorage;//容量

迭代器

这里的迭代器iterator可看作为指针

typedef T*iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start; 
}iterator end()
{
return _finish; 
}
const_iterator begin()const
{
return _start;
}const_iterator end() const
{
return _finish;
}

构造函数

vector()//构造函数//这里用初始化列表比较方便:_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}

析构函数

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

size()

指针相减 得指针之间成员个数

size_t size() const//size---有效成员个数{return 	_finish - _start;}

capacity()

	size_t capacity()const//capacity---容量{return _endofstorage - _start;}

operator[]重载

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

扩容

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();//记录成员个数T* tmp = new T[n];//开辟新空间if (_start)//如果_start指向的空间不为空就要拷贝数据{//把_start的数据拷贝到tmp上面//memcpy(tmp, _start, sizeof(T) * oldsize);//这里实现了浅拷贝//后面会谈到memcpy的弊端for(size_t i=0;i<oldsize;i++){tmp[i]=_start[i];//这里实现深拷贝}//删除旧空间-空间不为空才需要释放delete[]_start;}_start = tmp;//指向新空间
//原来的size=_finish-_start,而此时的_start是新空间的_start,   //_finish是旧空间的_finish，相减得出不是之间成员个数了；所以我们要用oldsize()来记录先前的成员个数，用新的_start+oldsize()得出新的_finish_finish = _start + oldsize;_endofstorage = _start + n;}
}

resize()

void resize(size_t n, T val = T())//value_type val 给匿名对象
//n<size():缩容；
//size()<n<capacity():用val初始化有效成员以外的成员变量；
//n>capacity():扩容且用val初始化有效成员以外的成员变量；		
{if (n > capacity())//n大于容量{reserve(n);//扩容}if (n > size()){while (_finish < _start + n){//用val初始化有效成员以外的成员变量；*_finish = val;++_finish;}}else{_finish = _start + n;//缩size（）}}

尾插

void push_back(const T& x)//尾插{if (_finish == _endofstorage)//扩容{size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}

验证是否为空

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

尾删

void pop_back(){assert(!empty());--_finish;}

clear 清除

void clear()//清理---不影响容量{_finish = _start;}

swap交换

void swap(vector<T>& v)//交换
{//这里要指明是std库里的swap，因为头文件展开后从上往下找swap函数不一定先找到的是std库里的swap，还可能是vector的swapstd::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage,v._endofstorage);}

insert插入

这里我们实现第一个接口

//迭代器失效：当插入时要扩容，pos指针指向原来的空间，而_start指向新空间，在挪动数据时会出问题iterator insert(iterator pos, const T& val){//pos要在_start和_finish之间assert(pos >= _start);assert(pos < _finish);//_start为空时插入要扩容或者容量满了都要扩容if (  _finish==_endofstorage){size_t len = pos - _start;//记录pos的相对位置size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;//针对迭代器失效要对pos更新}iterator end = _finish - 1;while (end >= pos)//挪动数据{*(end + 1) = *(end);--end;}pos = val;++_finish;	return pos;}

erase删除

这里我们实现第一个接口

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

在这里我们创建一个vector往里面尾插1234；之后我们删除4；并且打印删除后的迭代器位置

这里我们运行了看起来没有问题，实际上问题很大！删除4后容器的数据只有123，而我们访问到了4—野指针越界访问！ 这里我们实现的模拟跟Linux系统下相似，所以在Linux系统下也不会报错；但我们如果删除的是2或者是3呢？会越界吗？换句话说：迭代器会失效吗？答：在Linux系统下迭代器可能会失效也可能不会！但在vs下必然失效！

这里我们换库里面的vector的erase试一下

果然在vs下对迭代器做了更严格的检查，读都不给读，更何况是写；—迭代器失效了吗？？？好像失效了，这里有人会说你这个删除4肯定是越界了，那我删除别的对象不就不越界了嘛？

好现在我们删除2

照样报错！所以我们使用完迭代器之后最好就不要再用迭代器了

如果硬要用就更新迭代器！

删除4—会被断言出越界

删除2—更新了迭代器不会报错

现在在vs还是Linux下都不会发生迭代器失效了，若越界直接断言！

迭代器区间初始化构造函数

		template <class InputIterator>vector(InputIterator first, InputIterator last)//构造函数：用迭代器区间去初始化: _start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);++first;}}

拷贝构造

	vector(const vector<T>& v)//拷贝构造:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)//因为要扩容，所以要提前初始化三个迭代器
{
vector<T> tmp(v.begin(),v.end());//用迭代器构造tmp；因为是用的const+引用所以要有中间者tmpswap(tmp);//this和临时对象tmp交换}

赋值运算符重载

vector<T>& operator=( vector<T> v)//传值{
//赋值的时候如果容量满了会扩容，就算是自己赋值給自己也会扩容；先后经过后者拷贝构造临时对象，拷贝构造时用到迭代器区间构造临时对象，//然后构造时就用到尾插push_back，尾插时就验证要不要扩容！swap(v);//this和v交换return *this;}

n个val构造函数

		vector(size_t n, const T& val = T())//库里面給的是size_t n: _start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);//扩容for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T())//int模式构造函数的n重载size_t模式构造函数的n: _start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);//扩容for (int i = 0; i < n; i++){push_back(val);}}

上面出现了size_t n的构造函数和int n的构造函数

我们做个实验，把int n的构造函数注释掉；然后用10个5初始化构造v

运行后发现报错了，原因是非法的间接寻址。这是为啥呢？

我们看到上面10个5初始化，类型为**（int ,int)** ；而n个val的参数类型为**（size_t ,int)**

另一个迭代器区间初始化的参数类型为**（InputIterator first, InputIterator last）**

分别为两个参数模板类型，而int参数也可以作为参数模板；

（int,int)参数类型进到**(size_t,int)参数类型前者int还需要整形提升**；而对于（InputIterator first, InputIterator last）类型(int,int)可以直接进入。但到后面的地址解引用就是非法寻址了！

所以我们还需要在写一个(int,int)参数类型的构造函数重载(size_t ,int)构造函数

再谈构造函数

这里我们创建一个4个vector<vector<int>>,給vector<int>序列初始化为11

然后我们打印出来

我们打印四个vector<int>，没毛病。我们打印五个：报错了！

这是为啥呢？我们前面写到构造函数扩容，size达到4时要扩容，前者四个没报错而后者5个报错了！这说明扩容有问题！

构造函数用到push_back，数量达到4个要扩容，而这里的扩容是先new一块8个对象(类型为vector<int>)大的新空间tmp（类型为vector<vector<int>>)，把旧空间的vector<int>的_start一个个拷贝（这里是memcpy-浅拷贝）到新空间；再delete旧空间vv（先依次析构v再析构空间vv）；再把 vv的 _start指向新空间tmp；这时我们发现vv扩容为tmp是完成了深拷贝（把v的 _start一个个拷贝到tmp上），而v却还是浅拷贝（ v的 _start 还是指向原来的空间，而原来的空间已经被析构了—属于野指针越界访问！）这里配合着下图理解

所以我们要换种方式扩容拷贝

		void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];//开辟新空间if (_start)//如果_start指向的空间不为空就要拷贝数据{for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];//复用运算符重载=完成深拷贝delete[]_start;//删除旧空间-空间不为空才需要释放}}_start = tmp;//指向新空间_finish = _start + oldsize;_endofstorage = _start + n;}}

好啦，vector的模拟实现就到这了。小伙伴们要多多实现加深印象噢！