在查看STL库里面vector的实现时,我们发现它是一个类模板并且定义了三个成员变量,分别是
iterator start
、iterator finish
、iterator end_of_storage
用来标记开始,结束,以及总容量,对于vector来说其迭代器iterator就是T*
,例如我们之前学习过的顺序表插入的是int类型的数据,所以对存放int类型的vector来说T*
就是int*
如下图所示: 假设vector里已经插入了6个数据
因为还没有写构造函数,所以成员变量那里先给缺省值,方便使用
这里将vector的实现都放在一个头文件下,放置多个文件可能会出现链接错误;并设置自己的命名空间tutu
插入数据首先都应该判断一下容量是否够用,不够用就需要扩容,这里使用reserve()函数扩容,该函数将在后面实现,此外插入数据后
_finish
要往后偏移一位
🥳🥳有关容量和数据个数的函数:
扩容时,因为我们使用的实现vector类的成员变量是指针(或者说迭代器),所以改变空间后不仅仅_start改变,_finish指向的空间会被销毁,所以这时候如果再使用扩容后的_finish-_start来找到容量size来确定现在_finish指向的空间肯定是不对的,所以我们要提前记录好oldsize
这里拷贝数据使用的是
memcpy
,一个字节一个字节拷贝
这里返回的是T的引用,也就是vector里面存储的数据
结果如下:
可以看到尾插成功,并且可以使用[]来访问vector v1里面的元素
在最开始vector成员变量那里我们将T*typedef成iterator,所以对于vector类来说其迭代器实质上就是
T*
,是一个指针;但要注意不是所有的迭代器都是指针,例如list的迭代器就不是,我们后续再学习
提供给const对象使用的迭代器,指向的内容不可以被修改
使用迭代器来遍历数据
结果如下:
因为我们这里的迭代器实质上就是
T*
,所以vector<int>::iterator it = v1.begin();
也可以写成这样:int* it = v1.begin();
,但是最好还是使用第一个,因为这个是在所有的地方通用的,屏蔽了底层实现,体现了C++的封装的思想
此外范围for其实质上就是通过迭代器来实现的,所以我们写完了迭代器就可以使用范围for来遍历数据了,代码如下:
这里要注意迭代器因为扩容导致pos失效的问题(野指针),所以要提前规避,记录好pos相对位置,然后再即时更新pos迭代器,否则就会出现随机值;
此外,insert的参数pos是对实参的拷贝,形参的改变不会影响实参,所以外部的实参也会失效,但是我们也不能通过引用传参,因为其迭代器返回的是临时拷贝具有常性不能通过引用传参,所以这里我们就可以通过控制insert函数的返回值来解决,我们会返回更新后的迭代器,这样就可以访问该位置了
🥳🥳有了插入函数之后尾插push_back()就可以使用insert()来实现啦,代码如下:
erase()之后迭代器失效问题
所以我们认为删除操作之后迭代器也会失效,和插入函数一样通过返回迭代器来更新迭代器使用才行
结果如下:
结果如下:
这里使用了函数模板用来匹配不同类型的迭代器,因为vector可以存储不同类型的数据,相应的迭代器也会有所不同,所以使用函数模板
注意这里给的缺省参数是匿名对象
T()
,而不是0,因为vector除了能存储int类型外还可以存储其他类型的数据比如string等
结果如下:
上述代码s1使用的是缺省值匿名对象string()也就是’\0’,所以什么都没打印,第一行是空的,第二行打印s2的10个"hello"
但是当我们使用下面的代码测试的时候就会发现:
运行后:
出现了非法的间接寻址,并且报错在
vector(InputIterator first, InputIterator last)
迭代器区间初始化这里这是因为编译器在匹配函数时
vector<int> v1(4, 2);
4和2都是int类型恰好和vector(InputIterator first, InputIterator last)
这两个函数模板的参数匹配上了,而我们写的n个val初始化vector(size_t n, const T& val=T())
第一个参数类型是size_t,第二个才可以隐式类型转换为int类型,没有迭代器区间初始化的函数匹配所以编译器会选择使用迭代器区间来初始化v2,但是迭代器区间初始化函数里面写了解引用,对于int类型来说是行不通的,所以出现了错误
这时我们只需要在初始化v2时将第一个参数给为unsigned int就行:vector<int> v1(4u, 2);
或者可以在重载一个n个val构造的函数,第一个参数给为int
类型:
这样上述代码的结果就如下:
initializer_list是C++新增的一个类型,方便初始化,支持将花括号括起来的值给initializer_list,initializer_list对象里面有两个指针,指向花括号里面值开始和结尾的下一个,并支持迭代器,所以可以使用范围for来遍历,当然这个要编译器支持将花括号传给它
C++11引入
结果如下:
这里使用传值传参,是实参的拷贝,所以我们将它与被赋值的对象交换后返回即可完成赋值,并且交换后形参生命周期结束就会自动调用析构函数释放原来的空间
🥳🥳swap函数
结果如下:
可以看到程序异常退出,这是因为我们在使用reserve()扩容时,使用的是
memcpy(tmp, _start, oldsize*sizeof(T));
来拷贝数据,如果数据是int类型不会有什么问题,但如果是string类,memcpy进行的是一个字节一个字节拷贝,是浅拷贝,释放原来的空间后,就会存在野指针,访问已经释放的空间出现错误,所以reserve实现应该如下:
上述代码拷贝使用赋值,如果是类类型会调用赋值运算符重载实现你想要的拷贝,这样上述测试代码就可以测试成功啦🥳🥳
结果如下:
以上就是C++STL标准库中vector的模拟实现了,在实现过程中,我们使用了动态内存分配来实现vector的大小动态调整,并通过指针来管理内存。我们还实现了一些常用的成员函数,如push_back、pop_back、at等,以及一些运算符重载,如[]、=等。 通过实现这个简单的vector类,我们不仅加深了对vector容器的理解,还学习了一些C++的底层原理和技巧。同时我们也遇见并解决了一些问题比如迭代器失效,深浅拷贝…以上就是今天所有的内容啦~ 完结撒花 ~🥳🎉🎉