【C++】vector容器实现

目录

一、vector的成员变量

二、vector手动实现

（1）构造

（2）析构

（3）尾插

（4）扩容

（5）[ ]运算符重载

5.1 迭代器的实现：

（6）尾删

（7）插入

（8）删除

（9）迭代器失效

9.1 reserve扩容迭代器失效

9.2 insert后迭代器失效

9.3 erase迭代器失效

（10）resize初始化

（11）普通拷贝构造

（12）=运算符重载拷贝构造

三、其他构造方法

（一）initializer_list初始化

（二）迭代器初始化

四、动态二维数组

---

vector的开始也代表STL学习的开始。接下来将讲解如何手动实现部分vector常用接口。

希望在看下面文章之前已经对string类的实现比较了解，或者看过我之前描述string类实现的文章，这样对理解vector会比较友好。

正文：

一、vector的成员变量

vector学习时一定要学会查看文档https://cplusplus.com/reference/vector/vector/，vector在实际中非常的重要，我们熟悉常见的接口就可以。

下面就不带大家看整个vector源码了，只截取了它成员变量在底层如何声明的小部分原码

下图可知vector原码核心成员变量就三个迭代器，迭代器跳转过去其实也是个typedef原生指针（和string类似）所以三个变量就是三个指针。再去看构造函数，它把三个指针初始化成空（不展示），那么之前数组都有大小，vector没有直接给出就进一步去看原码怎么算大小和容量的（不展示）。下面实现就模仿库的形式也定三个迭代器变量。

二、vector手动实现

类模版的声明和定义一般写在同一个文件下。创建一个vector.h（类实现过程）和test.cpp（接口测试），为了防止出现命名冲突，我外层套了一层命名空间zss，大家练习过程中可以不套。

下面是模拟原码实现的vector基础框架，成员就三个迭代器，vector本身是个顺序结构_start代表整个数组，_finish指向最后一个数据的下一个位置，_end_of_storage表示整个数组空间大小。

（1）构造

由于我们在声明的时候三个指针都给了缺省值nullptr，只要给缺省值了，用户不传参初始化列表会直接用缺省值初始化三个成员变量，所以我们提供的构造可以什么都没有。虽然什么都没有但是不能直接删掉，因为如果实现其他构造函数，要初始化三个指针还是得先走初始化列表。

（2）析构

到时候插入数据是需要自己手动new申请一段数组空间的，自己申请的空间析构也要对应匹配delete[ ]清理数据，并把指针置为空。

（3）尾插

push_back尾插之前必须确保有足够大的空间进行尾插数据，如果没有就进行空间的扩容，而要获取到数组空间大小用capacity()函数返回，顺便把size也求一下。由于扩容这一操作后面会经常使用所以封装成一个函数。

（4）扩容

reserve扩容采取深拷贝的思想，先开一段足够大小的tmp新空间，memcpy将旧空间数据一个字节一个字节拷给新空间，再将旧空间_start释放掉，把新空间tmp赋值给_start（reserve函数调用结束tmp自动销毁）最后更新一下_finish和_end_of_storage数据。

这里要注意的点是size()大小问题，大家看我还要再定个oldsize 变量存size()大小可能感到很奇怪，上面不是已经实现了size()函数，已经可以获取到数组大小了吗，怎么还多此一举存一下。

这里涉及到拷贝后_finish大小报错问题：

一开始我们计算的size()大小是还没替换空间前size的大小，替换空间后_start已经不再是原来空间而size却还是原来空间，两个不同空间的指针相加是会报错的，所以要用oldsize 变量存size()大小，这样_finish = _start + oldsize加的大小才是正确的。

（5）[ ]运算符重载

在数组的遍历中，最常用的就是[ ]、迭代器和范围for。内置类型下标遍历转换为解引用，自定义类型要实现下标遍历得重载运算法。有时候打印的数据具有常性不允许改变需要调用const版本，所以下面也实现了个const版本。

[ ]的实现：

5.1 迭代器的实现：

迭代器的实现也有分普通类型和const类型，const类型迭代器并不是在迭代器前面加个const就行，这是限制迭代器本身不能改变，而我们要的是数据不能改变，所以要typedef提供一个新的迭代器类型。

迭代器的行为是模拟指针并不代表它就是指针

使用：

范围for遍历：
范围for看起来很高大上，很便利，其实底层是依靠迭代器的实现，只要实现了迭代器范围for直接用。所以变层看似有[ ]、迭代器和范围for三种遍历方式，实际上只有[ ]和迭代器。

（6）尾删

pop_back尾删很简单，想象一下数组尾删是不是只要改变数组个数就好，同理vector尾删--_finish就行，到时候插入也是从_finish位置重新覆盖插入。

（7）插入

insert在任意位置插入一个元素，只要和插入有关都先考虑内存够不够问题，不够扩容。

如果是在中间插入是要把pos位置及之后数据向后移动一位再进行插入，移动利用迭代器更高效。

（8）删除

erase删除pos位置元素，同样利用迭代器将数据移动覆盖，最后--_finish个数。

要注意的是erase返回值还是一个迭代器，这是为了防止迭代器失效问题。

（9）迭代器失效

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。 对于vector可能会导致其迭代器失效的操作有：会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

9.1 reserve扩容迭代器失效

