C++:vector和list的迭代器区别和常见迭代器失效问题
创始人
2024-06-01 18:50:49
0

迭代器常见问题的汇总

  • vector迭代器和list迭代器的使用
    • vector迭代器
    • list迭代器
  • vector迭代器失效问题
  • list迭代器失效问题
  • vector和list的区别

vector迭代器和list迭代器的使用

学习C++,使用迭代器和了解迭代器失效的原因是每个初学者都需要掌握的,接下来我们就先从使用迭代器开始,帮助大家浅浅的认识一下迭代器究竟是个什么东西

首先有一点我们需要认识到的是,vector和list在内存上是有差异的,vector是连续的一段内存,而list是链表方式建立起来的。

vector迭代器

查询网站–www.cplusplus.com 建议切换到旧版进行查询

在这里插入图片描述
因为本篇文章的重点在于了解迭代器的失效问题,所以这里我们只介绍一下前四个的使用,要想了解的更多,还请大家查询相关的文章。

#include 
#include 
#include 
using namespace std;int main()
{vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//通过迭代器来遍历vector容器auto it = v1.begin();while (it != v1.end()){cout << *it++ << " ";}cout << endl;return 0;
}

我们暂时可以将vector的容器理解成指针,这能更好的帮助我们理解接下来的东西,但是是否真的是指针,是跟编译器有关的,像VS下vector的迭代器就不是指针,而g++下就是使用指针来实现的。

上面我们创建了一个int类型的容器,使用vector就是说明使用的是一段连续的空间(数组),如下图所示:
在这里插入图片描述

begin()就是第一个元素的位置,end()就是最后一个元素的下一个位置,这么看的话我们是否觉得使用迭代器还不如直接使用指针呢?但是别忘了vector是被叫作容器的,看下面的一段代码:

vector s1;s1.push_back("holle");s1.push_back("world");s1.push_back("holle");s1.push_back("iterator");auto lt = s1.begin();while (lt != s1.end()){cout << *lt++ << " ";}cout << endl;

这次我们在容器中放入的是字符串类型,而不是内置类型,这在使用传统的数组是无法办到的,这才是vector容器的价值体现,所以我们C++才需要封装一个叫迭代器的东西以便我们在面对不同的容器的时候都能通过同样的方式去遍历和访问,这一点在list中的体现更大。

list迭代器

在这里插入图片描述

list ls;//链表ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);ls.push_back(5);auto LT = ls.begin();while (LT != ls.end()){cout << *LT++ << " ";}cout << endl;

在使用上是看不出来vector和list的迭代器的差别的,但是我们细想一下的话,就能发现其中并不是那么简单的!

list是一种带头双向循环的链表,那么每个结点就有三个区域
指向下一个结点的next指针
指向前一个结点的prev指针和
数据域data
如图:
在这里插入图片描述
这时如果我们还将迭代器简单的理解为指针的话,那么不妨想一下,如果我们使用++运算符的话,还能找到下一个结点的位置吗?答案是不能的,因为list不像vector一样是一段连续的内存空间,我们如果还以为迭代器是指针的话,那么++的位置只能是结点的下一个位置,但这个位置极大的概率不是下一个结点的位置。
为什么说极大的概率呢?虽然list构建链表的时候,使用的是空间碎片构建的,但是不排除正好是使用的连续的两块地址空间构造的。

那又为什么我们却能像vector一样的去使用list的迭代器呢?
而且*就是访问的数据,++和- -就能找到结点的后一个结点和前一个结点。

这都归功于类的封装,在对迭代器封装的时候,重新的定义了这些符号的意义(++, - - , *)
也就是符号的重载。这才使得我们能就像使用指针一样去使用迭代器,但实际上它们的底层早已千差万别。

迭代器的封装具体是怎做到,可以看一下这里的代码(list的模拟实现),这里就模拟了一份迭代器的封装,重要的不是看懂这些代码,而是认识到迭代器并不是简单的指针
代码:

