[C++]vector模拟实现

目录

前言：

1. vector结构

2. 默认成员函数

2.1 构造函数

无参构造：

有参构造：

有参构造重载：

2.2 赋值运算符重载、拷贝构造（难点）

2.3 析构函数：

3. 扩容

3.1 reserve

3.2 resize

4. 插入删除

5. 迭代器操作

---

前言：

        本篇文章模仿的vector与STL源码并不完全一致，例如本文直接通过new来开辟空间，但是源码中通过内存池分配，但是这并不影响彼此之间的关系，所以本篇文章还是有一定的学习意义的。

1. vector结构

模板：

template<class T>

class vector

{

public:

        typedef T* iterator;

        typedef const T* const_iterator;

private:

        iterator _start;

        iterator _finish;

        iterator _end_of_storage;

} 

        我相信如果大家用过vector的话，一定是知道每一次使用vector都需要标注清楚这个类是用来存储什么样的数据的，例如：

vector<int> vv1;                存整型数据

vector<double> vv2;         存浮点型数据

vector<vector<int>> vv3;  存存整型数据的vector数据

        所以，我们模拟的vector类就不能单独面向某一种数据，而是应该考虑到所有的类型，就算是一直自定义类型嵌套也能实例化出来，如下：

vector<vector<vector<vector<vector<int>>>>>  vv4;

         虽然上述的类型对于我们来说估计这辈子都不会遇到，但是我们总不能防止某些好奇心重的小伙伴搞事，所以是必须要能够支持这种写法的，就像是为了满足到酒吧点炒饭的帅小伙。

        所以首先得出结论：我们的类需要被构建成模板类。

成员变量：

        上面代码中可以看到我们的成员变量的类型是自定义类型重定义iterator，也就是平时我们熟知的迭代器，我们的迭代器实现又是指针的方式，所以可以将这三个变量理解为我们存储数据空间的三个位置。_start对应开头，_finish对应数据结尾，_end_of_storage对应空间容量的最后位置。也即是对应我们顺序表的size和capacity。

2. 默认成员函数

        每当我们实现一个类，默认成员函数是必不可少的，特别是像是我们vector这样需要向堆申请空间的类。

2.1 构造函数

无参构造：

        无参构造可以说是非常简单了，我们甚至连空间都不需要开辟，只需要通过初始化列表为我们的三个迭代器变量初始化即可，如下：

//默认构造方式，全指针都置空值，后续无论怎么插入都有扩容为指针赋值
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}

        可能有朋友要问，那用这种方式，不就表示了自己之后不能插入数据之类的吗？事实不是，因为我们还有其它的函数接口为我们服务，大家看下去就明白了。

有参构造：

        有参构造咱们就与库保持一次，既然它不支持通过一个值直接去初始化，而支持通过n个T类型数据去构造，那么我们也这样学习它这样：

         看不懂上面的库实现方式没事，看我的也是一样：

