＜C++＞ vector模拟实现

目录

前言

一、定义命名空间

二、构造函数

三、拷贝构造

四、赋值运算符重载

五、push_back && reserve

六、深拷贝问题

七、iterator 迭代器

1. 可读可写

2. 只读

八、operator[ ]

1. 可读可写

2. 只读

九、insert

问题：内部迭代器失效

十、erase

十一、resize

总结

前言

vector的使用与string大致相同，本节我们来参考stl中的vecor，模拟实现vector

由于空间适配器较难，我们直接采用new、delete来完成开空间操作，后期再学习空间适配器。

一、定义命名空间

vector内的数据使用模板代替，因为vector内可能是指针、整形、string、vector等类型
成员变量仿照stl内的vector成员变量，三个指针：start、finish、end_of_storage
将指针类型重命名为iterator

namespace my_vector
{template<class T>class vector{public: typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

二、构造函数

成员变量初始化为nullptr

		vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

初始化n个val，先初始化三个指针为nullptr，不然resize时会使用野指针，这也就体现了C++11可以给成员变量缺省值的优点，不用再为指针初始化为nullptr

		//先初始化为nullptrvector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){resize(n, val);}

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

因为迭代器指针类型不同，所以需要使用模板
		//迭代器模板，适用各种类型指针template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}
但是当我们构造一个v
vector<int> v(10, 1);
编译器会优先调迭代器版本的构造函数，相比 vector(size_t n, const T& val = T()) ，这两个参数更匹配 vector(InputIterator first, InputIterator last)，这是因为有两种选择，编译器选择了更加适合的，所以我们可以重载一个比它更适合的构造函数
		//重载一个更适合的版本vector(int n, const T& val = T()){resize(n, val);}

三、拷贝构造

首先初始化列表初始化各指针为空
再开空间，拷贝，最后修改指针

		//方法一：vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T)*v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

现代写法：我们可以调用内部的函数，而不用手动开空间
		//方法二：vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.capacity());for (auto e: v){push_back(e);}}

在深拷贝问题分析中，我们会再次修改拷贝构造函数

		vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){_start = new T[v.capacity()];/*memcpy(_start, v._start, sizeof(T)*v.size());*/for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

四、赋值运算符重载

同模拟实现string的赋值运算符重载，我们将实参拷贝构造形参，交换this对象与形参对象，返回*this，使得this对象指向了拷贝构造的形参对象，而形参对象指向了原this，这样，在出了函数后，形参自动销毁，而*this的生命周期还在函数外，所以引用返回

		void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}

五、push_back && reserve

尾插前先判断空间是否还有剩余，如果满了，就reserve一段空间
由于经常需要用到size、capacity的值，这些值需要指针相减计算，所以我们直接封装为size()、capacity() 成员函数，方便使用
reserve时，判断原数组_start是否为空。若不为空，再进行数据拷贝，并释放_start空间，最后更新成员变量
在更新成员变量_finish时，如果直接使用size()，会出现错误，因为_start更新了，_finish还没更新，size()返回的是旧的finish - 新的start，会导致第一次更新的_finish为空，所以*finish = x 时就会出错。所以，我们可以提前记录size()，或者调换_start 和 _finish 的更新顺序

		size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];//如果原数组不为空，拷贝数据if (_start){//size(T)算的是成员变量的内存大小，数组内有多少元素没有影响memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;//这里如果直接使用size()，会出现错误//因为start更新了，finish还没更新，size()返回的是 旧的finish - 新的start，//会导致第一次更新的finish为空，所以*finish = x 时就会出错//所以，提前记录size()即可，或者调换_start 和 _finish 的更新顺序_finish = _start + sz;_end_of_storage = _start + n;}}//尽量用引用，因为vector里的数据可能是string、vector等较大的数据void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}

size(T)算的是成员变量的内存大小，数组内有多少元素没有影响

六、深拷贝问题

	vector<std::string> v;v.push_back("11111");v.push_back("22222");v.push_back("33333");v.push_back("44444");v.push_back("55555");for (auto& e : v){cout << e << endl;}
这里的 “11111” 会隐式类型转换为string，因为string有一个单参数的构造函数const char*，因为push_back参数是const T&，所以会发生构造临时变量的操作

当vector内的数据类型为内置类型，进行扩容时reserve函数memcpy没有问题，是按字节拷贝。

但是当vector内的数据是拷贝时需要深拷贝的自定义类型，扩容reserve函数的memcpy就有问题了，虽然vector数组是深拷贝，但是数组元素没有深拷贝，我们是按自定义类型字节大小进行的浅拷贝，拷贝的vector内的对象指向了被拷贝的vector对象的数组空间，又因为memcpy之后，立即调用了 delete[] _str，delete直接调用了数组内所有对象的析构函数，并释放数组空间，最终导致新拷贝的vector内的元素string的_str都指向了被释放的空间

