秦皇岛网站定制哪家好,免费外贸网站源码,个人做外贸网站违法吗,手机电脑版淘宝网址✅1主页#xff1a;我的代码爱吃辣 #x1f4c3;2知识讲解#xff1a;C之STL #x1f525;3创作者#xff1a;我的代码爱吃辣 ☂️4开发环境#xff1a;Visual Studio 2022 #x1f4ac;5前言#xff1a;上次我们已经数字会用… ✅1主页我的代码爱吃辣 2知识讲解C之STL 3创作者我的代码爱吃辣 ☂️4开发环境Visual Studio 2022 5前言上次我们已经数字会用了vector这次我们对其底层更深一步挖掘其中重点是Vector中一些深浅拷贝问题。 目录
一.Vector模拟实现的整体框架
二. Vector的构造与析构
三.sizecapacity 四.reserveresize
1.reserve
2.resize
五.push_backpop_back
1.push_back
2. pop_back
六.Vector的迭代器 七.operator [ ] 八.inserterase
1.迭代器失效
2.insert
3.erase
九.再看Vector构造函数
十.拷贝构造
1.深浅拷贝
2.正确的拷贝构造代码
3.正确的 reserve
4.赋值运算符重载
十一.总体代码 一.Vector模拟实现的整体框架
我们先认识一下Vector的整体模拟实现框架Vector在功能上就是我们数据结构阶段实现的顺序表基本一致但是Vector在成员框架上与顺序表有所不同且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的构造与析构
Vector主要是对成员变量初始化 Vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
析构主要释放我们申请的空间 ~Vector(){delete[] _start;_start _finish _end_of_storage nullptr;}
三.sizecapacity
size返回当前顺序表存储的数据个数capacity返回当前顺序表的容量。 size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;} 四.reserveresize
1.reserve
设置Vector的容量注意容量支持增加但是不支持减小。
void reserve(size_t capa){//仅支持容量扩大不支持容量减小if (capacity() capa){size_t sz size();iterator tmp new T[capa];//分清当前的是否已经有了容量如果已经有了容量需要释放之前的容量//如果之前没有容量仅需将新开的空间指向我们的_start.if (_start){memcpy(tmp, _start, sizeof(T) * capacity()); /*error */delete[] _start;}//注意:此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,//然后计算的size也并非是准确的size。_start tmp;_finish tmp sz;_end_of_storage _start capa;}} 注意: 此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,然后计算的size也并非是准确的size。除此之外这份代码依旧是有问题的。我们后面解释。 错误代码如下 void reserve(size_t capa){if (capacity() capa){iterator tmp new T[capa];if (_start){memcpy(tmp, _start, sizeof(T) * capacity());delete[] _start;}//注意:此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,//然后计算的size也并非是准确的size。_start tmp;_finish tmp size();_end_of_storage _start capa;}} 2.resize
提供改变存储数据的个数的能力。如果 n size 时就是删除数据n size且空间不够时需要扩容初始化空间足够仅需要初始化剩下的空间。 void resize(size_t n, T val T()){ //1.n size;--删除数据if (n size()){_finish _start n;}//2.n sizeelse {//(1)如果空间不足需要扩容初始化if (n capacity()){reserve(n);}//(2)空间足够仅需要初始化剩下的空间while (_finish ! _start n){*(_finish) val;_finish;}}}五.push_backpop_back
1.push_back
从尾部插入一个数据。 void push_back(const T val){//检查是否需要扩容if (_finish _end_of_storage){capacity() 0 ? reserve(5) : reserve(capacity() * 2);}//插入数据*(_finish) val;_finish;}
2. pop_back bool empty() const {return size() 0;}void pop_back(){//判空assert(!empty());//我们仅需将维护尾部数据的指针向前挪一位。_finish--;}
六.Vector的迭代器 typedef T* iterator;typedef const T* const_iterator;
Vector底层就是顺序存储的结构所以可以使用原生指针作为迭代器。 //普通迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const_iterator begin()const {return _start;}const_iterator end()const{return _finish;}
有了迭代器就可以支持迭代器访问和范围for。
int main()
{Vectorint v1;v1.push_back(100);v1.push_back(200);v1.push_back(300);v1.push_back(400);v1.push_back(500);v1.push_back(600);v1.push_back(700);Vectorint::iterator it v1.begin();while (it ! v1.end()){cout *it ;it;}cout endl;for (auto e : v1){cout e ;}return 0;
} 七.operator [ ] //穿引用返回T operator[](size_t pos){//判断位置的合法性assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];} 八.inserterase
1.迭代器失效
在模拟实现之前我们先看一下什么是迭代器失效问题
迭代器失效问题通常发生在容器类的成员函数中例如erase和insert。在这些函数中迭代器被重置或修改导致原始迭代器不再指向容器的正确位置从而导致迭代器失效。
int main()
{vectorint v1;v1.push_back(100);v1.push_back(200);v1.push_back(300);v1.push_back(400);v1.push_back(500);v1.push_back(600);v1.push_back(700); vectorint::iterator pos find(v1.begin(), v1.end(),200);//对pos位置插入v1.insert(pos, 150);//pos已经失效v1.insert(pos, 170);return 0;
} 原理图
情况一 上述代码中的迭代器失效问题也是属于这种情况。
情况二 2.insert iterator insert(iterator pos,T val){assert(pos _start);assert(pos _finish);//迭代器失效问题,记录pos的相对位置int len pos - _start;if (_finish _end_of_storage){capacity() 0 ? reserve(5) : reserve(capacity() * 2);}//扩容后重新计算pos没有发生扩容pos不变pos _start len;iterator end _finish;//数据挪动while (end pos){(*end) *(end - 1);end--;}_finish;(*pos) val;return pos;}
在使用pos时要注意扩容会使得pos失效需要重新计算pos位置。
3.erase iterator erase(iterator pos){//判断位置是否合法assert(pos _start);assert(pos _finish);iterator end pos ;/挪动数据删除while (end _finish){*end *(end 1);end;}_finish--;return pos;}
九.再看Vector构造函数
std中的vector还支持使用指定个数和初始化值初始化和迭代器区间初始化。这两个功能在我们平时也是能用到的。 //1.VectorT v(5,10);创建一个Vector并且初始化前5个值为10Vector(size_t n, const T val T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (int i 0; i n; i){push_back(val);}}//2.迭代器初始化[frist,lest)templateclass InputIteratorVector(InputIterator frist, InputIterator lest):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(lest - frist);while (frist ! lest){push_back(*frist);frist;}}//3.防止构造函数调用错误Vector(int n, const T val T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (int i 0; i n; i){push_back(val);}}第三个构造函数的作用是防止构造调用错误冲突在我们进行如下的调用时
Vectorint v2(5, 10);
编译器会以为我们在调用迭代器区间初始化构造函数因为经过模板的推导只有迭代器区间初始化构造函数更适合这个调用。然后将一个整形当作地址在迭代器区间初始化构造函数里面解引用了报错是非法的间接寻址。 正常调用结果
十.拷贝构造
今天这里编译器默认生成的拷贝构造显然是不能用了。
1.深浅拷贝
万万不可以直接使用拷贝函数按二进制或者按字节直接拷贝了。
错误代码1 Vector(const VectorT v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());//万万不可以直接按二进制拷贝memcpy(_start, v._start, sizeof(T) * v.capacity()); /*error!!!!*/_finish _start v.size();_end_of_storage _start v.capacity();}
原因
调用处代码 int main()
{string str(abcdefg);Vectorstring v2(5,str);Vectorstring v3(v2);return 0;
} 会使得我们同一块空间被delete两次从而引发内存错误。
2.正确的拷贝构造代码 Vector(const VectorT v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());//这里我们将数据一个一个push进去这样我们借助push_back底层插入的时候//会使用string的赋值构造完成深拷贝。for (int i 0; i v.size(); i){push_back(v[i]);}}//现代写法Vector(const VectorT v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){VectorT tmp(v.begin(), v.end());swap(tmp);}
错误代码2reserve void reserve(size_t capa){//仅支持容量扩大不支持容量减小if (capacity() capa){size_t sz size();iterator tmp new T[capa];//分清当前的是否已经有了容量如果已经有了容量需要释放之前的容量//如果之前没有容量仅需将新开的空间指向我们的_start.if (_start){//这里千万不能按二进制直接拷贝.memcpy(tmp, _start, sizeof(T) * capacity()); /*error */delete[] _start;}//注意:此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,//然后计算的size也并非是准确的size。_start tmp;_finish tmp sz;_end_of_storage _start capa;}}
这里我们仍然是使用了memcpy。
调用处代码
int main()
{string str(abcdefg);Vectorstring v2;for (int i 0; i 6; i){v2.push_back(str);}return 0;
} 3.正确的 reserve
void reserve(size_t capa){//仅支持容量扩大不支持容量减小if (capacity() capa){size_t sz size();iterator tmp new T[capa];//分清当前的是否已经有了容量如果已经有了容量需要释放之前的容量//如果之前没有容量仅需将新开的空间指向我们的_start.if (_start){//这里千万不能按二进制直接拷贝.//memcpy(tmp, _start, sizeof(T) * capacity()); /*ror */for (int i 0; i size(); i){//内置类型直接赋值,自定义类型使用赋值构造tmp[i]_start[i];}delete[] _start;}//注意:此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,//然后计算的size也并非是准确的size。_start tmp;_finish tmp sz;_end_of_storage _start capa;}}
这里有一个细节就是在reserve和拷贝构造的拷贝数据的时候我们都是使用了赋值。问题我们并没有重载赋值运算符编译器自动生成简单来说就是这里又会是一个浅拷贝。
4.赋值运算符重载 //传统写法VectorT operator(const VectorT v){T* tmp new T[v.capacity()];if (_start){for (int i 0; i v.size(); i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start v.size();_end_of_storage _start v.capacity();return *this;}//现代写法void swap(VectorT v ){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);}VectorT operator(VectorT v){swap(v);return *this;}
现代写法利用拷贝构造拷贝出来的对象然后交换对象的成员。
十一.总体代码
#pragma once
#includeiostream
#includealgorithm
#includestring
#includecstring
#includecassert
using namespace std;templateclass T
class Vector
{
public:typedef T* iterator;typedef const T* const_iterator;Vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//1.VectorT v(5,10);创建一个Vector并且初始化前5个值为10Vector(size_t n, const T val T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (int i 0; i n; i){push_back(val);}}//2.迭代器初始化[frist,lest)templateclass InputIteratorVector(InputIterator frist, InputIterator lest):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(lest - frist);while (frist ! lest){push_back(*frist);frist;}}//3.防止构造函数调用冲突Vector(int n, const T val T()):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(n);for (int i 0; i n; i){push_back(val);}}//传统写法 拷贝构造//Vector(const VectorT v)// :_start(nullptr),// _finish(nullptr),// _end_of_storage(nullptr)//{// reserve(v.capacity());// //这里我们将数据一个一个push进去这样我们借助push_back底层插入的时候// //会使用string的赋值构造完成深拷贝。// for (int i 0; i v.size(); i)// {// _start[i] v[i];// }//}//现代写法拷贝构造Vector(const VectorT v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){VectorT tmp(v.begin(), v.end());swap(tmp);}//传统写法赋值拷贝//VectorT operator(const VectorT v)//{// T* tmp new T[v.capacity()];// if (_start)// {// for (int i 0; i v.size(); i)// {// tmp[i] _start[i];// }// delete[] _start;// }// _start tmp;// _finish _start v.size();// _end_of_storage _start v.capacity();// // return *this;//}void swap(VectorT v ){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);}//现代写法赋值拷贝VectorT operator(VectorT v){swap(v);return *this;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void reserve(size_t capa){//仅支持容量扩大不支持容量减小if (capacity() capa){size_t sz size();iterator tmp new T[capa];//分清当前的是否已经有了容量如果已经有了容量需要释放之前的容量//如果之前没有容量仅需将新开的空间指向我们的_start.if (_start){//这里千万不能按二进制直接拷贝.//memcpy(tmp, _start, sizeof(T) * capacity()); /*ror */for (int i 0; i size(); i){//内置类型直接赋值,自定义类型使用赋值构造tmp[i]_start[i];}delete[] _start;}//注意:此处不能直接tmpsize()来计算因为在计算_start的时候已经已经改变了_start,//然后计算的size也并非是准确的size。_start tmp;_finish tmp sz;_end_of_storage _start capa;}}void resize(size_t n, T val T()){ //1.n size;--删除数据if (n size()){_finish _start n;}//2.n sizeelse {//(1)如果空间不足需要扩容初始化if (n capacity()){reserve(n);}//(2)空间足够仅需要初始化剩下的空间while (_finish ! _start n){*(_finish) val;_finish;}}}//穿引用返回T operator[](size_t pos){//判断位置的合法性assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}void push_back(const T val){if (_finish _end_of_storage){capacity() 0 ? reserve(5) : reserve(capacity() * 2);}//内置类型直接赋值,自定义类型使用赋值构造*(_finish) val;_finish;}bool empty() const {return size() 0;}void pop_back(){//判空assert(!empty());//我们仅需将维护尾部数据的指针向前挪一位。_finish--;}iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator end pos ;while (end _finish){*end *(end 1);end;}_finish--;return pos;}iterator insert(iterator pos,T val){assert(pos _start);assert(pos _finish);//迭代器失效问题,记录pos的相对位置int len pos - _start;if (_finish _end_of_storage){capacity() 0 ? reserve(5) : reserve(capacity() * 2);}//扩容后重新计算pos没有发生扩容pos不变pos _start len;iterator end _finish;//数据挪动while (end pos){(*end) *(end - 1);end--;}_finish;(*pos) val;return pos;}//普通迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const_iterator begin()const {return _start;}const_iterator end()const{return _finish;}~Vector(){delete[] _start;_start _finish _end_of_storage nullptr;}
private:iterator _start;//数据存储首地址iterator _finish;//有效数据尾部地址下一个地址。iterator _end_of_storage;//容量尾地址下一个地址int tmp;
};