//有参构造n个T类型的数据进入vector<int>
vector(size_t n, const T& va = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{T* temp = new T[n];for (size_t i = 0; i < n; ++i){//这里赋值操作是<T>和<T>之间的操作temp[i] = va;}_start = temp;_finish = _start + n;_end_of_storage = _finish;
}

        这里的构造也是一样，需要通过初始化列表先将三个迭代器变量初始化空指针，因为我们不能保证有没有小聪明蛋给n赋值为0去初始化，其次就是我这里使用了T()这样的匿名对象作为缺省参数。

        有同学在这里就要问了：T()这样的匿名对象生命周期不是只有一行吗？你这代码都多少行了，还在用不是错的吗？

        其实不是，在C++当中，当我们用const加引用类型的变量去接收匿名对象，会改变匿名对象的生命周期为这个变量的生命周期长度，如下：

const int& ret = T();        改变T()的生命周期为ret

T();                                生命周期只有一行

         值得注意的是上面的const是必须加的，因为我们的T()属于本身是属于临时对象的，而临时对象又有常量属性，也就是不可更改属性。如果不用const接收，那么就会导致错误。

        有点意思的是，不加const在vs2013及其之前的版本都是不报错的，后续版本我不清楚，但是到了vs2019这个BUG就被修复了。

函数设计：

        这里的代码我用了最全面的写法，后面可以通过函数复用的方式直接究极简化。

        首先通过new向堆申请n个T类型的空间，这里不能使用malloc这种C语言的申请方式，原因我相信大家也明白，就是因为我们要实现模板类，那必然有可能使用自定义类型，有自定义类型要就要去调用它的构造函数，只有new才能实现，malloc不行。

T* temp = new T[n];

        然后通过循环不断的赋值，最后为三个迭代器变量定位即可，这里循环体中的赋值操作涉及了很复杂的嵌套操作，绝不是简单的一行代码，等到下一小节重载赋值运算符我再来讲。

有参构造重载：

vector(int n, const T& va = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (n--){push_back(va);}
}

        该重载的函数体就是我所说的究极优化的方式，通过尾插函数，不断的复用，就实现了函数功能，但是重点不在这里，我重载这个函数的意义在于为我们的迭代器区间构造函数服务。 

        为什么这么说？请先看迭代器区间构造函数。

template<class InputIterator>
vector(InputIterator start,InputIterator end):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (start != end){push_back(*start);++start;}
}

         首先我们得知道一个点，那就是C++为我们提供了函数重载，那么编辑器就会通过传入的参数类型为我们匹配最适合的函数。

        举例：当我们通过下列方式传参：

vector<int> vv1(5,5);

        编辑器会将我们的传参类型认为是int,int，而不是size_t,int，也就是说，编辑器就会找到迭代器区间构造函数中去了，这并不是我们想要的结果，而编辑器却认为这是最合适的函数，为了避免这种情况的出现，所以需要重载int型的构造函数。

        当然，有的小伙伴可能不太理解为什么我们需要再写一个模板出来，这理解起来真难受。这确实让人很难受，但是他带来的好处也是很大的，因为这样实现的功能，让我们的构造方式做种多样的起来，无论是何种形式的迭代器去构造，我们都有对应的方式去构造出来，这就是牛逼之处。

2.2 赋值运算符重载、拷贝构造（难点）

代码：

vector<T>& operator=(const vector<T>& va)
{if (_start != va._start){//只能通过new的方式实现，因为要调用自定义类型的构造函数T* temp = new T[va.capacity()];//保留数据//memcpy(temp, va._start, sizeof(T)* va.size());int len = va.size();for (int i = 0; i < len;++i){//嵌套temp[i] = va[i];}//释放掉原来空间，如果有的话delete[] _start;_start = temp;_finish = _start + va.size();_end_of_storage = _start + va.capacity();}return *this;
}

        赋值需要相同类型才能成功，这里用const vector<T>&相信大家也能理解，我就直接切入重点了。

        为什么我代码中要用循环一个一个的赋值，为什么不直接调用库函数memcpy()呢？简单又方便，而是通过循环一个一个的赋值，感觉写得好搓哦。其实呢，也不是博主不想用memcpy()，而是现实给了博主一巴掌，让我认清，写模板类的深拷贝有多令人头疼。

        举一个例子：如果我们构建的vector<vector<int>>类型的类，那么我们开辟了一片空间用于存n个vector<int>，然后这些vector<int>被我们直接用memcpy直接拷贝过来了，但是我们呢，又不能直接为单独写一个函数，因为这是模板，要是单独写了，又不满足vector<int>类型了。下图：

         原本我们是希望赋值出来的对象能有一个新的空间去承载这些数据，如上图，但是如果我们通过memcpy来实现能够成功吗？请看下图：

         很明显，如果通过memcpy实现了一个什么功能？我们确实实现了一层深拷贝，将vector<int>用新的空间承载起来了，但是还有更里面的空间呢？这些空间也是需要new出来的哇。用memcpy还能行吗？能行，但不完全行，除非你保证你以后不会用自定义类型模板。

        所以决定采用循环的方式，一次一次的赋值，其中有一句话非常重要，那就是：

temp[i] = va[i];

         这一句话没有你想象的那么简单，你想，如果是内置类型我们关不关心他申请空间？不关心，那么对于自定义类型它会怎么做？嵌套！！！，直到遇到内置类型嵌套就结束了，如下图：

        上图中，我们可以看到，每次我们赋值拷贝，如果遇到了一个赋值运算符，编辑器就回去检查是否是自定义类型，需要去调用赋值运算符重载函数，如此反复，直到没有赋值运算符重载函数，也就是没有需要申请空间的必要了。

         下图的编译，运行，使用也不会报任何的错误了。

拷贝构造：

//拷贝构造
vector(const vector<T>& va)
{//赋值重载*this = va;
}

        拷贝构造直接复用赋值运算符重载函数就行，写法和逻辑思维差不多，博主也想偷懒。

2.3 析构函数：

//析构函数
~vector()
{//释放空指针不会出错，无论是什么方式delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;
}

        析构函数也没有什么好讲的，看代码就行。

3. 扩容

3.1 reserve

代码：

void reserve(size_t n)
{if (n > capacity()){size_t len = size();T* temp = new T[n];if (_start != nullptr){//memcpy(temp, _start, sizeof(T) * size());for (size_t i = 0; i < len; ++i){temp[i] = _start[i];}delete[] _start;}_start = temp;_finish = _start + len;_end_of_storage = _start + n;}
}

        vector和其它string、顺序表或者说任何数据结构一样，能不缩容就不缩容，所以，当我们的n小于容量大小的时候，不做任何处理直接返回即可。

        同样，这里也涉及到了多次深拷贝的问题，也就不能用memcpy来实现，需要用循环依次赋值。还有，咱们需要考虑到当空间异地扩容之后是需要将原空间释放的，以防内存泄漏。

3.2 resize

代码：

void resize(size_t n,const T val& = T())
{//小于操作不需要缩容，只需要将_finish重定位即可if (n < size()){_finish = _start + n;}else if (n == size()){}		//无动作else{int len = n - size();//_finish和_end_of_storage的绝对位置之差与n的大小之比if (_finish + n > _end_of_storage){reserve(capacity() == 0 ? n : capacity()+n);}//补齐T类型数据while (len-- > 0){*_finish = val;_finish++;}}
}

        resize功能比reserve多一个，那就是能够实现重定size大小，大于size的部分通过数据val占位。然后复用reserve，如果是第一次扩容，那就需要用三目运算来判断给定大小。

4. 插入删除

        内容比较简单，相信大家配合注解能够看懂，直接上代码：

//尾插只需要考虑如果空间不够就应该扩容
//并且，还有空容量的情况也需要考虑
void push_back(const T& val)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//如果不需要reserve表示不用扩容，那么就是原地扩，不需要动_start和_end_of_storage//如果扩了容，reserve会为我们将这几个变量重定向*_finish = val;++_finish;
}//插入
iterator insert(iterator pos, const T& val)
{//检查插入位置的有效性assert(pos >= _start);assert(pos <= _finish);//提前保留绝对距离size_t len = pos - _start;//判断扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//通过绝对值偏移重定向pos = _start + len;//指向最后一个位置的下一个地址iterator end = _finish;//移动完pos位置的数据，结束while (end > pos){*(end) = *(end - 1);--end;}//因为有赋值运算符重载，那么不管是否是内置类型，都能满足*pos = val;//向后移动一位++_finish;return pos;
}//删除
void erase(iterator pos)
{//判断pos可行性assert(pos >= _start);assert(pos < _finish);//从pos下一个位置地址开始依次向前移动iterator start = pos + 1;//中途是没有任何扩容缩容的地方，所以迭代器不会更换while (start != _finish){*(start - 1) = *start;++start;}//删除会有机会产生结果不确定的意外情况//所以，任何一次删除，该迭代器都应该被销毁//该函数才不会设置返回值--_finish;
}//尾删，检查是否还有数据能删除
void pop_back()
{assert(_start != _finish);--_finish;
}

5. 迭代器操作

//迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}//求个数、容量
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}//重载[]，需要区分const有无的区别和pos位置的准确性
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}

        迭代器是有失效的情况的，这部分根据不同的编辑器会有不同的实现方式，博主这里不太想多讲，不过我建议大家通过迭代器插入删除数据之后就别再使用这个迭代器了，或者是重新给他定位，防止非法越界。

---

        以上就是博主对vector模拟实现的全部理解了，希望能够帮到大家。