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

相关内容

热门资讯

国产系统能否代替安卓,迈向替代... 最近国产系统可是火得一塌糊涂,大家都在讨论它能不能取代安卓呢!咱们就来聊聊这个话题,看看国产系统到底...
安卓原生系统流畅吗,流畅体验背... 亲爱的手机控们,今天咱们来聊聊安卓原生系统,这个看似简单却充满魅力的系统到底流畅不流畅呢?咱们得从多...
安卓降低系统版本好处,揭秘降低... 亲爱的手机控们,你们有没有想过,手机系统升级后,有时候反而不如原来的版本用着顺心呢?没错,今天咱们就...
创维酷开系统变安卓系统,轻松切... 你家的创维酷开电视是不是觉得有点儿“老气横秋”,想要给它来个“青春焕发”的变身呢?别急,今天就来手把...
如何更改安卓系统亮度,安卓系统... 亲爱的手机控们,你是否曾在夜晚被手机屏幕的亮光刺得睁不开眼?或者,在阳光明媚的午后,屏幕的亮度让你无...
安卓系统常用操作软件,安卓系统... 你刚入手了一部安卓手机,是不是有点小激动呢?别急,别急,让我这个手机达人带你一起探索安卓系统的奇妙世...
电脑安装纯净安卓系统,轻松体验... 你有没有想过,在电脑上也能装个安卓系统,就像在手机上那样玩玩游戏、刷刷视频呢?没错,这可不是天方夜谭...
安卓系统浏览pdf文件,操作指... 你有没有遇到过这种情况?手机里一堆PDF文件,打开一看,哎呀妈呀,密密麻麻的字,眼睛都花了!别急,今...
安卓系统动画60帧,性能优化与... 亲爱的手机控们,你们有没有想过,为什么你的安卓手机在滑动屏幕时,有时候会感觉有点卡呢?别急,今天就来...
ios系统无法观战安卓系统王者... 你是不是也遇到了这样的烦恼?想看朋友在王者荣耀里的精彩操作,却发现iOS系统无法观战安卓系统?别急,...
电脑装安卓系统上网,轻松上网新... 你有没有想过,在电脑上也能畅游安卓的海洋呢?没错,就是那个你手机里常用的安卓系统,现在也能在你的电脑...
安卓系统应用怎么重装,安卓应用... 手机里的安卓系统突然卡成“龟速”,是不是让你头疼不已?别急,今天就来教你怎么给安卓手机里的应用来个“...
赚钱的软件安卓系统,指尖上的财... 手机里的时间总是过得飞快,是不是你也和我一样,总想找点乐子还能赚点小钱呢?别急,今天就来给你揭秘安卓...
安卓手机系统更新排行,小米MI... 手机系统更新大揭秘:安卓系统更新排行大盘点亲爱的手机控们,你是否也像我一样,对手机系统更新充满好奇?...
飞智手柄安卓系统,畅享多平台游... 你有没有想过,玩游戏的时候,如果不用手指戳屏幕,而是像玩掌机一样,用个手柄来操作,那会是怎样的体验呢...
安卓可以装系统吗,探索安装其他... 你有没有想过,你的安卓手机不仅能打电话、发短信,还能装上全新的操作系统呢?没错,安卓系统不仅可以装在...
安卓系统隐藏游戏下载,解锁隐藏... 你有没有发现,你的安卓手机里竟然藏着一些神秘的小游戏?没错,就是那些你平时可能从未留意到的隐藏游戏!...
声控导航软件安卓系统,安卓系统... 你有没有想过,开车的时候,双手可以完全解放,导航还能跟着你的声音走?这就是今天要聊的神奇玩意儿——声...
安卓进入系统就卡,安卓系统启动... 亲爱的手机控们,你们有没有遇到过这种情况:新买的安卓手机,刚进入系统就感觉卡得要命,仿佛在跟你的耐心...
迷你电脑主机 安卓系统,安卓系... 你有没有想过,家里的电视、投影仪,甚至是智能手表,它们竟然都悄悄地换上了安卓的“新衣”?没错,安卓系...