[C++] STL_vector 迭代器失效问题

这篇具有很好参考价值的文章主要介绍了[C++] STL_vector 迭代器失效问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

1、前言

**迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:string的迭代器就是原生指针char,vector的迭代器就是原生态指针T因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
对迭代器失效我们了解了,那么现在我们就分析,在vector中哪些操作会导致迭代器失效。

2、情况一:底层空间改变的操作

存在底层空间改变的函数接口有:resize、reserve、insert、assign、push_back等。
产生的原因:
这几个接口都存在扩容的问题,扩容的时候存在异地扩容,当异地扩容后,原本的空间被释放,但是迭代器指的是被释放空间,这就会导致迭代器的失效问题,会引发程序崩溃的问题。
解决方法:
一旦存在扩容,扩容后对迭代器更新一次,重新给迭代器赋值即可。
举例:
我们看一下insert接口。
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

我们由图中可以看到,当我们需要在3之前插入数据30,但是空间已经满了,因此我们需要进行扩容,扩容是异地开空间,开好空间将旧空间的数据拷贝回来,并将旧空间释放掉,_start指向新的空间头部,但是it指的是旧空间的位置,这就是迭代器失效。我们记住it相对于_start的相对位置,在新空间开好后,更新it,让其指向新空间的相对位置。(方式:计算出it到_start的距离len,开好新空间后,更新it为新的_start+len)。
代码实现:

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;//先记下_start到pos位置的距离,因为扩容后迭代器pos就会失效
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;//新的空间需要更新迭代器pos
    }

    iterator end = _finish - 1;
    //挪动数据
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;

    return pos;
}

3、情况二:指定位置元素的删除操作

对于erase接口也会导致迭代器失效问题。那它是怎么导致的呢,我们来分析一下。
产生原因:
在erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

#include <iostream>
using namespace std;
#include <vector>

int main()
{
    int a[] = { 1, 2, 3, 4 };
    vector<int> v(a, a + sizeof(a) / sizeof(int));
    // 使用find查找3所在位置的iterator
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    // 删除pos位置的数据,导致pos迭代器失效。
    v.erase(pos);
    cout << *pos << endl; // 此处会导致非法访问
    return 0;
}

解决方法:
本质是因为尾删导致的迭代器失效问题,因此我们在尾删完后,返回it的下一个位置,我们的模拟实现是数据覆盖(it+1覆盖it),因此返回的还是it,一删之后 --_finish,当 it指的位置就是_finish 的时候正好也就停止了,因此也就解决了迭代器失效的问题。
代码实现:

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator it = pos + 1;
    //挪动数据
    while (it < _endOfStorage)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;

    return pos;
}

4、g++编译器对迭代器失效检测

Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs2019下极端。
我们来看下面这几种情况下,代码在vs2019和g++下不同的表现。

4.1 扩容

int main()
{
    vector<int> v{1,2,3,4,5};
    for(size_t i = 0; i < v.size(); ++i)
    	cout << v[i] << " ";
    cout << endl;
    
    auto it = v.begin();
    cout << "扩容之前,vector的容量为: " << v.capacity() << endl;

    v.reserve(100);
    cout << "扩容之后,vector的容量为: " << v.capacity() << endl;
    
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    return 0;
}

g++下运行结果:
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

vs2019下运行结果:
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

vs2019下程序崩溃了。
结论:当扩容后迭代器就是失效的,g++下虽然能运行,但是结果出错了,vs下直接程序崩溃。

4.2 erase删除任意位置(非尾删)

#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v{1,2,3,4,5};
    vector<int>::iterator it = find(v.begin(), v.end(), 3);
    
    v.erase(it);
    cout << *it << endl;
    
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    return 0;
}

g++下运行结果:
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

vs2019下运行结果:
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

结论:在非尾删的删除中,空间是没有变的,迭代器指的是还是那块空间,g++下迭代器没有失效,删除后后面的数据前移,it位置没失效,vs下只要是erase,就判断为迭代器失效了。

4.3 erase尾删

