【 C++ 】vector的模拟实现+vector迭代器失效

目录1、基本成员变量2、默认成员函数构造函数析构函数拷贝构造函数赋值运算符重载函数3、容器访问相关函数接口operator[ ]运算符重载迭代器范围for4、vector空间增长问题size和capacityreserve扩容resizeswap 交换数据5、增加的相关函数接口push_back尾插insert6、删除的相关函数接口pop_back尾删eraseclear清空数据7、vector迭代器失效问题insert迭代器失效扩容导致野指针意义变了erase迭代器失效迭代器失效总结8、深浅拷贝问题1、基本成员变量namespace cpp { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; //指向容器的头 iterator _finish; //指向有效数据的尾 iterator _endofstoage;//指向容器的尾 }; }2、默认成员函数构造函数1、无参构造函数只需要把每个成员变量初始化为nullptr即可。//无参构造函数 vector() :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) {}或者我们可以在成员变量声明处给一个缺省值namespace xzy { templateclass T class vector { public: vector() {} private: iterator _start nullptr; iterator _finish nullptr; iterator _end_of_storage nullptr; } }2、带参构造函数用迭代器区间去初始化vector的带参构造函数首先在初始化列表对基本成员变量初始化在将迭代器区间在[first, last)的数据一个个尾插到容器当中即可//带参构造函数 template class InputIterator vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { //将迭代器区间在[first, last)的数据一个个尾插到容器当中 while (first ! last) { push_back(*first); first; } }这里之所以用一个模板而不用 vector 内部的迭代器是因为用模板我们即可以支持 vector 的迭代器也可以支持其他类型的迭代器。void test() { xzy::vectorint v1 { 1, 2, 3, 4, 5, 6 }; xzy::vectorint v2(v1.begin() 1, v1.end() - 1); for (const auto e : v2) cout e ; //2 3 4 5 cout endl; string s1(hello); xzy::vectorint v3(s1.begin(), s1.end()); for (const auto e : v3) cout e ;//104 101 108 108 111 cout endl; }注迭代器区间可以是容器的迭代器也可以通过传递数组原生指针void test() { //迭代器区间也可以传递数组 int a[] { 1, 2, 3, 4, 5, 6 }; xzy::vectorint v(a, a 6); for (const auto e : v) cout e ;//1 2 3 4 5 6 cout endl; }3、用n个val去初始化vectorvector的构造函数还支持用n个val去初始化只需要先调用reserve函数开辟n个大小的空间再利用for循环把val的值依次push_back尾插进去即可。//用n个val来构造vector vector(size_t n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (size_t i 0; i n; i) { push_back(val); } } //法二复用resize vector(size_t n, const T val T()) { resize(n, val); }这样写会出现一个问题内存寻址错误。当我想实现下面的语句时cpp::vectorint v(10, 4);这里我调用的地方两个参数都是int此时调用构造函数时匹配的是第二个传迭代器区间的构造函数导致这样的原因在于编译器会优先寻找最匹配的那个函数。此构造函数的第一个参数是unsigned int类型10 这个默认为 int 类型的值还要通过类型转换成 size_t 才能进行传参。而调用第二个迭代区间初始化直接可以顺利传参不需要类型准换。所以编译器会优先选择更适合的一个函数进行调用即这里的迭代区间初始化。所以不会优先匹配此构造函数。而迭代区间初始化有解引用操作但是我们传过来的参数是 int 类型所以才会出现非法的间接寻址这样的错误。因此我们需要再重载一个第一个参数为int类型的构造函数即可解决vector(int n, const T val T()) : _start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { reserve(n); for (int i 0; i n; i) { push_back(val); } } //法二复用resize vector(int n, const T val T()) { resize(n, val); }4、initializer_listC11对于vector还支持一种初始化方式vectorint v1{ 1, 2, 3, 4, 5 }; vectorint v2 { 1, 2, 3, 4, 5 };即我们可以用一个 {} 指定元素然后对一个 vector 对象进行初始化。它的底层原理是用了一个叫 initializer_list 的类来实现的。其成员函数有如下4个原理是通过用 begin 获取 {} 中第一个元素的迭代器用 end 获取 {} 中最后一个元素下一个位置的迭代器然后通过循环来初始化一个 vector 对象。vector(initializer_listT il) { reserve(il.size());// 开和 {} 一样大的空间 for (auto e : il)// 支持迭代器就支持范围for push_back(e); }析构函数首先判断该容器_start是否为空不为空就释放空间置空即可。//析构函数 ~vector() { if (_start)//避免释放空指针 { delete[] _start;//释放容器所指向的空间 _start _finish _endofstoage nullptr;//置空 } }拷贝构造函数拷贝构造可以借助先前string的拷贝构造思路利用现代方法解决首先对基本成员变量进行初始化接着建立一个tmp的模板将要拷贝的数据利用构造函数去传递过去再将这个tmp模板与自己交换即可。//拷贝构造函数 vector(const vectorT v) :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { vectorT tmp(v.begin(), v.end());//调用构造函数 swap(tmp); }法二vector(const vectorT v)//或者vector(const vector v) { reserve(v.size()); for (auto e : v) push_back(e); }赋值运算符重载函数这里是传值传参没有引用传参直接利用vector调用构造函数返回的值与左值进行swap交换即可进行赋值//赋值运算符重载 vectorT operator(vectorT v)//调用构造 { this-swap(v);//交换这两个对象 return *this;//返回 }法二vectorT operator(const vectorT v)//或者vector operator(const vector v) { if (this ! v) { delete[] _start; _start _finish _end_of_storage nullptr; reserve(v.size()); for (auto e : v) push_back(e); } return *this; }3、容器访问相关函数接口operator[ ]运算符重载直接返回pos位置的数据即可进行下标[ ]的方式进行访问//operator[]运算符重载 T operator[](size_t pos) { assert(pos size());//检测pos的合法性 return _start[pos]; }为了方便const对象也可以调用[ ]运算符重载因此还推出了一个const版本的[ ]运算符重载。//const版本的[]运算符重载 const T operator[](size_t pos) const { assert(pos size());//检测pos的合法性 return _start[pos]; }迭代器vector的begin直接返回容器的_start起始位置即可vector的end返回容器的_finish的位置。//begin iterator begin() { return _start;//返回容器起始位置 } //end iterator end() { return _finish;//返回有效数据下一个的地址 }这里迭代器同样也要考虑到const对象调用的可能性因此推出const版本的迭代器如下//const版本迭代器 const_iterator begin() const { return _start; } //end const_iterator end() const { return _finish; }范围for和前面一样范围for的底层是通过迭代器实现的写法也很简单void test_vector() { cpp::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); //范围for for (auto e : v) { cout e ;//1 2 3 4 5 } }4、vector空间增长问题size和capacity指针相减可以得到对应的个数因此获取size只需_finish - _start。获取capacity只需_endofstoage - _start。size函数size_t size() const //最好加上const普通对象和const对象均可调用 { return _finish - _start; //指针相减就能得到size的个数 }capacity函数size_t capacity() const { return _endofstoage - _start; }reserve扩容reserve扩容和string的扩容非常相似。先开辟一块新的扩好容的空间如果旧空间里头有数据那么就利用for循环将容器中的数据一个一个拷贝到新空间再释放旧空间最后指向新空间。如果没有直接指向新空间即可。//reserve扩容 void reserve(size_t n) { size_t sz size();//提前算出size()的大小方便后续更新_finish if (n capacity()) { T* tmp new T[n]; if (_start)//判断旧空间是否有数据 { //不能用memcpy因为memcpy是浅拷贝 for (size_t i 0; i size(); i) { tmp[i] _start[i];//将容器当中的数据一个个拷贝到tmp当中 } delete[] _start;//释放旧空间 } _start tmp;//指向新空间 } //更新_finish和_endofstoage _finish _start sz; _endofstoage _start n; }补充1在扩容结束后要记得更新_finish和_endofstoage这里的_finsh要加上原先的size()长度要先用变量sz保存下来否则后续扩容后会更改指针的指向由原先的_start变为tmp若直接 size()函数的返回值会导致结果为随机值。补充2不能使用memcpy进行数据拷贝因为memcpy是浅拷贝它会将一段内存空间中内容原封不动的拷贝到另外一段内存空间中导致后续delete时拷贝过的数据一并给delete了具体我下面详谈。resize如果 n 小于当前容器的size()则内容将减少到其前 n 个元素删除超出并销毁的元素。如果 n 大于当前容器 size()则通过在末尾插入所需数量的元素以达到 n 的大小来扩展内容。若指定了 val则新元素将初始化为 val 的副本否则它们将进行值初始化。如果 n 也大于当前容器容量capacity()则会自动重新分配分配的存储空间。//resize //void resize(size_t n, T val T()) void resize(size_t n, const T val T()) //利用T()调用默认构造函数的值进行初始化这样写说明C的内置类型也有自己的构造函数 { //如果 n capacity()容量就需要扩容 if (n capacity()) { reserve(n); } //如果 n size()就需要把有效数据_finish到_start n之间的数据置为缺省值val if (n size()) { while (_finish _start n) { *_finish val; _finish; } } //如果 n size()更新有效数据到_start n else { _finish _start n; } }补充C的内置类型也有自己的构造函数和析构函数这样才能更好的支持模板。void test() { int i 0; int j int(); int k int(1); cout i endl;//0 cout j endl;//0 cout k endl;//1 }swap 交换数据直接调用库函数的swap去进行成员变量的交换即可。//交换函数 void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstoage, v._endofstoage); }5、增加的相关函数接口push_back尾插push_back尾插和之前写过的尾插大同小异先判断是否需要扩容把尾插的值赋过去再更新有效数据地址_finish即可void push_back(const T x) { //检测是否需要扩容 if (_finish _endofstoage) { size_t newcapcacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapcacity); } *_finish x; _finish; }这里push_back还可以复用下文实现好的insert进行尾插当insert中的pos为_finish时insert实现的就是push_back尾插。而_finish可以通过调用迭代器end函数来解决。void push_back(const T x) { //法二复用insert insert(end(), x); //当insert中的参数pos为end()时就是尾插 }insert首先要坚持插入的位置是否越界以及是否需要扩容。接着检测是否需要扩容。再挪动数据最后把值插入进去。注意注意扩容以后pos就失效了要记得更新pos否则会发生迭代器失效。可以通过设定变量n来计算扩容前pos指针位置和_start指针位置的相对距离最后在扩容后让_start再加上先前算好的相对距离n就是更新后的pos指针的位置了。其实这里还有一个迭代器失效的问题具体是啥后续有写。下面给出完善修正后的insert//insert iterator insert(iterator pos, const T x) { //检测参数合法性 assert(pos _start pos _finish); //检测是否需要扩容 /*扩容以后pos就失效了需要更新一下*/ if (_finish _endofstoage) { size_t n pos - _start;//计算pos和start的相对距离 size_t newcapcacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapcacity); pos _start n;//防止迭代器失效要让pos始终指向与_start间距n的位置 } //挪动数据 iterator end _finish - 1; while (end pos) { *(end 1) *(end); end--; } //把值插进去 *pos x; _finish; return pos; }6、删除的相关函数接口pop_back尾删首先判断_finish是否大于_start若大于直接_finsh--即可否则啥也不需要操作。void pop_back() { if (_finish _start)//判断是否可以进行删除 { _finish--; } }pop_back也可以复用下文的erase实现当erase的参数为_finish时实现的就是尾删而_finish可以通过调用迭代器end()函数来解决。void pop_back() { //法二复用erase erase(end() - 1); //不能用end()--因为end()是传值返回返回的是临时对象临时对象具有常性不能自身或--因此要用end() - 1 }erase首先要检查删除位置pos的合法性其次从pos 1的位置开始往前覆盖即可删除pos位置最后记得返回的值为删除位置的下一个位置其实返回的就是pos因为在pos删除后下一个值会覆盖到pos的位置上。//erase iterator erase(iterator pos) { //检查合法性 assert(pos _start pos _finish); //从pos 1的位置开始往前覆盖即可完成删除pos位置的值 iterator it pos 1; while (it _finish) { *(it - 1) *it; it; } _finish--; return pos; }补充1一般vector删除数据都不考虑缩容的方案当size() capacity() / 2 时可以考虑开一个size()大小的新空间拷贝数据释放旧空间。缩容的本质是时间换空间。一般设计不会考虑缩容因为实际比较关注时间效率不是太关注空间效率因为现在硬件设备空间都比较大空间存储也比较便宜。补充2erase也会存在失效erase的失效是意义变了或者不存在有效访问数据有效范围。一般不会使用缩容的方案那么erase的失效一般也不存在野指针的失效。后续讲解迭代器失效。这里先给出结论erase(pos)以后pos失效了pos的意义变了但是在不同平台下面对于访问pos的反应是不一样的我们用的时候要以失效的角度去看待此问题。对于insert和erase造成迭代器失效问题linux的g平台检查很佛系基本靠操作系统本身野指针越界检擦机制。windows下VS系列检擦更严格一些使用一些强制检擦机制意义变了可能会检擦出来。虽然g对于迭代器失效检查时是非常佛系的但是套在实际场景中迭代器意义变了也会出现各种问题。clear清空数据只需要把起始位置的指针_start赋给有效数据指针_finish即可完成数据的清空。//clear清空数据 void clear() { _finish _start; }7、vector迭代器失效问题insert迭代器失效上面我们写了insert的模拟实现这里先我们给出不完善版本以insert的雏形开始往后深层次递进演化如下void insert(iterator pos, const T x) { //检测参数合法性 assert(pos _start pos _finish); //检测是否需要扩容 if (_finish _endofstoage) { size_t newcapcacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapcacity); } //挪动数据 iterator end _finish - 1; while (end pos) { *(end 1) *(end); end--; } //把值插进去 *pos x; _finish; }insert的迭代器失效分为两大类扩容导致野指针意义变了扩容导致野指针我们给出两组测试用例如下怎么push_back尾插4个后调用insert会出现随机值而push_back尾插5个后调用insert就没问题此问题就是迭代器失效原因在于pos没有更新。导致非法访问野指针。上述当尾插4个数字后再头插一个数字发生扩容根据reserve扩容机制_start和_finish都会更新维度这个插入的位置pos没有更新此时pos依旧执行旧空间再者reserve后会释放旧空间此时的pos就是野指针这也就导致后续执行*pos x就是对非法访问野指针所以最终结果就是随机值。解决办法可以通过设定变量n来计算扩容前pos指针位置和_start指针位置的相对距离最后在扩容后让_start再加上先前算好的相对距离n就是更新后的pos指针的位置了。修正如下void insert(iterator pos, const T x) { //检测参数合法性 assert(pos _start pos _finish); /*扩容以后pos就失效了需要更新一下*/ if (_finish _endofstoage) { size_t n pos - _start;//计算pos和start的相对距离 size_t newcapcacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapcacity); pos _start n;//防止迭代器失效要让pos始终指向与_start间距n的位置 } //挪动数据 iterator end _finish - 1; while (end pos) { *(end 1) *(end); end--; } //把值插进去 *pos x; _finish; }意义变了比如现在我要在所有的偶数前面插入2可是测试结果确是如下这里发生了断言错误这段代码发生了两个错误和上面的错误一样首先it是指向原空间的当insert插入到要扩容时原来的旧数据被拷到了新空间上这也就意味着旧空间全是野指针而it一直是指向旧空间的随后遍历it时就非法访问野指针也就失效了。形参的改变不会影响实参即使你内部pos的指向改变了但是并不会影响我外部的it。为了解决上面的错误有人会觉着提前reserve开辟足够大的空间即可避免发生野指针的现象但是又出现了一个新的问题看图此时insert以后虽然没有扩容it也没有成为野指针但是it指向位置意义变了导致我们这个程序重复插入20。解决办法给insert函数加上返回值即可解决返回指向新插入元素的位置。iterator insert(iterator pos, const T x) { //检测参数合法性 assert(pos _start pos _finish); //检测是否需要扩容 /*扩容以后pos就失效了需要更新一下*/ if (_finish _endofstoage) { size_t n pos - _start;//计算pos和start的相对距离 size_t newcapcacity capacity() 0 ? 4 : capacity() * 2; reserve(newcapcacity); pos _start n;//防止迭代器失效要让pos始终指向与_start间距n的位置 } //挪动数据 iterator end _finish - 1; while (end pos) { *(end 1) *(end); end--; } //把值插进去 *pos x; _finish; return pos; }我们实际调用那块也得改动让it自己接收insert后的返回值void test_vector10() { //在所有的偶数前面插入2 cpp::vectorint v; //v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); cpp::vectorint::iterator it v.begin(); while (it ! v.end()) { if (*it % 2 0) { it v.insert(it, 20); it; } it; } for (auto e : v) { cout e ; } }erase迭代器失效先给出上篇博文erase模拟实现的代码iterator erase(iterator pos) { //检查合法性 assert(pos _start pos _finish); //从pos 1的位置开始往前覆盖即可完成删除pos位置的值 iterator it pos 1; while (it _finish) { *(it - 1) *it; it; } _finish--; return pos; }erase的失效都是意义变了或者不在有效访问数据的有效范围内一般不会使用缩容的方案那么erase的失效一般也不存在野指针的失效现在要对如下代码进行测试void test2() { cpp::vectorint v; //v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout v.size() : v.capacity() endl; auto pos find(v.begin(), v.end(), 2); if (pos ! v.end()) { v.erase(pos); } cout *pos endl; *pos 10; cout *pos endl endl; cout v.size() : v.capacity() endl; for (auto e : v) { cout e ; } }这里首先在尾插4个数据后比较了下size和capacity的大小此时是相等的接下来删除值为2的数此时*pos就是删除数字的下一个数据没有问题并且s有效数据size也少了一个后续修改*pos也没有问题。可是当我要删除值为4的数据呢再执行上述测试用例会是什么结果呢这里我总共就有4个数字按理说把最后一个数字删去后有效数字-1理应不存在说还会访问最后一个值的现象但是此结果确实是删掉4后又访问了4离谱的是还修改了4为10这就是erase典型的迭代器失效。但是这里也不足为奇因为你空间还没有缩容删掉的4还存在导致最终还能够被访问。迭代器失效总结vector迭代器失效有2种1、扩容缩容导致野指针式失效2、迭代器指向的位置意义变了系统越界机制检查不一定能检查到编译实现机制检查相对靠谱8、深浅拷贝问题接下来用先前模拟实现的vector来测试杨辉三角以此来解释我们的深浅拷贝问题namespace cpp { class Solution { public: // 核心思想找出杨辉三角的规律发现每一行头尾都是1中间第[j]个数等于上一行[j-1][j] vectorvectorint generate(int numRows) { vectorvectorint vv; // 先开辟杨辉三角的空间 vv.resize(numRows); for (size_t i 1; i numRows; i) { vv[i - 1].resize(i, 0); // 每一行的第一个和最后一个都是1 vv[i - 1][0] 1; vv[i - 1][i - 1] 1; } for (size_t i 0; i vv.size(); i) { for (size_t j 0; j vv[i].size(); j) { if (vv[i][j] 0) { vv[i][j] vv[i - 1][j - 1] vv[i - 1][j]; } } } return vv; } }; void test7() { vectorvectorint vv Solution().generate(5); for (size_t i 0; i vv.size(); i) { for (size_t j 0; j vv[i].size(); j) { cout vv[i][j] ; } cout endl; } } }理想结果如下测试结果如下再把扩容的代码给出//reserve扩容 void reserve(size_t n) { size_t sz size();//提前算出size()的大小方便后续更新_finish if (n capacity()) { T* tmp new T[n]; if (_start)//判断旧空间是否有数据 { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start;//释放旧空间 } _start tmp;//指向新空间 } //更新_finish和_endofstoage _finish _start sz; _endofstoage _start n; }分析如下这里出错的原因在于扩容错在扩容时调用的memcpy是浅拷贝导致先前存储的数据被memcpy后再delete就全删掉变成随机值了。仔细观察我调用的这行代码vectorvectorint vv Solution().generate(5);这行代码的意义是有一个vector容器其内部成员也是一个vector容器就好比一个二维数组有n行每一行都是一个一维数组。画图演示上述测试用例的原因总结vectorT中当T设计深浅拷贝的类型时如string/vectorT等等我们扩容使用memcpy拷贝数据是存在浅拷贝问题。memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是内置类型的元素memcpy即高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。解决方案reserve扩容时不使用memcpy改成for循环来解决//reserve扩容 void reserve(size_t n) { size_t sz size();//提前算出size()的大小方便后续更新_finish if (n capacity()) { T* tmp new T[n]; if (_start)//判断旧空间是否有数据 { //不能用memcpy因为memcpy是浅拷贝 for (size_t i 0; i size(); i) { tmp[i] _start[i]; } delete[] _start;//释放旧空间 } _start tmp;//指向新空间 } //更新_finish和_endofstoage _finish _start sz; _endofstoage _start n; }更正结果如下