C++ vector迭代器失效完全解析：原因、场景与解决方案
创作时间:
作者:
@小白创作中心
C++ vector迭代器失效完全解析：原因、场景与解决方案
引用
CSDN
1.
https://blog.csdn.net/weixin_45031801/article/details/138410868
在C++编程中，vector容器的迭代器失效是一个常见的问题，如果不加以注意，可能会导致程序崩溃。本文将详细探讨什么是迭代器失效、哪些操作会导致迭代器失效，以及如何避免迭代器失效，帮助开发者更好地理解和使用vector容器。
一、前言
最近我们学习了vector类的用法和模拟实现，同时提到了C++中的迭代器失效问题。在之前的文章中只是简单提及，由于迭代器失效问题非常重要，所以本文特地整理出来方便后期的复习和学习。如果有需要，可以参考以下文章：
- vector类的使用详解
- vector类的模拟实现
本文的要点包括：什么是迭代器失效？vector的哪些操作会导致迭代器失效？如何避免迭代器失效？
二、什么是迭代器失效？
- 迭代器的作用：主要作用是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装。
- vector的迭代器：就是原生态指针
T*。
template<class T>
typedef T* iterator; // 迭代器某种意义上就是指针
typedef const T* const_iterator;
- 因此迭代器失效：实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。具体的可以用一下三步来说明：
- 迭代器的本质就是指针，迭代器失效就是指针失效。
- 指针失效：指针指向的空间是非法的。
- 指针指向非法空间：指向了被释放的空间或者越界访问。
三、哪些操作会导致迭代器失效？
- 所有可能会引起扩容的操作都可能会导致迭代器失效。如：resize、reserve、insert、assign、push_back等 -------------- 野指针引起的迭代器失效
- 指定位置的插入和删除都会都可能会导致迭代器失效。如:insert 、erase ----------------- 迭代器指向的位置意义发生改变
四、如何避免迭代器失效？
接下来，我们将从insert和erase这两个接口函数来讲解如何避免迭代器失效问题。
insert迭代器失效
insert迭代器失效分为两类：
- 扩容导致野指针
- 迭代器指向的位置意义发生改变
下面我们先给出insert的初始版本，然后再逐渐的完善：
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++;
}
扩容导致野指针
首先我们给出以下两组测试用例：
- 这里为什么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 == _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++;
}
迭代器指向的位置意义发生改变
什么是迭代器指向的位置意义发生改变呢？举个例子来说明一下：
- 比如现在我要在所有的偶数前面插入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以后虽然没有扩容，it也并没有成为野指针，但是it指向位置意义变了，导致我们这个程序重复插入20。
解决方法：
给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;
}
我们实际调用的时候也需要改动，让it自己接收insert后的返回值：
erase迭代器失效
我们先给出erase的初始版本，然后再逐渐的完善：
void erase(iterator pos)
{
//检查合法性
assert(pos >= _start && pos < _finish);
//从pos + 1的位置开始往前覆盖，即可完成删除pos位置的值
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
}
- erase的失效都是迭代器指向的位置意义发生改变，或者不在有效访问数据的有效范围内
- erase一般不会使用缩容的方案，那么也就导致erase的失效一般不存在野指针的失效。
我们现在对下面代码进行测试：
void test_vector()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
cout << v.size() << ":" << v.capacity() << endl;
auto it = find(v.begin(), v.end(), 2);
if (it != v.end())
{
v.erase(it);
}
cout << *it << endl;
*pos = 10;
cout << *it << endl << endl;
cout << v.size() << ":" << v.capacity() << endl;
for (auto e : v)
{
cout << e << " ";
}
}
- 我们尾插4个数字，比较size和capacity的大小，此时是相等的，接下来删除值为2的数，此时it就是删除数字的下一个数据也就是3，此时有效数据也少了一个，后续修改it也就不存在问题。
- 如果我们这里要删除的值为4，那么结果会是怎么样的呢？
- 我们这里一共有4个数据，按理说把最后一个数字删除以后，有效数字-1，不存在还会访问最后一个值的现象，但是此结果却是删除4以后又访问了4，而且还修改4为10，这就是典型的erase迭代器失效。
我们再用另外一组例子来测试：
void test_vector()
{
//删除所有的偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
it++;
}
for (auto e : v)
{
cout << e << " ";
}
}
画图演示错误过程：
- 解决方案如下：
给 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;
}
void test_vector()
{
//删除所有的偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
it++;
}
}
for (auto e : v)
{
cout << e << " ";
}
}
五、迭代器失效总结
vector迭代器失效有两种：
- 扩容、缩容导致野指针式失效
- 迭代器指向的位置意义变了
系统越界机制检查，不一定能够检查到。编译实现检查机制，相对比较靠谱。
六、共勉
以上就是对vector的迭代器失效问题的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对C++ list的理解，请持续关注我哦！！！
热门推荐
宁波奉化雪窦寺历史、旅游攻略
舌尖上的临汾：探寻洪洞牛肉丸子面的魅力
麻仁胶囊的功效与作用
春节非遗里的初四拜年：传承千年的文化记忆
百达翡丽维修中心教你专业保养秘籍
百达翡丽手表清洁小窍门，你get了吗？
【白云族记】杨氏：恪守祖训精忠报国清白传家
冲绳美军基地：日本军事布局的核心
冲绳：从二战战场到美日军事一体化最前线
出现工伤后员工怎样保护自己的权益
辽宁男篮三连冠背后的商业化秘诀：混合体制运营模式解析
郭艾伦因伤缺阵，广州男篮不敌青岛
辽宁男篮大胜宁波背后：张舸豪能否接班赵继伟？
拔鱼刺，中国医生是最强的
鱼刺卡喉别慌！科学处理养成好习惯很重要
鱼刺卡喉土方法不可取，六旬大妈险些因此丧命
解读《素书》的智慧与哲理：如何在现代生活中应用？
丽江古城深度游：两天一夜完美打卡
成都发布大风预警！川西自驾游安全攻略来了
成都自驾游必打卡：春熙路&太古里
九寨沟冬季游：观光车购票全攻略
九寨沟VIP观光车购票攻略：手把手教你快速上车！
冬季旅游火热 经济与可持续发展需平衡
心脏不适挂哪个科室？一文读懂五大科室职责
啤酒与美食的完美搭配
中国海外军事基地：科科群岛与瓜达尔港的战略布局
中国空军基地：新型卫星技术助力军事行动
从积极心理学看糖友的情绪管理
糖尿病患者心理状态直接影响血糖控制，专家建议多管齐下缓解压力
健康教育：照亮糖尿病患者心理阴霾的明灯