第一张图代码是一开始正常逻辑没修改过的代码，reserve内部会开新空间然后拷贝赋值销毁，通过调试看到，原本指向上面空间的_start指针指向了下面新开的空间，这些都很合理，但是insert在pos位置插入数据，这个pos还指向被销毁了的原空间，当下面while循环时it在新空间内向左移动找旧pos是永远找不到的。

遇到这种问题，要更新迭代器让pos指向新空间的原始位置，怎么计算就是：一开始要算出pos距离首元素大小，等扩容完了更新，请看第二张代码图。

9.2 insert后迭代器失效

VS默认insert后迭代器全部失效，这条没有解决办法，唯一的办法就是：别用！！！

9.3 erase迭代器失效

通过以下部分代码演示：删除数组中的所有偶数，在删除的过程中++it会使判断条件被跳过

图二：erase内部删除pos位置元素，后面元素会自动向前移一位，这时3覆盖2，但++it使3被跳过判断了。

图三：如果偶数在最后一个呢？_finish覆盖4，但又++it使结束条件直接跳过，野指针访问

图一                                    图二                                   图三

以上情况也是更新一下迭代器就行，erase有返回值只要重新接收返回值就OK

（10）resize初始化

resize的改变会影响数组的数据个数，数据不够就插入，太多就删数据，不够还空间不足就扩容+插入

第二个参数不是必须给的，当用户没给第二个参数时匿名对象初始化；int就是0，指针就nullptr

（11）普通拷贝构造

有两种写法v2(v1)和v2=v1，这两种都可以考虑复用写过的代码实现

（12）=运算符重载拷贝构造

现代写法：

一种很妙的写法，通过参数传递的浅拷贝思想和swap实现。v里面的数据等函数运行结束自动销毁，而我们想要的已经通过*this返回了。

三、其他构造方法

（一）initializer_list初始化

下面写法大家在刷题时是不是经常看到，这是C++11的一种构造方式，专门用于支持花括号 {} 初始化语法。它提供了一种统一的方式来初始化各种容器和自定义类型。

用法：

实现：复用reserve和push_back

（二）迭代器初始化

迭代器初始化引入了一个新概念，类模板的成员函数也可以是模板，这样不用固定整个类的迭代器，任意类型的迭代器都可以初始化了。

实现：还是复用了push_back，使整体代码更简洁

四、动态二维数组

vector<vector<int>>它本质上是一个二维动态数组，模版变量可以是任何类型的指针，当然也可以是vector<int>*指针类型。

想象 vector<vector<int>> 就像一组可以伸缩的抽屉柜：

外层 vector：这是一个大柜子，里面可以放很多抽屉（每个抽屉就是一个 vector<int>）

每个内层 vector：每个抽屉里可以放很多整数（int），而且每个抽屉的大小可以不一样

案例：力扣——杨辉三角

与静态数组对比的好处：

静态数组（如 int arr[3][4]）：大小固定、每行长度必须相同、内存连续

vector<vector<int>>：大小可变、每行长度可以不同、内存不一定完全连续（外层连续，内层各自连续）

完整vector手动实现代码如下：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace zss
{template<class T>class vector{public:typedef T* iterator;//const 迭代器typedef const T* const_iterator;size_t capacity()const{return _end_of_storage - _start;}size_t size()const{return _finish - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//1.构造//这玩意什么都不写也不能因为在声明给缺省值就删掉//因为自己实现了拷贝构造或者其他构造删掉就不是自动生成了//可能我们自己也会写其他构造initialize_list，允许用 { } 初始化对象vector(){}//13.initializer_list初始化vector(initializer_list<T> il){//走初始化列表把三个指针初始化了然后直接开空间尾插reserve(il.size());for (auto& e : il){push_back(e);}}//14.迭代器初始化//类模板的成函数模板，这样不用类的迭代器，任意迭代器都可以template<class InputIierator>vector(InputIierator first, InputIierator end){while (first != end){push_back(*first);++first;}}//2.析构~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//3.尾插void push_back(const T& x){if (_finish == _end_of_storage){//扩容//没有容量就通过capacity()函数获取一个reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}//4.扩容void reserve(size_t n){//可能reserve被单独调用所以再判断一次容量if (n > capacity()){//这里原本_start、_finish、_end_of_storage都指向同一块空间//拷贝了_start指向新的空间，你用两个不同空间指针相减不可能得到size//所以更新前保存一下size()size_t oldsize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * oldsize);//自定义类型string不能用memcpy，会指向同一块空间释放多次for (int i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}//5.[]T& operator[](size_t i){assert(i < size());return _start[i];}//6.const[]const T& operator[](size_t i)const{assert(i < size());return _start[i];}//7.尾删void pop_back(){assert(_finish > _start);--_finish;}//8.插入void  insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);//扩容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}//插入，因为是迭代器不存在没有小于0的情况iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}//9.删除元素iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}_finish--;return pos;}//10.迭代器失效处理//11.resizevoid resize(size_t n, const T& val = T()){if (n < size())_finish = _start + n;else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//12.拷贝构造v2(v1)vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//v2=v1//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		//如果有值先释放掉//		delete[] _start;//		_start = _finish = _end_of_storage = nullptr;//		//开新的空间//		reserve(v.size());//		//拷贝数据//		for (auto& e : v)//		{//			push_back(e);//		}//	}//	return *this;//}//现代写法void swap(vector<T>& v){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage,_end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}private://模拟STL库的实现iterator _start=nullptr;iterator _finish=nullptr;iterator _end_of_storage=nullptr;};
}

---

下次继续一起学习，感谢观看~