//结点templatestruct list_node{list_node* next;list_node* prev;T _data;list_node(const T& x = T())//所以要实现默认构造函数:next(nullptr), prev(nullptr), _data(x){}};// 1、迭代器要么就是原生指针// 2、迭代器要么就是自定义类型对原生指针的封装,模拟指针的行为//这里如果单纯的使用结点的指针作为迭代器的话,是没法用++等操作符操作的,所以我们对结点的迭代器进行了//封装!!!template//模板参数一个一个的去理解 1.先不考虑const对象的情况struct _list_iterator{//迭代器内部并不需要进行析构,因为这个类对结点的指针进行了封装,以便我们能够更好的访问链表typedef list_node node;node* _node;typedef _list_iterator self;//构造出一个结点的指针,初始化这个指针的指向为我们想要的结点的位置_list_iterator(node* n):_node(n){}//const T* operator->()Ptr operator->()  //优雅!{return &_node->_data;//取地址}Ref operator*()  //Ref-->const T&  / Ref-->T&  !!!!优雅{return _node->_data;}self& operator++() //前置++{_node = _node->next;return *this;}self operator++(int) //后置++{self temp(*this);_node = _node->next;return temp;//返回的是++之前的位置,也就是原来的位置,但是迭代器已经向后移动了}self& operator--(){_node = _node->prev;return *this;}self operator--(int){self temp(*this);_node = _node->prev;return temp;}//bool operator!=(self n)//权限的放大和缩小只针对引用和指针类型bool operator!=(const self& n){return _node != n._node;}bool operator==(const self& n){return _node == n._node;}};templateclass list{typedef list_node node;public://第三个模板参数是类型指针,为了重载->时使用typedef _list_iterator iterator;typedef _list_iterator const_iterator;void empty_init(){_head = new node;_head->next = _head;_head->prev = _head;}//构造函数--创建头结点list(){empty_init();}templatelist(iterator first, iterator second){empty_init();while (first != second){push_back(*first);++first;}}void swap(list& temp){std::swap(_head, temp._head);}list(const list& lt){empty_init();list temp(lt.begin(), lt.end());swap(temp);}/*list(const list& lt){empty_init();for (auto e : lt){push_back(e);}}*/list& operator=(list lt)//这里不能使用引用,会改变原来list的数据{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);//后置++}}iterator begin(){return iterator(_head->next);//头结点的下一个就是第一个结点的位置}iterator end(){return iterator(_head);//头结点就是end结点的位置}const_iterator begin() const{return const_iterator(_head->next);}const_iterator end() const{return const_iterator(_head);}void insert(iterator pos, const T& val){node* cur = pos._node;//当前位置node* pre = cur->prev;//pos的前一个位置node* new_node = new node(val);//开始插入pre->next = new_node;new_node->prev = pre;new_node->next = cur;cur->prev = new_node;}iterator erase(iterator pos){assert(pos != _head);node* pre = pos._node->prev;//pos位置的前一个node* next = pos._node->next;//pos位置的后一个pre->next = next;next->prev = pre;delete pos._node;return iterator(next);//返回的是删除位置的下一个位置}void push_back(const T& val){创建结点//node* new_node = new node(val);//node* tail = _head->prev;//链表的最后一个结点的位置尾插过程//tail->next = new_node;//new_node->prev = tail;//new_node->next = _head;//_head->prev = new_node;insert(end(), val);//复用}void pop_back(){//erase(_head->prev);erase(--end());}void push_front(const T& val){//insert(_head->next);insert(begin(), val);}void pop_front(){//erase(_head->next);erase(begin());}private:node* _head;//头结点指针};

这份代码也是模拟实现list的完整代码。

vector迭代器失效问题

int main()
{vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//通过迭代器来遍历vector容器auto it = find(v1.begin(), v1.end(), 3);//在begin()--end()的区间内查找1v1.erase(it);v1.insert(it, 0);for (auto e : v1){cout << e << " ";}cout << endl;
}

上面代码的意思就是找到3的并删除掉他,然后再在该位置插入0。
按照理解这段代码应该是没有问题的,就是很简单的一段删除和插入嘛。

结果:
在这里插入图片描述
代码崩了?

这里就是很典型的迭代器失效问题,迭代器it原本指向的是3的位置,之后我们将他删除后,it指向的数据是4,不再是原数据了,这就是迭代器的失效。对于迭代器失效VS是assert断言处理的,所以我们才看到上面的信息。
同样- -也会导致一样的问题。
解决办法就是it接收一下erase的返回值,erase的返回值是该位置的下一个位置的迭代器。这样就能有效的避免上面的问题。
在这里插入图片描述

还有一种迭代器失效是在insert时导致的。

假如我们一开始的容器大小是5个,且这个容器已经满了,此时我再进行insert的时候,就会发生扩容。
而C++的扩容是异地扩容的,并没有像C语言的realloc函数一样的接口。

异地扩容就必定会导致一个问题,我们原来it指向的地址发生了改变,此时如果不做处理的话,it指向的就是一块未知的空间,it就变成了一个野指针,这也是一种迭代器的失效。

这个问题在大家模拟实现vector的时候是特别需要注意的一点。

list迭代器失效问题

list的迭代器在删除时也会导致和上面相同的问题,解决办法也是接受一下erase的返回值,同样list的erase的返回值也是该位置的下一个结点位置(next)。

但是list在插入的时候并不会导致迭代器失效,因为list不存在扩容的概念。
在这里插入图片描述

在这里插入图片描述
list就不存在扩容的问题了。

