wordpress怎么当站长,手机网页被禁止访问了怎么办,开源网站模板cms,手机网站开发协议在之前《vector》章节当中我们学习了STL当中的vector基本的使用方法#xff0c;了解了vector当中各个函数该如何使用#xff0c;在学习当中我们发现了vector许多函数的使用是和我们之前学习过的string类的#xff0c;但同时也发现vector当中一些函数以及接口是和string不同的… 在之前《vector》章节当中我们学习了STL当中的vector基本的使用方法了解了vector当中各个函数该如何使用在学习当中我们发现了vector许多函数的使用是和我们之前学习过的string类的但同时也发现vector当中一些函数以及接口是和string不同的。那么接下来在本篇我们就将试着模拟实现vector在模拟实现过程当中我们就会了解当vector当中迭代器失效的问题相信在本篇之后你会对vector有更深的了解接下来就开始本篇的学习吧 1.实现各个函数之前的工作
在模拟实现我们先要解决在模拟实现vector过程文件该如何创建
在vector由于是要是要使用到类模板来实现因此在实现就和实现string不同不再将vector成员函数的声明和定义分离到两个文件因此在此就创建一个头文件vecor.h来存放类vector的实现在创建一个.cpp文件test.cpp来测试在vector当中实现的各个成员函数是否满足要求以及是否能正常运行。
注在此为了避免我们实现的vector和std命名空间当中的vector冲突因此就先新创建一个命名空间之后将我们模拟实现的vector类放在创建的命名空间内这样就不会出现冲突了 完成了文件的创建之后接下来就来分析在我们模拟实现的类vector当中成员变量该如何创建
在此你可能就会直接认为由于vector就是顺序表那么就直接和之前在数据结构当中实现顺序表一样使用三个变量来实现即可第一个变量就是指向数组的指针第二个变量就是底层数组的有效元素个数最后一个变量就是数组的内存空间大小
以上你这种也是可以实现的但是在通过vector源码就可以发现在实现vector时vector当中的成员变量是三个迭代器这时你可能就会疑惑这三个迭代器分别表示的是什么呢
其实在以上三个迭代器当中start指向的是vector对象内第一个元素finish指向的是vector对象当中最后一个有效元素之后的位置end_of_storage指向的是vector对象当中最后内存空间之后的位置。并且在此我们还要了解到由于vector的底层是用数组来实现的那么各个元素在物理逻辑上就是连续存放的那么在vector当中迭代器底层就可以直接使用对应的指针来实现。那么这时将finish减start就可以得到有效元素将end_of_storage减finish就可以此时底层数组的内存空间大小
因此通过以上的分析就可以发现使用vector源码当中的成员变量这种形式也是可以满足我们的要求的那么接下来在模拟实现vector当中也按照源码的这种方式来实现成员变量
#includeiostream
#includeassert.husing namespace std;namespace zhz
{templateclass Tclass vector{public://成员函数. . .private:T* _start nullptr;T* _finish nullptr;T* _endofstorage nullptr;};}解决了以上的问题接下来就可以开始实现vector当中的各个成员函数了 2.vector模拟实现
在模拟实现vector我们是先实现插入和删除的函数这时因为在构造函数当中通过调用插入的函数就可以实现各个接口的构造函数这样就不需要我们自己来实现插入了这就让构造函数的代码写起来简单多了 2.1 size和capacity
在以上我们就分析出了在vector当中该如何来得到size与capacity因此接下来就直接实现代码
在vector.h内实现函数的代码
size_t size()const
{return _finish - _start;
}size_t capacity()const
{return _endofstorage - _start;
} 2.2 下标[ ]访问
在vector由于各个元素之间的物理空间是连续的那么就可以实现[ ]的运算符重载函数在此要实现const与非const对象的两个版本
在vector.h内实现函数的代码
T operator[](size_t i)
{assert(i size());return _start[i];
}
const T operator[](size_t i)const
{assert(i size());return _start[i];
}
注在此在使用[ ]来访问vector对象内的元素不能超出对象内底层数组的大小因此在此在实现 [ ]的运算符重载函数就需要使用assert断言 2.3 迭代器
在vector当中迭代器的实现直接使用指针来使用就可以满足要求在此vector的迭代器就是原生态指针T* 因此在此在实现begin和end函数之前先要将指针重命名为迭代器
typedef T* iterator;//普通迭代器
typedef const T* const_itreator;//const迭代器完成以上操作就可以来实现begin和end函数的代码了
在vector.h内实现函数的代码
iterator begin()
{return _start;
}iterator end()
{return _finish;
}
//const迭代器
const_itreator begin()const
{return _start;
}
const_itreator end()const
{return _finish;
} 2.4 reserve和resize
通过之前的学习我们了解过了reverse是用于调整内存空间的大小resize是用于调整有效元素那么接下来我们就试着来实现这两个函数
先在vector.h内实现reserve函数的代码
在此和之前string实现一样只有当指定的大小比当前的空间大时才进行调整这时要将原内存空间调整为大小为n的内存空间就需要先申请大小为n个变量的空间之后再将原空间内的数据拷贝到新申请的内存空间内再将原空间释放。最后将类成员变量的指向改变就完成了
这时reserve实现出的代码就如下所示
void reserve(int n)
{if (n capacity()){T* tmp new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start tmp;_finish _start size();_endofstorage _start n;}
}
以上的代码看起来完全可以满足我们的要求但是其实存在两个严重的问题你能看出来吗 首先是在以上代码中我们将_start指向tmp指向的内存空间后_finish _start size()这时在这条语句其实调用size()函数就有问题了这时在进入size()函数之后由于_start已经指向新的内存空间但是_finish还是指向原空间再将这两个指针相减就无法得到有效元素个数并且会导致程序奔溃 那么要解决以上这个问题就先再改变_start之前创建一个变量oldsize将原来的有效元素个数存储在该变量内之后_finish _start size()修改为_finish _start oldsize就可以解决该问题
void reserve(int n)
{if (n capacity()){T* tmp new T[n];size_t oldsize size();memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start tmp;_finish _start oldsize;_endofstorage _start n;}
}
以上代码其实还存在一个问题就是memcpy进行的是浅拷贝这在T是内置类型时确实没什么问题但我们实现的vector是类模板那么就是为了也能满足vector内的元素是自定义类型这种情况那么这时再进行浅拷贝就会在使用delete出现问题就例如当vector对象内的元素是string类型时 在使用完memcpy之后就会使得原内存空间内的string对象内的指针和新空间内string对象对象的指针指向同一块空间这在调用delete将原空间释放时由于会想调用string的析构函数将string对象内指针指向的空间释放那么在这之后就会使得在新空间内的string对象内的指针变为空指针
那么要解决以上这个问题就要再拷贝时进行深拷贝而不是浅拷贝
void reserve(int n)
{if (n capacity()){T* tmp new T[n];size_t oldsize size();//memcpy(tmp, _start, sizeof(T) * size());//memcpy完成的是浅拷贝for (int i 0; i oldsize; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish _start oldsize;_endofstorage _start n;}
} 完成了reserve函数之后接下来在vector.h内实现resize函数的代码
在此在resize函数当中要分为两种情况一种是当要调整的大小比原有效元素个数小时就直接改变_finish指针指向即可但当要调整的大小比原有效元素个数大时就要从_finish指针开始插入新的元素并且在最后还要改变_finish指针指向
这时resize实现出的代码就如下所示
void resize(size_t n,T xT())
{if (n size()){_finish _start n;}else{ reserve(n);//当n比原内存空间还大时避免多次扩容while (_finish _start n){*_finish x;_finish;}}
}
注在以上代码在插入元素后使用缺少参数T()在此使用到了匿名对象这时由于类vector是类模板那么变量x的类型就是不确定的因此就不能直接将变量的缺省值使用0或者nullptr来实现。因此在此就可以使用到之前在类和对象当中学到的匿名对象来实现这个缺省值 2.5 insert和erase
通过之前的学习我们知道insert和erase是分别实现任意位置的插入与删除并且在vector当中这两个函数的接口都是迭代器
先在vector.h内实现reserve函数的代码
在insert函数当中要实现的是在pos迭代器位置插入指定的数据在此在插入数据之前要先检查空间是否已经满了如果满了就要先进行扩容并且在此在vector当中我们是使用指针来实现遍历的这就不会出现之前我们在string当中实现insert使用下标时的问题
void insert(iterator pos, const T x)
{assert(pos _start pos _finish);//判断pos指针是否合法if (_finish _endofstorage){reserve(capacity() 0 ? 4 : 2 * capacity());//扩容}iterator i _finish -1;while (pos i){*(i 1) *i;i--;}*pos x;_finish;}
在以上我们就实现了insert的代码但是以上代码其实存在迭代器失效的问题首先在解决以上问题之前我们先要来了解什么是迭代器失效 迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 在了解了什么是迭代器失效之后接下来就可以来分析为什么以上的代码存在迭代器失效的问题了
在插入前当内存空间不足时也就是_finish _endofstorage时就需要先进行扩容那么在调用reserve之后_start就指向新的内存空间但问题是此时指针pos还指向原来的内存空间但是原内存空间内的数据已经被释放此时pos指针就变为空指针所以之后的将要插入位置之后的数据都往后移动一位时就会造成程序奔溃。
所以要解决以上pos迭代器失效的问题就要在扩容之后更新迭代器并且将该函数的返回值为新插入位置的迭代器
iterator insert(iterator pos, const T x)
{assert(pos _start pos _finish);//判断pos指针是否合法if (_finish _endofstorage){size_t len pos - _start;//记录pos迭代器位置reserve(capacity() 0 ? 4 : 2 * capacity());//扩容pos _start len;//更新pos迭代器}iterator i _finish;while (pos i){*(i 1) *i;i--;}*pos x;_finish;return pos;
} 完成了insert函数之后接下来在vector.h内实现erase函数的代码
在此erase函数就不会出现insert当中pos指针为空的情况因此你可能就会直接实现出以下代码
void erase(iterator pos)
{assert(pos _start pos _finish);iterator i pos1;while (i _finish){*(i-1) *i;i;}_finish--;
}
但其实迭代器失效除了包括扩容引起的野指针其实还包括删除数据导致数据挪动原本的迭代器已经不是指向之前的位置了这时该迭代器其实野失效了这是因为之后再使用原来的迭代器可能会导致逻辑问题 就例如以下示例 #include iostream
using namespace std;
#include vectorint main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
} erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理 论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end 的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素 时vs就认为该位置迭代器失效了。 再来看以下代码以下代码的功能是删除vector中所有的偶数请问那个代码是正确的为什么 #include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}return 0;
}
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;}return 0;
} 以上两段代码再VS下只有第二段代码是能通过的第一段代码会由于迭代器失效直接报错。而在Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端所以以上两段代码都能实现要求 那么在VS当中为什么在出现使用失效的迭代器就直接报错呢 这是由于在一些情况下使用失效的迭代器会造成程序奔溃就例如将以上数组v内数据改为以下时 vectorint v{ 1, 2, 2, 3, 4 , 5, 2 }; 这时再将以上第一段代码中在将数组中的第一个2删除之后迭代器it就指向了3这就会使得数组中的第二个2不会被删除并且在删除最后的2时这时由于进入erase函数之后只会让_finish--这时删除完2之后继续it,在此之后it就一直不会等于_finish所以while就会死循环造成越界。这种情况下在Linux下也会出现错误 通过以上的分析就知道为什么VS下一旦出现了使用失效的迭代器就报错那么为了避免使用失效的迭代器在我们模拟实现的erase也要作出修改
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator i pos1;while (i _finish){*(i-1) *i;i;}_finish--;return pos1;
}
在以上代码将pos迭代器之后位置的迭代器作为erase的返回值这样在调用了erase之后就可以通过其返回值来更新迭代器 2.6 push_back与pop_back
在以上我们实现insert和erase函数之后在实现尾插push_back和尾删pop_back函数可以直接通过调用insert和erase来实现
void push_back(const T x)
{insert(end(), x);
}bool Empty()
{return _start _finish;
}void pop_back()
{assert(!Empty());erase(end()-1);
} 2.7 swap
在vector当中实现swap就可以避免在调用swap时调用到算法库内的swap从而导致深拷贝而在我们在vector内实现的swap只需要交换指针即可实现vector对象的交换
void swap(vectorT x)
{std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);
} 2.7 构造函数
在以上实现了插入函数之后接下来实现vector构造函数的各个接口就很简单了
//空构造
vector()
{}//使用迭代器区间构造
templateclass InputIterator
vector(InputIterator fist, InputIterator last)
{while (fist ! last){push_back(*fist);fist;}
}//调用initializer_list构造
vector(initializer_listT t1)
{reserve(t1.size());for (auto x: t1){push_back(x);}}vector(int n, const T x T())
{reserve(n);while (n--){push_back(x);}
}//n个x构造
vector(size_t n, const T x T())
{reserve(n);while(n--){push_back(x);}
}//拷贝构造
vector(const vectorT x)
{reserve(x.capacity());for (auto e : x){push_back(e);}
} 在以上构造函数中在实现n个变量构造时为什么还要提供以下接口呢 这是因为当vector对象类型是int时在使用原本的n个变量构造时由于迭代器区间构造参数类型会比n个变量构造的参数类型更加匹配这时就构造会调用到迭代器区间构造。因此实现以上函数就是为了避免这个问题 2.8 析构函数
在vector当中析构函数的作用是在对象清除时完成资源清理的工作又因为在vector当中底层的资源就是数组那么析构函数内要实现的就是将start指向的内存空间释放
完成了分析接下来就在vector.h内实现函数的代码
~vector()
{if(_start){delete[] _start;_start _finish _endofstorage nullptr;}
} 2.9 赋值运算符重载
在vector赋值运算符重载函数和string中一样可以直接使用以下的现代写法实现
vectorint operator(vectorT x)
{swap(x);return *this;
} 以上就是本篇的所有内容了希望能得到你的点赞、收藏❤️
