库中如何实现vector

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:模拟实现STL库中的vector部分接口,帮助大家更好的理解vector.

vector 底层框架

在这里插入图片描述

我们模拟实现的时候,其中成员变量可以采用缺省值方式更加方便.

一、构造函数实现:

(1) 默认构造函数

由于我们已经给出了缺省值,所以可以不必要用初始化列表.

(2) 初始化为n个值

本应该开空间,然后再将数据插入进容器vector,此处我们复用resize函数的一种.就不需要自己再手撕一遍了.

(3) 迭代器区间初始化

因为迭代器可能是原生指针,比如:数组的地址区间 也可能是别得复杂的迭代器,例如: vector<string>,这里采用再套一层模板,这样无论是什么形式的迭代器,总支持迭代++和 迭代区间[begin,end)

需要理解迭代器的特性.

(2) 拷贝构造 (重点,重点,重点)

拷贝构造是一种使用很频繁的构造方式,这里还存在一个复杂的问题: 外部深拷贝,内部浅拷贝的复杂问题.

方案1

普通类型使用此方案的拷贝构造没有问题.

运行结果:

v3=1 3 4 5 6 7 8 98 100 11 v4=1 3 4 5 6 7 8 98 100 11

但是对于稍微复杂的类型,成员本身也有动态开辟空间,例如:string类时

在这里插入图片描述

为什么运行不起来,会报错呢? 因为, _start = new T[v.capacity()]; 使得外部的确完成了深拷贝,使得v1和v2的_start 指向了不同的空间.

但是像string类的成员自己也有动态申请空间,而内部采用 memcpy(_start, v._start, sizeof(T)*v.size()); 则是按值进行的浅拷贝.

在这里插入图片描述

方案2:

_start[i] = v._start[i];(重点) 这可不是简单的赋值,而是调用了自己的(这里是string类)的赋值运算符重载,这就完成了内部的深层拷贝.

运行结果:

二、容量操作

这两个函数比较简单,可以根据文章开头的vector底层框架结构图分析,计算方式是根据这样设计的.

(1) size()与capacity()

(2) reserve() (重点)

resize:改变容量大小

在这里插入图片描述

此时,我们发现_finish 初始是nullptr 经过_finish = _start + size()之后,_finish 依旧是nullptr,为什么?

解释:

因为此时_start已经指向新空间了,而size=()函数计算方法是 return _finish - _start; 此时size=_finish - _start 等价于 nullptr - _start= -_start 执行_finish=_start+ (-_start)= nullptr

解决方案: 将size()保存一份,即当执行 _finish = _start + size(); 时,size是用sz也就是_start没有指向新空间时已经计算好的长度.

(3) resize()函数

此处画图理解为佳.

在这里插入图片描述

if (n > size()): 先判断是否需要扩容, 再从_finish 位置开始,往后填充数据即可

三、修改与访问操作

(1) 迭代器:

(2) 元素访问[]

注意判断pos位置是否合法.不需要考虑pos小于0,因为类型是size_t .

(3) push_back与pop_back

在进行插入操作之前,先考虑是否需要扩容. 扩容逻辑需要注意,很可能初始状态capacity=0,所以要先判断一下是否是0再进行1.5倍或者二倍扩.

其次,_finish 指向的正是有效元素的最后一个位置,即是尾插时待插入元素的位置.

(4) swap

借助算法库中的swap()函数,交换三个指针即可.

(5) insert 与erase

需要注意的是判断pos位置是否合法.

试着画图分析如何移动数据.

本篇只是简单的模仿库中完成部分接口的实现,目的是帮助大家更好的理解vector.

今天就分享到这里了,下次见.