解决方法：

按元素个数遍历，逐个赋值运算符重载赋值给tmp

		void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];//如果原数组不为空，拷贝数据if (_start){//size(T)算的是成员变量的内存大小，数组内有多少元素没有影响/*memcpy(tmp, _start, sizeof(T) * sz);*/for (size_t i = 0; i < sz; ++i){//每个自定义类型数据都采用赋值运算符重载//若为内置类型，也没有影响tmp[i] = _start[i];}delete[] _start;}_start = tmp;/*这里如果直接使用size()，会出现错误因为start更新了，finish还没更新，size()返回的是 旧的finish - 新的start，会导致第一次更新的finish为空，所以*finish = x 时就会出错所以，提前记录size()即可，或者调换_start 和 _finish 的更新顺序*/_finish = _start + sz;_end_of_storage = _start + n;}}

所以，拷贝构造函数的memcpy也要跟着修改

		vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){_start = new T[v.capacity()];/*memcpy(_start, v._start, sizeof(T)*v.size());*/for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

所以，我们可以再次理解vector<vector<int>> vv

七、iterator 迭代器

1. 可读可写

begin()、end() 分别对应 _start 和 _finish，返回两指针即可

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

2. 只读

对于被const修饰的对象，在使用迭代器时，迭代器需要被const修饰，权限平移

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

八、operator[ ]

1. 可读可写

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

2. 只读

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

九、insert

第一步：对于insert函数，参考STL中vector的insert函数，参数为iterator迭代器，以及要插入的值，所以第一步要判断iterator是否在合法的范围
第二步：进行扩容判断，如果要扩容就扩二倍，reserve()
第三步：进行移位（这里略微体现了STL的vector为什么成员变量要用指针表示，而不用size_t 型的size以及capacity，因为对于size_t类型，如果pos指向_start，即pos == 0，那么end--时会出现end < 0 的情况，而size_t是无符号整形，-1是最大值，循环不会中断，陷入死循环）
第四步：进行填充，并使_finish++，相等于size++

		void insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finfish;}

问题：内部迭代器失效

当我们插入的数据超过8个时（第一次扩容为4，第二次扩容二倍为8，第三次扩容为16），就会插入失败，是随机值。为什么呢？

分析：扩容处出现错误，因为每次扩容都是开辟一个新的空间，_start、_finish、_end_of_storage都会随之修改，而形参iterator pos是不变的，它还指向的原空间，成为野指针。

解决：扩容前记录pos相对_start位置，并在扩容后更新

		void insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finfish;}

对于 push_back 我们可以复用 insert 函数

		void push_back(const T& x){/*if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;*/insert(end(), x);}

新问题：外部的迭代器

因为insert函数形参是iterator类型，是临时拷贝，如果扩容了，函数内部的pos会更新，但是在外部，实参pos还是原先的迭代器，如果此时在外部修改pos，相当于修改野指针，很容易出错，也就是说，在insert之后迭代器可能会失效（之所以是可能，是因为平台不一样扩容机制不一样，Linus扩容2倍，VS扩容1.5倍）

所以，记住！insert以后就不要使用这个形参迭代器了，因为它很可能失效了，如果再进行
	vector<int>::iterator pos = v.begin() + 3;v.insert(pos, 500);*pos += 10;
*pos += 10; 这是高危行为

所以，STL的vector将insert的返回值设置为iterator，

返回指向第一个新插入元素的迭代器，所以如果想继续修改，就用返回的迭代器，不要用实参传的迭代器
		iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}

十、erase

删除元素，移动后面元素即可
--_finish

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

erase的迭代器会失效吗？

会，在特殊的情景会失效，当迭代器指向最后一个元素，删除元素后，迭代器就会失效。

我们先看一般情况：
void test2()
{vector<int> v;v.push_back(5);v.push_back(4);v.push_back(3);v.push_back(2);v.push_back(1);for (auto& e : v){cout << e << " ";}cout << endl;vector<int>::iterator it = v.begin();v.erase(it);cout << *it << endl;++it;cout << *it << endl;for (auto& e : v){	cout << e << " ";}
}
可以看出，此时的迭代器没有失效，解引用和++操作都没有异常，但是当it指向最后一个元素时，问题就出现了
void test2()
{vector<int> v;v.push_back(5);v.push_back(4);v.push_back(3);v.push_back(2);v.push_back(1);for (auto& e : v){cout << e << " ";}cout << endl;vector<int>::iterator it = v.begin() + 4;v.erase(it);cout << *it << endl;++it;cout << *it << endl;for (auto& e : v){	cout << e << " ";}
}
可以看到，当删除了最后一个元素后，第一次解引用是被删除的值 —— 1，相当于野指针（因为该空间按理来说已经 “释放” 了，对于数组删除元素，我们一般不抹除值，只进行覆盖），当 it++ 后再次解引用，it 还是野指针，但指向的空间是随机值，所以打印出了随机值