vector和list的区别

  1. vector可以随机访问,通过[ ],而list不支持随机访问。vector访问某个元素的效率为O(1)
    list访问某个元素的效率为O(n)。

  2. vector中插入和删除都可能导致迭代器失效,而list中插入元素不会导致迭代器失效,删除元素会导致迭代器失效;
    vector中插入元素有可能需要增容,迭代器指向的之前的空间会被释放,之前的迭代器会失效;删除元素也会导致迭代器失效;
    list中插入元素只是添加了一个新的节点,不会导致之前存在的迭代器失效,而删除元素只会导致当前迭代器失效,其他迭代器不会受到影响。

  3. vector中的迭代器是原生态指针,也就是元素类型的指针(vs下不是,g++是); list中的迭代器是对原生态指针(节点指针)的封装;

上一篇:3/11 考试总结

下一篇:Face Forgery Suvery

相关内容

热门资讯

安卓系统相机不能启动,安卓相机... 手机里的安卓系统相机突然不能启动了,这可真是让人头疼啊!你有没有遇到过这种情况呢?别急,今天就来跟你...
安卓原生系统时间校准,基于安卓... 手机时间不准了?别急,我来教你如何轻松搞定安卓原生系统时间校准! 话题引入:手机时间不准,是不是让你...
主机系统内存和安卓联机,主机系... 你有没有想过,为什么你的手机在玩大型游戏时总是卡得要命?又或者,为什么你的电脑在处理复杂任务时,反应...
安卓如何手机上刷系统,轻松升级... 你有没有想过,你的安卓手机是不是已经有点儿“老态龙钟”了呢?别急,别急,今天就来教你怎么给它来个“青...
苹果系统观战安卓好友,观战新体... 亲爱的读者,你是否也有过这样的经历:一边享受着苹果系统的优雅与流畅,一边又忍不住好奇地观战安卓好友们...
安卓系统最好是哪个,最佳生成方... 你有没有想过,手机里的安卓系统哪个才是最适合你的呢?在这个信息爆炸的时代,手机已经成为了我们生活中不...
改时间安卓系统vivo,探索v... 你有没有发现,最近你的vivo手机有点儿“慢吞吞”的?别急,别急,让我来给你支个招儿,让你的安卓系统...
安卓系统的旋钮在哪,旋钮生成位... 你有没有发现,有时候手机上的小细节也能让人头疼不已?比如说,安卓系统的旋钮在哪?这问题看似简单,但不...
安卓手机app系统软件,探索安... 你有没有发现,现在手机里的app简直就像是个小宇宙,各种功能应有尽有,让人眼花缭乱。尤其是安卓手机,...
win111安卓子系统,开启跨... 哇,你有没有听说最近的大新闻?那就是Windows 11的安卓子系统!是的,你没听错,Windows...
游戏摇杆连安卓系统电视,畅享游... 你有没有想过,家里的安卓系统电视也能玩起游戏来?没错,就是那种让你手舞足蹈、热血沸腾的游戏摇杆!今天...
nokia平板系统兼容安卓,尽... 你有没有想过,那些曾经陪伴我们度过无数时光的诺基亚手机,现在竟然也能摇身一变,成为平板电脑的得力助手...
安卓原生系统是什么品牌,探索安... 你有没有想过,为什么你的手机那么流畅,界面那么美观?这背后,可是有一个强大的“大脑”在默默支撑着呢!...
安卓3大操作系统,从三大分支看... 你知道吗?在安卓的世界里,操作系统可是有着三大巨头呢!它们就像安卓世界的三驾马车,各自有着独特的魅力...
开源文件管理系统安卓,打造个性... 你有没有想过,手机里那些乱糟糟的文件,要是能有个好帮手,生活该有多轻松啊?今天,就让我带你走进一个神...
手机删除了系统安卓市场,手机系... 手机里的安卓市场突然不见了,这可怎么办呢?别急,让我来给你详细说说这个棘手的问题,让你轻松应对!一、...
安卓系统写脚本软件下载,基于安... 你有没有想过,你的安卓手机或者平板电脑,除了用来刷剧、玩游戏,还能变成一个强大的工作助手呢?没错,就...
安卓系统有哪些机型好,探索顶级... 你有没有想过,安卓系统里的手机型号那么多,哪一款才是最适合你的呢?别急,今天我就来给你好好盘点看看安...
安卓系统之间如何互传,安卓设备... 你是不是也和我一样,手机里存了那么多好东西,却苦于不能和好友分享呢?别急,今天就来教你怎么用安卓系统...
安卓系统启动修改工具,安卓系统... 你有没有想过,你的安卓手机启动速度竟然可以像火箭一样快?没错,这就是今天我要跟你分享的神秘工具——安...