vector 手动实现 及遇到的各种细节问题
之前对vector的一些功能使用了一下 接下来手动实现一下vector vector的实现和string还是有不小区别的 有很多地方都有细节的问题
不同于string的成员变量一个指针一个size一个capacity的成员变量 vector里面存的是三个迭代器iterator 这的迭代器其实就是模版T的指针 这样就可以存各种类型的数据了
三个指针 statr指向第一个位置 finish指向最后一个元素的后一个位置 end_of_storage指向能存储容量的后一个位置
因为用到了模版 所以不能分两个文件来写 就都写到vector.h里面
接下来一步步实现vector的功能 在实际的过程中遇到了各种的问题 一步步分析并解决
容量操作
首先先实现简单的一些容量的接口
size和capacity只需要分别返回finish-start和_end_of_storage empty只需要判断finish是否等于start
reserve
如果按照string那样的方式如下图的方式来写reserve会出问题
这里的三个成员变量都是指针 扩容开新空间释放原来空间之后 需要让三个成员变量进行更新 _start和_end_of_storage按照上面写的没有什么问题 但是_finish的更新需要依靠size这个函数如下 此时_finish是更新前的 而_start是更新后的 此时相减就出问题了
解决方法
1. 先更新_finish 再更新start 先更新finish的话 此时的finish和start都指向原来的空间 size可以正常算 那么finish的就可以指向更新后的位置了
2. finish更新位置需要用到size 那么在更新start之前就提前算一下size并存起来到old_size中
有了reserve之后 我们就可以写尾插的函数了 先判断空间满没有 满了先用reserve来扩容 然后进行尾插并更新finish
形参用引用是因为 用传值传参的方式会进行拷贝构造 如果传的是自定义类型的话拷贝代价比较大 同时如果实参传递的时候传的不是变量而是1 2 直接的数字这种方式 此时的实参具有常性 如果这里引用的不用const修饰的话 相当于权限放大了 会报错
然后再重载[]之后我们就可以用下标的方式进行打印了
如下实现四个迭代器之后 我们就可以通过迭代器的方式和范围for的方式进行打印了 这些都和之前一样
insert
在string那里insert插入我们实现的是下标的方式 在上次vector使用中我们发现标准库中的insert只有迭代器的方式 所以这里也用迭代器的方式
如果按下图的方式进行insert插入的操作就会出问题 之后再对pos其实出的问题和之前reserve中_finish更新的问题相似 不过这里是pos的问题
下面来分析一下为什么会出现上述的问题
在insert插入之前 如果空间不够需要先扩容 扩容操作通过reserve实现开新空间和将三个迭代器进行更新 但是pos没有更新还是指向之前空间的某个位置如下图
而且扩容操作会把原来的空间给释放掉 此时pos位置指向的是被是否掉的空间 类似野指针 *pos=x操作是在原来空间的位置进行的 新的空间数据将原来数据拷贝之后 但是finish正常进行了++ 就导致还是最终会多打印一个数据 但这个数据为随机数
问题解决
我们知道出问题的原因和reserve那里类似 pos的位置还指向原来的空间
所以我们需要对pos的位置进行更新 在reserve更新之前存pos和_start相减的值 通过reserve更新空间及三个迭代器之后 再更新pos的位置 这样就可以正常的运行了
find可以查找传的两个迭代器区间内传的第三个参数 并返回该位置的迭代器
迭代器失效
有了insert之外再结合find 我们就可以选择在想要的位置进行插入了 如下图 find找到2的位置并返回给了pos insert再根据这个pos进行插入 但是在插入之后将pos进行*10的操作 没有将2*10 而是新插入的6*10了
这还是刚刚类似的问题 在insert函数里面pos位置插入数据后pos指向的还是原来的位置 这时候这个位置的数据是新插入的6了 也就是之前的通过find得到的pos失效了 pos的意义改变了
另一种失效问题
如下图先尾插4个数据 再在2的位置插入一个6 再对pos位置*10 这次这里什么都没有变 这里是在insert函数里面空间不够通过reserve扩容了 扩容了之后pos指向的还是原来的旧空间 刚刚我们更新pos是在insert函数里面对形参pos进行的 对于实参pos还是指向旧的空间 这种的其实就类似野指针一样
所以pos再使用一次之后就不要再次直接使用了
实际上对于pos的二次使用标准库中的vector在vs下这样都会直接报错（如下图） linux下gcc编译器不会报错 会和我们上面自己写的一样可以运行
解决方法
错误方式
既然是在里面形参改变没有影响实参 那么如果采用加引用的方式呢
采取这种方式 对于右下这种正常的写法就不能使用了（函数返回的临时对象具有常性 这里传过来相当于权限放大）
正确解决方法
insert返回pos+1的位置 pos每次使用之后更新它的位置 如下图就可以正常进行了 并符合我们的预期
在类外写一个Printf_vector函数 这里的x是被const修饰的 调用begin时候也是调用的const的版本返回值也为const类型的迭代器
但是这样只能打印int类型的 所以这里可以用模版函数的方式 如下图
但是这里会报如下图的错误
这是因为在类外用域作用符::访问类里面时候 可能访问的是类型 也可能是类的静态成员变量 编译器不知道是什么 这是规定 没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
解决方法
在前面加上typename就是告诉编译器我们访问的是类型 如果是要访问静态的那后面也不会有变量i
除了在前面加typename之外 也可以用auto来自动识别类型的方式解决
另外打印还可以如下 这样不只是vector可以打印 任意类型的容器用迭代器方式都可以打印
erase实现
如下图要用erase删除全部的偶数 迭代器it从begin开始每次判断该位置的值是不是偶数是就用erase删去然后it++ 一直到最后一个位置 但是结果不和我们预期的一样 会有以下两种问题
第一个报错了 第二个没有删干净
原因是这个代码如果该位置是偶数的话会把这个数给删掉然后后面的数在函数里面会向左移动 然后此时it指向的已经是下一个数据了 此时再++就跳过这个数据了 第二种情况就是这样
如果最后一个是偶数的话 把最后一个删掉之后此时it指向的就是finish了 但是还会++就跳过finish了之后再走也永远不会等于finish 第一种错误就是这样
解决
因为删除之后再里面就会自动移位了 所以如果删除的话不需要再移动it 为了分清也可以让erase返回pos位置的然后每次更新一下it 这样我们会更容易控制代码
resize
第二个参数之前string那里我们只需要一个字符 但这里是模版类的形式 第二个参数可能是内置类型的int double char都有可能 或者是自定义类型的 所以这里固定缺省值为某一个类型是不行的
这里缺省值用到了匿名对象的方式 对于自定义类型 这种方式就会调用他们的默认构造函数 但是这样子如果是内置类型怎么办呢 内置类型有构造吗
本来内置类型是没有的 但是为了支持类似这样的写法 就让内置类型也支持构造了 如下
而对于里面的处理
分为三种情况 n<size size<n<capacity n>capacity
对于第一种情况 直接改变_finish指向的位置就可以了
对于第二三中情况 不管哪种都直接reserve反正对于第三种情况也不会缩容 然后空间够了之后直接用迭代器finish位置到start+n之前都用val来填充就额可以了 在结束的时候finish的位置也刚好是它正确的位置
拷贝构造还是需要我们自己来写 不然默认的是浅拷贝 v2和v1指向的是同一块的空间 在我们写了析构函数之后 对于同一块空间就会析构两次就会崩掉 所以拷贝构造函数需要我们自己来写实现深拷贝
拷贝构造有以下两种方式来实现 第一种和之前的类似 先开空间再更新对应的成员变量 然后拷贝数据 第二种方式是用范围for的方式 范围for每一次从v1取一个值然后尾插给新的要创建的
这里要注意 如果我们自己写了拷贝构造 编译器默认的构造就不能使用了 我们需要自己来写一个默认构造函数(无参的或者全缺省的) 或者使用强制调用编译器默认构造的方式
对于以下自己实现的无参构造函数
这里的具体过程是 在声明位置我们把三个成员变量都=nullptr的方式了 在调用函数里面内容之前会先用初始化列表把三个成员变量都初始化为空指针 然后才会进入函数里面 如果大于0执行下面的逻辑 如果等于0再经过初始化列表全部初始化为空指针就结束了不会再进行下面操作
赋值
下面这种方式和构造类似 不过之前可能有数据 先用clear把原来的数据给清理掉
还用另一种的方式 如下图
直接把传的形参和现在的进行交换 这里要注意两个点
一个是形参不能为引用了（这里要交换 不能把原来的实参给改变了）
另一个是这个swap我们最好自己来实现一下 std库里的swap为了让各种类型都可以用 用模版的方式 在里面的实现用的是简单粗暴的 创建新变量c存a 然后a=b b=c这种方式
对于内置类型没有什么大的消耗 但是对于自定义类型也这样的话 里面有很多的数据 需要进行三次拷贝构造 代价就很大了 所以我们最好自己写一个swap的函数 如下图二我们自己写的 只是把两个对象的三个指针进行了交换
在类模版里面也可以写一个函数模版 它既是类模版的成员函数也是函数模版 如下面的函数模版写在类模版中 这样就可以支持各种类型的迭代器来初始化vector对象
如下图v1用vector类型的v的迭代器进行初始化 v2用list类型的l1进行初始化
但是用其他类型迭代器初始化的时候 如这里的v2 l1里面需要存的也是int类型或者是可以转换为int类型 这样才可以进行初始化
像这样在类模版里面再写一个支持各种类型的迭代器使用的函数模版 如果我们想把list对象排序 在list中排序不方便我们就可以放到vector中这样的函数模版 来排序
写了这个之后 我们使用之前写的两个参数的构造函数初始化的时候又会报错
为什么呢
如下图 两个都是构造函数 如果是用左边的 两个形参类型可以直接都实例化为int 而对于右边第一个参数需要从int到size_t类型的隐式转换 所以会调用左边的 而对于int类型在左边进行解引用操作就会报错了
解决方法
1.在传值的时候指定类型 如这里在10后面加一个u 代表该整数是unsigned类型 就会匹配第二个构造函数了
2.再写一个构造函数第一个参数为需要的类型 就会优先匹配这个构造函数了 实际上的std库中vector实现就是用到这种方法 写了多个这样的构造函数
.
最后reserve其实还存在一个问题
如上图 如果vector里面存的是自定义类型 在push_back里面空间不够会调用reserve reserve里面扩容是通过开新空间拷贝数据释放原来空间的方式 这里拷贝用到的是mercpy 是按字节拷贝的 对于内置类型不会出什么问题
但是如果是自定义类型的话 只能进行浅拷贝 把string里面的指针给拷贝了过去 然后释放原来空间时候会先把原来空间中指向的字符串空间先给全部释放了
如下图 原来vector存着四个string类型 每个string里面有一个指针指向堆区动态申请的空间 在开新空间之后用memcpy的方式只会把每一个string对象的指针和size cpapcity给拷贝过去 然后对于原来的空间会先把string对象str指向的空间给释放掉再释放掉旧的空间 此时新空间中存的指针指向的空间是已经被释放掉的空间
解决
不用memcpy的方式 而是对vector中每一个数据直接赋值的方式 对于自定义类型如string 就会调用string的赋值运算符 会自动开一块新的空间 然后把内容拷贝过去
