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

相关内容

热门资讯

2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...
灵岩寺外围山脊被刀片式铁丝网围... 11月16日,山东济南有网友发视频称,灵岩寺外围山脊被刀片式铁丝网围挡。视频画面中,一名徒友将铁丝网...
地板预留距离业主担心热胀冷缩 ... 陈先生的新房位于湖州德清,他说这段时间正在铺设木地板,去看了一下,结果发现“没有一个地方是对的”,希...
王传福:中国制造不是抢饭碗,而... 中国新能源汽车正积极拓展海外市场。11月17日,在深圳举办的2026年APEC工商领导人峰会上,比亚...
536分捡漏上北大考生被公派瑞... 11月16日晚,来自河南农村的赵同学宣布即将前往瑞士攻读博士学位,并感谢祖国的资助和老师们的帮助。他...