当前位置：首页 > news >正文

C++初阶学习第十弹——深入讲解vector的迭代器失效

news 2024/11/8 17:47:35

C++初阶学习第八弹--深入解析vector的使用-CSDN博客

C++初阶学习第九弹-----vector的模拟实现-CSDN博客

一.前言

二.迭代器失效的本质

2.1 迭代器失效 ------ 扩容导致的野指针

2.2迭代器失效 ------ 迭代器指向的位置意义发生改变

编辑三. erase迭代器失效

四.vector的迭代器失效总结

一.前言

近期我们学习了vector的模拟实现和一些使用方法，接下来我们学习了解vector的迭代器的失效问题。

二.迭代器失效的本质

迭代器失效：实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。具体的可以用一下三步来说明：

[1]迭代器的本质就是指针，迭代器失效就是指针失效。
[2]指针失效：指针指向的空间是非法的。
[3]指针指向非法空间：指向了被释放的空间或者越界访问。

2.1 迭代器失效 ------ 扩容导致的野指针

错误示范：

void insert(iterator pos, const T& x)
{//检测参数合法性assert(pos >= _start && pos <= _finish);//检测是否需要扩容if (_finish == _end_of_stoage){size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapcacity);}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *(end);end--;}//把值插进去*pos = x;_finish++;
}

修改过的代码：

当我们进行尾插的时候，如果空间不够了，会进行reserve扩容，扩容之后_finish和_start都会进行改变，pos就成为了野指针，改变的方法也很简单，在扩容之前记录一个_start和pos的相对位置。

等到扩容之后再重新更新pos的位置。

iterator insert(iterator pos, const T& x)
{//扩容if (_finish == _end_of_storage){size_t len= pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*end = x;_finish++;return pos;
}

2.2迭代器失效 ------ 迭代器指向的位置意义发生改变

 void test2()
{xas_vector::vector<int> v1;v1.Push_back(1);v1.Push_back(2);v1.Push_back(3);v1.Push_back(4);v1.Push_back(5);v1.Push_back(6);for (auto ch : v1){cout << ch << " ";}cout << endl;xas_vector::vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.insert(it, 20);it++;}it++;}for (auto ch : v1){cout << ch << " ";}cout << endl;
}

it是指向原空间的，当insert插入要扩容时，原空间的数据拷贝到新空间上，但这也就意味着旧空间全是野指针，而it是一直指向旧空间的，随后遍历it时就非法访问野指针，也就失效了。形参的改变不会影响实参，即使你内部pos指向改变了，但是并不会影响我外部的it。
有人觉得提前reserve开辟足够大的空间即可避免发生野指针的现象，但是又会出现一个新的问题，我们看下图：

修改方法： 给insert函数加上返回值即可解决，返回指向新插入元素的位置

iterator insert(iterator pos, const T& x)
{//检测参数合法性assert(pos >= _start && pos <= _finish);//检测是否需要扩容/*扩容以后pos就失效了，需要更新一下*/if (_finish == _end_of_stoage){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;
}

三. erase迭代器失效

当进行指定位置删除时，最终返回的是删除元素的位置，当我们访问这个位置的时候，如果删除元素后面还有值，那么就会往前挪，我们就能访问到元素，但是当删除位置pos位于最后一个元素时，删除后我们访问就会访问到begin()，就会越界

正确代码的展示：

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;
}