对于VS的vector，它会强制判断，如果进行上面的操作，即使不是删除最后一个元素后再使用迭代器，VS都会直接报错；而g++不同，它不进行检查，但是不检查的行为，会导致出现很多问题。

所以，同 insert 函数 erase 之后也不要使用迭代器，这也是高危行为

返回一个迭代器，指向删除的最后一个元素之后的元素的新位置。如果操作删除了序列中的最后一个元素，则容器结束。
		iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator begin = pos + 1;while (begin != _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}

如果要在vector中删除偶数，那么迭代器要使用erase返回的迭代器，如果使用自己的迭代器，VS就不通过，代码没有移植性。

其实对于erase，可能会出现其他平台，很珍惜内存空间，在删除了一半的数据后，会缩容，那么缩容时，迭代器肯定是失效的

总结：vector在使用insert和erase之后，不能再访问这个迭代器，虽然insert之后迭代器有可能没有失效，但是我们都认为失效了，即访问结果是未定义的

十一、resize

对于vector来说resize是很重要的，在resize时，我们要指定默认初始为什么，这里就用到了模板和匿名对象。
void resize(size_t n, const T& val = T())
对于自定义类型，构造时会调用其类型的默认构造函数，如果没有默认构造，那么这个resize函数就编译不通过，这也说明了，我们在写类的时候一定要写默认构造，不然坑害的是自己。

对于内置类型，比如 int ，int( )在理论上是不行的，因为int并没有构造函数，但是这个需求是肯定的！所以C++的内置类型在C++出了模板之后就升级了，对于内置类型也有其构造函数，对于整形默认初始化为0，浮点型为0.0，指针类型为空。
int main()
{int i = 0;int j = int();int k = int(1);cout << "i = " << i << endl;cout << "j = " << j << endl;cout << "k = " << k << endl;return 0;
}

		//T类型匿名对象，对于自定义类型，调用它的默认构造，没有默认构造，那么程序就编不过void resize(size_t n, const T& val = T()){if (n < _finish){_finish = _start + n;}else{reserve(n);while (_finish != start + n){*_finish = val;++_finish;}}}

整体代码：

#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using std::cin;
using std::cout;
using std::endl;namespace my_vector
{template<class T>class vector{public: 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;}//先初始化为nullptr，因为成员变量给了初始值，所以可以不使用初始化列表vector(size_t n, const T& val = T())//:_start(nullptr)//, _finish(nullptr)//, _end_of_storage(nullptr){resize(n, val);}//重载一个更适合的版本vector(int n, const T& val = T()){resize(n, val);}//迭代器模板,使用所有自定义类型的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//方法一：vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){_start = new T[v.capacity()];/*memcpy(_start, v._start, sizeof(T)*v.size());*/for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}方法二：//vector(const vector<T>& v)//	:_start(nullptr)//	, _finish(nullptr)//	, _end_of_storage(nullptr)//{//	reserve(v.capacity());//	for (auto e: v)//	{//		push_back(e);//	}//}//赋值运算符重载void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];//如果原数组不为空，拷贝数据if (_start){//size(T)算的是成员变量的内存大小，数组内有多少元素没有影响/*memcpy(tmp, _start, sizeof(T) * sz);*/for (size_t i = 0; i < sz; ++i){//每个自定义类型数据都采用赋值运算符重载//若为内置类型，也没有影响tmp[i] = _start[i];}delete[] _start;}_start = tmp;/*这里如果直接使用size()，会出现错误因为start更新了，finish还没更新，size()返回的是 旧的finish - 新的start，会导致第一次更新的finish为空，所以*finish = x 时就会出错所以，提前记录size()即可，或者调换_start 和 _finish 的更新顺序*/_finish = _start + sz;_end_of_storage = _start + n;}}//T类型匿名对象，对于自定义类型，调用它的默认构造，没有默认构造，那么程序就编不过void resize(size_t n, const T& val = T()){if (n < _finish){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//尽量用引用，因为vector里的数据可能是string、vector等较大的数据void push_back(const T& x){/*if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;*/insert(end(), x);}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//解决pos迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator begin = pos + 1;while (begin != _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}