vector模拟实现【C++】
文章目录
- 全部的实现代码放在了文章末尾
- 准备工作
- 包含头文件
- 定义命名空间和类
- 类的成员变量
- 迭代器
- 迭代器获取函数
- 构造函数
- 默认构造
- 使用n个值构造
- 迭代器区间构造
- 解决迭代器区间构造和用n个值构造的冲突
- 拷贝构造
- 析构函数
- swap【交换函数】
- 赋值运算符重载
- empty
- size和capacity
- operator[]
- reserve【调整容量大小】
- resize【调整size大小】
- push_back
- assign【把所有数据替换成迭代器区间中的数据】
- insert
- 为什么扩容会导致pos迭代器失效？
- 为什么要返回pos-1？
- erase
- 为什么要返回pos？
- 全部代码
全部的实现代码放在了文章末尾
准备工作
创建两个文件，一个头文件myvector.hpp，一个源文件 tesr.cpp
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件myvector.hpp中】
-
mystring.h：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义
-
test.cpp：存放main函数，以及测试代码
包含头文件
-
iostream：用于输入输出
-
assert.h：用于使用报错函数assert
定义命名空间和类
在文件myvector.hpp中定义上一个命名空间myvector
把vector类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题
类的成员变量
参考了stl源码中的vector的实现
成员变量有3个，都是迭代器
画图理解一下
迭代器
迭代器
因为存放数据的空间是从堆区申请的连续的内存，且只是简单模拟
所以我用了指针T*作为普通迭代器，const T*作为const迭代器
【T是vector中存储的数据的类型】
直接把T*重命名为iterator，把const T*重命名为const_iterator就完成了迭代器的实现
迭代器获取函数
因为const修饰的对象只能调用const修饰的成员函数
所以如果是const修饰的对象调用begin()和end()的时候，就会自动调用到const修饰的begin和end.
构造函数
默认构造
因为stl库里实现的默认构造是没开空间的，所以默认构造直接让3个成员变量都为nullptr就行
直接在声明的时候给缺省值，缺省值会传给成员初始化列表
即
而成员初始化列表会比构造函数先调用
并且每个构造函数调用之前都会先调用成员初始化列表，这样不管调用哪一个构造函数初始化，都会先把3个成员变量初始化成nullptr
使用n个值构造
迭代器区间构造
解决迭代器区间构造和用n个值构造的冲突
当重载了迭代器区间构造和用n个值构造的时候
如果传入的两个参数都是int类型的话就会报错
为什么？
因为在模板函数构成重载时，编译器会调用更合适的那一个
什么叫更合适？
就是不会类型转
如果传入的两个参数都是int类型，那么调用的应该是使用n个值构造，因为没有int类型的迭代器
但是使用n个值构造的第一个参数是size_t,int传进去要隐式类型转换
而调用迭代器区间构造，两个int的实参传进去，就会直接把InputIterator推导成int，不会发生类型转换，所以编译器会调用迭代器区间构造
解决方法：
再重载一个使用n个值构造的函数，把第一个参数改成int
拷贝构造
因为成员申请了堆区空间，所以要深拷贝
【不知道什么是深拷贝的可以看我这篇文章：类和对象【三】析构函数和拷贝构造函数】
析构函数
swap【交换函数】
因为存放数据的空间是在堆区开辟的，用3个成员变量去指向的
所以直接交换两个对象的成员变量就可以了
不需要拷贝数据
赋值运算符重载
因为成员申请了堆区空间，所以要深拷贝
【不知道什么是深拷贝的可以看我这篇文章：类和对象【三】析构函数和拷贝构造函数】
为什么上面的两句代码就可以完成深拷贝呢？
这是因为：
使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝
在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束
obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁
empty
size和capacity
operator[]
因为
const修饰的对象只能调用const修饰的成员函数
所以const对象只会调用下面的那个重载
reserve【调整容量大小】
resize【调整size大小】
push_back
assign【把所有数据替换成迭代器区间中的数据】
insert
iterator insert(iterator pos, const T& val) { assert(pos 记录一下扩容前的pos与start的相对位置 因为扩容的话会导致pos迭代器失效 size_t n = pos-_start; if (capacity() == 0) 如果容量为0 reserve(2); else 容量不为0，就扩2倍 reserve(capacity() * 2); 更新pos pos = _start + n; } iterator it = end()-1; 把pos及其之后的数据向后挪动一位 while (it = pos) { *(it + 1) = *it; it--; } _finish++; *pos = val;插入数据 返回指向新插入的数据的迭代器 用于处理迭代器失效问题 return pos-1; }为什么扩容会导致pos迭代器失效？
因为扩容之后原来的空间被释放了
又因为使用的扩容方式是reserve所以那3个成员变量的值扩容后可以指向正确的位置。
但是pos如果不更新的话，就还是指向被释放的空间，就成了野指针了。
更新方法也很简单，保存扩容之前的pos与start的相对距离n，扩容之后再让pos=_start+n就可以了。
为什么要返回pos-1？
这是stl库里面处理迭代器失效的方法之一
因为我们在使用stl库里面的insert函数的时候，是不知道什么时候会扩容的【每个平台实现的vector是不同的】
只能默认使用了之后传进去pos，在调用一次insert之后就失效了，失效的迭代器是不能使用的。
所以如果还要用pos就要把它更新一下，stl库里提供的更新方式就是：
==让pos接收insert的返回值。【pos是传值调用，形参改变不影响实参】==并且规定insert的返回值要是指向新插入的数据的迭代器
erase
为什么要返回pos？
因为使用了erase之后的迭代器也会失效，需要提供更新的方法
为什么使用了erase之后的迭代器会失效？
- 不确定是否删除到一定数据时，会不会减小容量，以适应size
此时和insert的一样，因为不能部分释放，所以会把原来的空间释放掉，申请新空间
- 不确定是否删除的是最后一个数据，如果是那么调用完erase之后pos指向的就
不是vector的有效数据范围了
所以和insert一样，调用了erase之后如果还要使用pos，就要接收返回值。
stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器，因为挪动覆盖的原因，下一个数据就是pos指向的数据，所以返回pos【没有接收返回值的迭代器，在检测较严格的编译器中，不管指向的位置是否正确，都会禁止使用，使用了就报错】
全部代码
#include #include using namespace std; namespace myvector { template class vector { public: typedef T* iterator; typedef const T* const_iterator; vector() { } vector(size_t n,const T& val=T()) { _start = new T[n];//从堆区可容纳申请n个元素大小的空间 _finish = _start;//还没有 有效数据 时start与finish重合 _end_of_storage = _start + n;//指向最大容量 的 下一个位置 for (size_t i = 0; i capacity())//要调整的容量n，大于capacity才扩容 { size_t origsize = size();//记录扩容前的size T* tmp = new T[n];//申请空间 //把原来的数据拷贝到 新空间 for (size_t i = 0; i tmp[i] = _start[i]; } delete[] _start;//释放旧空间 //让成员变量指向 新的空间的相对位置 _start = tmp; _finish = _start + origsize; _end_of_storage = _start + n; } } void resize(size_t n, const T& val = T()) { if (size() == n)//如果size与要调整的n相等 return;//直接返回 else if (size() 0); _finish--; } template void assign(InputIterator first, InputIterator last) { delete[] _start;//释放原来申请的空间 //把3个成员变量置空 _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; while (first != last) { //一个一个尾插进去 push_back(*first); ++first; } } iterator insert(iterator pos, const T& val) { assert(pos //记录一下扩容前的pos与start的相对位置 //因为扩容的话会导致pos迭代器失效 size_t n = pos-_start; if (capacity() == 0)//如果容量为0 reserve(2); else//容量不为0，就扩2倍 reserve(capacity() * 2); //更新pos pos = _start + n; } iterator it = end()-1; //把pos及其之后的数据向后挪动一位 while (it = pos) { *(it + 1) = *it; it--; } _finish++; *pos = val;//插入数据 return pos-1; } template void insert(iterator pos, InputIterator first, InputIterator last) { assert(pos in++; len++; } if (_finish + len = _end_of_storage) { size_t n = pos - _start; if (capacity() == 0) { reserve(len); } reserve(capacity()+len); pos = _start + n; } iterator it = end() - 1; while (it >= pos) { *(it + len) = *it; it--; } _finish+=len; it = pos; while (it != pos + len) { *it = *first; it++; first++; } } iterator erase(iterator pos) { // 防止传入的pos 是越界的 assert(pos -
