海外医疗兼职网站建设,阿里巴巴网站怎么做推广方案,网站开发进入腾信职位,口碑营销5t理论目录
前言#xff1a;
1. vector结构
2. 默认成员函数
2.1 构造函数
无参构造#xff1a;
有参构造#xff1a;
有参构造重载#xff1a;
2.2 赋值运算符重载、拷贝构造#xff08;难点#xff09;
2.3 析构函数#xff1a;
3. 扩容
3.1 reserve
3.2 resize…目录
前言
1. vector结构
2. 默认成员函数
2.1 构造函数
无参构造
有参构造
有参构造重载
2.2 赋值运算符重载、拷贝构造难点
2.3 析构函数
3. 扩容
3.1 reserve
3.2 resize
4. 插入删除
5. 迭代器操作 前言 本篇文章模仿的vector与STL源码并不完全一致例如本文直接通过new来开辟空间但是源码中通过内存池分配但是这并不影响彼此之间的关系所以本篇文章还是有一定的学习意义的。
1. vector结构
模板 templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; } 我相信如果大家用过vector的话一定是知道每一次使用vector都需要标注清楚这个类是用来存储什么样的数据的例如 vectorint vv1; 存整型数据 vectordouble vv2; 存浮点型数据 vectorvectorint vv3; 存存整型数据的vector数据 所以我们模拟的vector类就不能单独面向某一种数据而是应该考虑到所有的类型就算是一直自定义类型嵌套也能实例化出来如下 vectorvectorvectorvectorvectorint vv4; 虽然上述的类型对于我们来说估计这辈子都不会遇到但是我们总不能防止某些好奇心重的小伙伴搞事所以是必须要能够支持这种写法的就像是为了满足到酒吧点炒饭的帅小伙。 所以首先得出结论我们的类需要被构建成模板类。
成员变量 上面代码中可以看到我们的成员变量的类型是自定义类型重定义iterator也就是平时我们熟知的迭代器我们的迭代器实现又是指针的方式所以可以将这三个变量理解为我们存储数据空间的三个位置。_start对应开头_finish对应数据结尾_end_of_storage对应空间容量的最后位置。也即是对应我们顺序表的size和capacity。
2. 默认成员函数 每当我们实现一个类默认成员函数是必不可少的特别是像是我们vector这样需要向堆申请空间的类。
2.1 构造函数
无参构造 无参构造可以说是非常简单了我们甚至连空间都不需要开辟只需要通过初始化列表为我们的三个迭代器变量初始化即可如下
//默认构造方式全指针都置空值后续无论怎么插入都有扩容为指针赋值
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{} 可能有朋友要问那用这种方式不就表示了自己之后不能插入数据之类的吗事实不是因为我们还有其它的函数接口为我们服务大家看下去就明白了。
有参构造 有参构造咱们就与库保持一次既然它不支持通过一个值直接去初始化而支持通过n个T类型数据去构造那么我们也这样学习它这样 看不懂上面的库实现方式没事看我的也是一样
//有参构造n个T类型的数据进入vectorint
vector(size_t n, const T va T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{T* temp new T[n];for (size_t i 0; i n; i){//这里赋值操作是T和T之间的操作temp[i] va;}_start temp;_finish _start n;_end_of_storage _finish;
} 这里的构造也是一样需要通过初始化列表先将三个迭代器变量初始化空指针因为我们不能保证有没有小聪明蛋给n赋值为0去初始化其次就是我这里使用了T()这样的匿名对象作为缺省参数。 有同学在这里就要问了T()这样的匿名对象生命周期不是只有一行吗你这代码都多少行了还在用不是错的吗 其实不是在C当中当我们用const加引用类型的变量去接收匿名对象会改变匿名对象的生命周期为这个变量的生命周期长度如下 const int ret T(); 改变T()的生命周期为ret T(); 生命周期只有一行 值得注意的是上面的const是必须加的因为我们的T()属于本身是属于临时对象的而临时对象又有常量属性也就是不可更改属性。如果不用const接收那么就会导致错误。 有点意思的是不加const在vs2013及其之前的版本都是不报错的后续版本我不清楚但是到了vs2019这个BUG就被修复了。
函数设计 这里的代码我用了最全面的写法后面可以通过函数复用的方式直接究极简化。 首先通过new向堆申请n个T类型的空间这里不能使用malloc这种C语言的申请方式原因我相信大家也明白就是因为我们要实现模板类那必然有可能使用自定义类型有自定义类型要就要去调用它的构造函数只有new才能实现malloc不行。 T* temp new T[n]; 然后通过循环不断的赋值最后为三个迭代器变量定位即可这里循环体中的赋值操作涉及了很复杂的嵌套操作绝不是简单的一行代码等到下一小节重载赋值运算符我再来讲。
有参构造重载
vector(int n, const T va T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (n--){push_back(va);}
} 该重载的函数体就是我所说的究极优化的方式通过尾插函数不断的复用就实现了函数功能但是重点不在这里我重载这个函数的意义在于为我们的迭代器区间构造函数服务。 为什么这么说请先看迭代器区间构造函数。
templateclass InputIterator
vector(InputIterator start,InputIterator end):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (start ! end){push_back(*start);start;}
} 首先我们得知道一个点那就是C为我们提供了函数重载那么编辑器就会通过传入的参数类型为我们匹配最适合的函数。 举例当我们通过下列方式传参 vectorint vv1(5,5); 编辑器会将我们的传参类型认为是int,int而不是size_t,int也就是说编辑器就会找到迭代器区间构造函数中去了这并不是我们想要的结果而编辑器却认为这是最合适的函数为了避免这种情况的出现所以需要重载int型的构造函数。 当然有的小伙伴可能不太理解为什么我们需要再写一个模板出来这理解起来真难受。这确实让人很难受但是他带来的好处也是很大的因为这样实现的功能让我们的构造方式做种多样的起来无论是何种形式的迭代器去构造我们都有对应的方式去构造出来这就是牛逼之处。
2.2 赋值运算符重载、拷贝构造难点
代码
vectorT operator(const vectorT va)
{if (_start ! va._start){//只能通过new的方式实现因为要调用自定义类型的构造函数T* temp new T[va.capacity()];//保留数据//memcpy(temp, va._start, sizeof(T)* va.size());int len va.size();for (int i 0; i len;i){//嵌套temp[i] va[i];}//释放掉原来空间如果有的话delete[] _start;_start temp;_finish _start va.size();_end_of_storage _start va.capacity();}return *this;
} 赋值需要相同类型才能成功这里用const vectorT相信大家也能理解我就直接切入重点了。 为什么我代码中要用循环一个一个的赋值为什么不直接调用库函数memcpy()呢简单又方便而是通过循环一个一个的赋值感觉写得好搓哦。其实呢也不是博主不想用memcpy()而是现实给了博主一巴掌让我认清写模板类的深拷贝有多令人头疼。 举一个例子如果我们构建的vectorvectorint类型的类那么我们开辟了一片空间用于存n个vectorint然后这些vectorint被我们直接用memcpy直接拷贝过来了但是我们呢又不能直接为单独写一个函数因为这是模板要是单独写了又不满足vectorint类型了。下图 原本我们是希望赋值出来的对象能有一个新的空间去承载这些数据如上图但是如果我们通过memcpy来实现能够成功吗请看下图 很明显如果通过memcpy实现了一个什么功能我们确实实现了一层深拷贝将vectorint用新的空间承载起来了但是还有更里面的空间呢这些空间也是需要new出来的哇。用memcpy还能行吗能行但不完全行除非你保证你以后不会用自定义类型模板。 所以决定采用循环的方式一次一次的赋值其中有一句话非常重要那就是 temp[i] va[i]; 这一句话没有你想象的那么简单你想如果是内置类型我们关不关心他申请空间不关心那么对于自定义类型它会怎么做嵌套直到遇到内置类型嵌套就结束了如下图 上图中我们可以看到每次我们赋值拷贝如果遇到了一个赋值运算符编辑器就回去检查是否是自定义类型需要去调用赋值运算符重载函数如此反复直到没有赋值运算符重载函数也就是没有需要申请空间的必要了。 下图的编译运行使用也不会报任何的错误了。
拷贝构造
//拷贝构造
vector(const vectorT va)
{//赋值重载*this va;
} 拷贝构造直接复用赋值运算符重载函数就行写法和逻辑思维差不多博主也想偷懒。
2.3 析构函数
//析构函数
~vector()
{//释放空指针不会出错无论是什么方式delete[] _start;_start nullptr;_finish nullptr;_end_of_storage nullptr;
} 析构函数也没有什么好讲的看代码就行。
3. 扩容
3.1 reserve
代码
void reserve(size_t n)
{if (n capacity()){size_t len size();T* temp new T[n];if (_start ! nullptr){//memcpy(temp, _start, sizeof(T) * size());for (size_t i 0; i len; i){temp[i] _start[i];}delete[] _start;}_start temp;_finish _start len;_end_of_storage _start n;}
} vector和其它string、顺序表或者说任何数据结构一样能不缩容就不缩容所以当我们的n小于容量大小的时候不做任何处理直接返回即可。 同样这里也涉及到了多次深拷贝的问题也就不能用memcpy来实现需要用循环依次赋值。还有咱们需要考虑到当空间异地扩容之后是需要将原空间释放的以防内存泄漏。
3.2 resize
代码
void resize(size_t n,const T val T())
{//小于操作不需要缩容只需要将_finish重定位即可if (n size()){_finish _start n;}else if (n size()){} //无动作else{int len n - size();//_finish和_end_of_storage的绝对位置之差与n的大小之比if (_finish n _end_of_storage){reserve(capacity() 0 ? n : capacity()n);}//补齐T类型数据while (len-- 0){*_finish val;_finish;}}
} resize功能比reserve多一个那就是能够实现重定size大小大于size的部分通过数据val占位。然后复用reserve如果是第一次扩容那就需要用三目运算来判断给定大小。
4. 插入删除 内容比较简单相信大家配合注解能够看懂直接上代码
//尾插只需要考虑如果空间不够就应该扩容
//并且还有空容量的情况也需要考虑
void push_back(const T val)
{if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}//如果不需要reserve表示不用扩容那么就是原地扩不需要动_start和_end_of_storage//如果扩了容reserve会为我们将这几个变量重定向*_finish val;_finish;
}//插入
iterator insert(iterator pos, const T val)
{//检查插入位置的有效性assert(pos _start);assert(pos _finish);//提前保留绝对距离size_t len pos - _start;//判断扩容if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}//通过绝对值偏移重定向pos _start len;//指向最后一个位置的下一个地址iterator end _finish;//移动完pos位置的数据结束while (end pos){*(end) *(end - 1);--end;}//因为有赋值运算符重载那么不管是否是内置类型都能满足*pos val;//向后移动一位_finish;return pos;
}//删除
void erase(iterator pos)
{//判断pos可行性assert(pos _start);assert(pos _finish);//从pos下一个位置地址开始依次向前移动iterator start pos 1;//中途是没有任何扩容缩容的地方所以迭代器不会更换while (start ! _finish){*(start - 1) *start;start;}//删除会有机会产生结果不确定的意外情况//所以任何一次删除该迭代器都应该被销毁//该函数才不会设置返回值--_finish;
}//尾删检查是否还有数据能删除
void pop_back()
{assert(_start ! _finish);--_finish;
}
5. 迭代器操作
//迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}//求个数、容量
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}//重载[]需要区分const有无的区别和pos位置的准确性
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
} 迭代器是有失效的情况的这部分根据不同的编辑器会有不同的实现方式博主这里不太想多讲不过我建议大家通过迭代器插入删除数据之后就别再使用这个迭代器了或者是重新给他定位防止非法越界。 以上就是博主对vector模拟实现的全部理解了希望能够帮到大家。