int main()
{
	vector<int> v{1,2,3,4,5,6};

	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}

	for (auto e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

g++下运行结果:
[C++] STL_vector 迭代器失效问题,C++,c++,java,数据库

vs2019下不用看,直接崩溃。
结论:当在尾删的时候,删除之后存在数据挪动,一挪动_finish与it是一个位置了,erase本就返回被删除位置的下一个位置,此时迭代器失效,再++it程序直接崩溃。

5、总结

本篇主要讲了扩容、插入、删除造成的迭代器失效,g++对迭代器失效检测的不严格,而vs对迭代器失效检测很严格,直接崩溃。
1、扩容一般都要更新迭代器,我们不知道哪一次的扩容是异地扩。
2、插入任意位置时,一旦存在扩容就要更新迭代器,本质就是扩容要更新迭代器。
3、删除任意位置时,g++下非尾删不考虑迭代器失效问题,尾删一定要注意迭代器失效问题;vs2019中删除就认定为迭代器失效,直接崩溃。文章来源地址https://www.toymoban.com/news/detail-675234.html

到了这里,关于[C++] STL_vector 迭代器失效问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [STL-list]介绍、与vector的对比、模拟实现的迭代器问题

     list的底层是 带头双向链表 结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 与其他的序列式容器相比(array,vector,deque),list通常 在任意位置进行插入、移除元素的执行效率更好 list最大的缺陷是 不支持任意位

    2024年04月15日
    浏览(94)
  • 【C++庖丁解牛】STL之vector容器的介绍及使用 | vector迭代器的使用 | vector空间增长问题

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 vector的文档介绍 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存

    2024年03月14日
    浏览(75)
  • 【C++】vector模拟实现+迭代器失效

    铁汁们,今天给大家分享一篇vector模拟实现 + 迭代器失效,来吧,开造⛳️ 指向最后一个空间的下一个位置 💡 iterator _endofstorage 指向存储第一个有效数据空间的位置 💡 iterator _start 指向存储最后一个有效数据空间的下一个位置 💡 iterator _finish 在成员变量声明处给缺省值,

    2024年02月21日
    浏览(35)
  • STL之list模拟实现(反向迭代器讲解以及迭代器失效)

    这次是关于list的模拟实现的代码,先看看下面的代码: 上面是list的代码,其底层是一个带头双向循环的链表,实现的方法就不说了,相信大家已经都会了,然后自己实心的list我没有写析构函数等,这个也很简单,循环利用成员函数中的删除函数就可以。 先来说说个人认为

    2024年02月11日
    浏览(41)
  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(49)
  • STL标准模板库 vector容器与迭代器入门

    vector 就是一个连续的数据 C++11 std::vector a ={1,4,2,6,7}; 可以使用花括号来定义 容器的功能就是存储数据 迭代器的功能就是指向数据,并且可以实现前后移动(指针)算法和容器的接口的存在 vector功能是长度可变的数组, 身在栈上 里面的数据存储在堆上 因为栈不可动态扩容

    2023年04月23日
    浏览(46)
  • STL常用梳理——VECTOR常用接口及其迭代器实现

    vector是STL中容器之一,特性如下: vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自

    2024年02月05日
    浏览(46)
  • 【c++】list迭代器失效问题

    目录 一、list iterator的使用 二、list的迭代器失效         对于list的迭代器的用法,可以将它看做一个指针(实际要更加复杂)来使用,该指针指向list中的一个节点。         【注意】         (1)begin和end为正向迭代器,对迭代器执行++操作,迭代器向后移动         (2)r

    2024年01月23日
    浏览(40)
  • C++笔记之迭代器失效问题处理

    code review! 参考博文:C++STL迭代器失效的几种情况总结 对于 std::vector 来说,擦除(erase)元素会导致迭代器失效。具体而言

    2024年02月14日
    浏览(39)
  • JPA连接达梦数据库导致auto-ddl失效问题解决

      现象:         项目使用了JPA,并且auto-ddl设置的为update,在连接达梦数据库的时候,第一次启动没有问题,但是后面重启就会报错,发现错误为重复建表,也就是说已经建好的表没有检测到,又重新走的建表流程。经过一天的排查,总结了2个解决方案。  问题的根源:

    2024年02月15日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包