c++还原简单的vector

文章目录 vectorvecotor的介绍 vector的模拟实现类的框架成员变量迭代器构造函数析构函数size()capacity()operator[]重载扩容resize()尾插验证是否为空尾删clear 清除swap交换insert插入erase删除迭代器区间初始化构造函数拷贝构造赋值运算符重载n个val构造函数再谈构造函数

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的swap std::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+引用所以要有中间者tmp swap(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的模拟实现就到这了。小伙伴们要多多实现加深印象噢！