我们之前讲了vector的接口,我们今天来看一下vector的底层的实现:
在gitee上面我们的这个已经实现好了,我们看gitee就可以:vector的实现/vector的实现/vector的实现.h · 拾亿天歌/拾亿天歌 - 码云 - 开源中国
我们在这强调比较难的知识:
迭代器失效:
首先是插入函数:insert:
我们看上面的是我们的插入函数的实现:
我们进入到函数以后先判断一下这个pos位置是不是合法的,然后看内存满了没有,如果满了的话,我们就进行一下扩容:
扩容完后我们设置一下我们的迭代器:(我们的迭代器可以看作是一种指针);
我们的_finish指的是我们的最后一个数据的下一个位置;
//也就是我们的_finish指向的不是一个有效的数据。
我们把迭代器it设置为我们的最后一个数据:
然后把pos及后面的所有的数据全部往后移动一位,最后把数据插入到pos位置。
我们的这个代码看起来都非常的好,但是这里会出现一个我们的迭代器失效的问题:
我们先看一下我们的reserve函数:
我们的上面的三张图片组成了我们的reserve函数:
我们看我们的函数,当我们要扩容的时候,我们给我们的函数传n进去,我们进行扩容,我们开辟新的内存空间,然后把原来的内存空间里面的数据拷贝过来,然后我们再把原来的内存空间释放掉;
看起来似乎没问题:
我们再看这两张图片,这个就是我们的刚才的insert函数,然后我们看,我们把pos位置及以后的数据全部往后移动一位以后,我们在pos的位置上插入数据,最后完成。
但是实际上,我们在扩容结束以后,我们在我们的reserve函数里面,我们把数据都拷贝了过来,然后把原来的数据释放掉,并且更新了我们的三个指针的指向,但是有一个问题,我们的指向pos位置的迭代器指针,我们是从我们的insert函数我们就传了过去,我们的pos的迭代器指针是指向我们的原来的内存的,但是我们的扩容,我们并没有对我们的pos指针进行更新。我们的新的内存是没有pos的。
这时候我们的pos迭代器指针还是指向我们的已经被释放掉的内存空间中,已经开辟好的内存空间里面根本没有我们的pos,这时候他们进行比较这就是有问题的。
那有没有办法来解决呢?
有:
我们把之前的扩容的部分我们进行一下添加,我们把他替换成上面的部分;我们把pos位置也进行一下更新;这时候我们的insert就没有问题了。
我们接着看下一个erase接口:
这个接口的问题其实还是迭代器失效:
我们看我们的这个erase函数接口:
这个是我们的erase函数接口:我们看我们的这个函数,我们的这个函数表示的是把我们的pos位置的数据进行删除,我们还是进到函数里面先判断我们的pos位置是不是合法的。
然后我们设置一个迭代器,设置的位置时我们的要删除的位置的下一个位置,然后我们把我们的这个位置和以后的数据统一的往前面的移动一个位置。
最后我们的_finish--;有效的数据减少一个;
这个函数接口的迭代器失效是什么呢?
我们看我们的这个代码:我们的这个代码设置一个迭代器,然后我们遍历我们的v对象,我们的要求是把所有的偶数删除,
我们的开始的数据时1,2,3,4,5,6,7。
我们的代码执行以后是有问题的。
这是为什么呢?这个就是我们的erase的迭代器失效;
我们看我们的上面的代码:
我们的vs表示的是我们的erase函数,我们的迭代器it指向的位置删除以后,我们的迭代器it就会失效,我们的库里面的erase函数接口会返回我们要删除的位置的下一个位置的迭代器,虽然我们的it迭代器失效了,我们的it下一个位置返回来了,我们看我们的上面的函数:
让我们的这个函数不是偶数的时候,我们的迭代器就++的往后面移动,但是如果这个数就是偶数的时候,我们就调用erase函数来进行删除,但是我们删除以后,我们的it就不能用了,,,我们就可以给我们的it再次的进行赋值,我们把数据删除了,我们的函数就返回了要删除的下一个位置的迭代器;我们再赋值(这就把我们的迭代器it给更新了);然后继续循环。
传值传参和传值返回:
我们看我们的这个函数,我们的第二个参数是我们的模板T的引用,我们的这里的参数为什么不传值过来,却传引用呢?
因为我们的类是一个模板类,我们不确定里面的T是什么类型的,我们可以实例化出任何的类型,如果是int之类的内置类型的类,我们的这个传值或者是传引用都是可以的。
但是如果是自定义类型的话,或者是string,vector之类的话,我们的传值传参会调用他的拷贝构造,这些自定义类型的拷贝构造,如果是自己实现的话,他是会发生深拷贝的,如果是没有写,编译器自己实现的话,实行浅拷贝,我们的自定义类型在这里我们就认为他会产生深拷贝,,,这时候发生深拷贝的代价是比较大的。
所以我们会选择传引用传参,这时候就不会调用拷贝构造;
我们接着来看:
构造函数的实现:
我们来看一下我们的构造函数的实现:
我们的构造函数的第一种是三个成员变量都在初始化列表设置为nullptr;
我们的这种构造函数没有参数,(没有参数,或者参数全部都是缺省值,或者是不写构造函数,这三种是我们的默认的构造函数)。
这个是我们的第二种构造函数,我们的这个构造函数表示的是我们的vector里面的指针指向的数组的数据是n个val值。
我们再看我们的第三种的构造函数的方式:
这种构造函数的构造,我们是使用initializer_list<T>来进行的。
这个就是我们的这种构造函数的用法,我们要什么数据我们直接写到我们的花括号里面就可以了。
析构函数的实现:
这个是我们的析构函数,我们的这个析构函数不难。把内存释放掉,指针置为nullptr就可以了。
拷贝构造的实现:
这个是我们的拷贝构造函数,这个拷贝构造函数,我们的构造函数如果第一个参数是我们的类类型的引用,这个就是拷贝构造函数。
我们的这个函数是把我们的对象v1里面的数据拷贝给我们的this,我们必须是要自己实现拷贝构造函数的,如果我们不自己实现拷贝构造的话,我们的编译器默认生成的拷贝构造函数实行的是浅拷贝,,这个浅拷贝的话,(他是直接把对象v1里面的三个成员变量指针直接拷贝一份给你),这就导致了我们的*this里面的三个指针和v1里面的三个指针指向的都是同样的内存空间,
就跟这个一样,那么这样的结果是什么呢?当我们的对象的声明周期结束的时候,他就会自动的调用析构函数来进行析构,如果我们的两个对象指向的内存是同一块,我们是不是会把这块内存析构两次。。。
所以我们就必须自己实现拷贝构造,实行深拷贝。
赋值重载的实现:
我们的这个图片里面的复制重载:
v1相当于是*this,v2相当于是形参对象v。
我们接着来实现我们的复制重载函数。
首先我们区分一下函数重载和拷贝构造:
拷贝构造是一个已经存在的对象和一个正在进行初始化的对象,把这个已经存在的对象给另一个正在初始化的对象来进行初始化。
复制重载是两个都是已经存在的对象,我们被其中一个对象赋给另一个对象;
首先我们看我们的这个参数,我们的这个函数的参数是我们的类类型的对象,我们之前一直说我们传参的时候我们尽量传引用,传值的话它会调用拷贝构造,拷贝构造的话,深拷贝消耗是比较大的。
我们这里要实现的是复制重载,这个函数我们的目的是把一个对象赋给另一个对象,但是我们的对象里面是含有内存的,那么我们把一个对象赋给另一个对象,我们当然不仅仅是把对象里面的成员变量指针给拷贝一份给另外的一个对象;(必须是深拷贝,不然的话就会发生重复的析构的问题)
所以我们这里的参数是一个传值类型的,会调用拷贝构造(他就会再把原来的内存拷贝一份给我们的形参v,然后我们的this指针调用swap交换函数,把*this和v进行交换,把他们的内存进行交换,然后我们的*this原本的内存就到了形参对象v里面去了,然后我们的拷贝构造得到的v里面的内存就到了*this里面,这时候我们函数结束,我们的对象v生命周期结束,调用析构函数,来把v内存释放掉)。
最后:
我们接着来看:
我们看我们的扩容reserve的函数接口:
我们的这个函数接口也不太对。
我们的这个类我们实现的是一个模板类,里面的T是什么类型的我们不知道,他可能是int类型之类的内置类型,也可能是自定义的类型,这个时候我们的扩容的函数里面的扩容方式是memcpy拷贝,我们看下面的图片:
我们看这个图片,当我们的模板T是自定义的类型的时候,这个时候我们的每个元素里面的数据就和我们的图片中的一样,我们的每个元素都有一个参数,这个参数是我们的指针,指向一个数组,但是我们的memcpy是怎么拷贝的,他会把上面的数据拷贝一份过来,但是,我们的数据不是内置类型是自定义类型的时候,就会发生和我们的上面的图片一样的事情,我们会把指针拷贝一份过来(浅拷贝),这时候原本的内存里面的每个元素里面的指针和新的内存里面的每个元素的里面的指针指向的内存是同一个内存。
然后我们再看这个代码,我们在memcpy拷贝完成以后,我们就会把原来的内存空间释放掉,原来的内存释放的话,里面的数据类型是自定义类型就会调用他们的析构函数,就会把他们里面的指针指向的内存释放。这时候新的内存里面的数据里面的指针就成了野指针了。