大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
C++ 迭代器(Iterator)
1.1 定义
- 迭代器是一种检查容器内元素并遍历元素的数据类型。
- 迭代器是一个变量,提供对一个容器中的对象的(间接)访问方法,并且定义了容器中对象的范围。
- 迭代器可以指向容器中的某个元素,通过迭代器就可以对非数组(存储空间不连续)的数据结构进行遍历。
- 容器和string有迭代器类型同时拥有返回迭代器的成员。如:容器有成员 begin 和 end ,其中begin成员复制返回指向第一个元素的迭代器,而end成员返回指向容器尾元素的下一个位置的迭代器,也就是说end指示的是一个不存在的元素,所以end返回的是尾后迭代器。
iterator iter; // 声明迭代器iter
for(iter = 容器.begin(); iter != 容器.end(); iter++){
cout << *iter 或者是 iter->first ;
}
1.2 迭代器种类
- 正向迭代器,定义方法如下:
容器类名::iterator 迭代器名;
- 常量正向迭代器,定义方法如下:
容器类名::const_iterator 迭代器名;
- 反向迭代器,定义方法如下:
容器类名::reverse_iterator 迭代器名;
- 常量反向迭代器,定义方法如下:
容器类名::const_reverse_iterator 迭代器名;
1.3 迭代器的使用
- 通过迭代器可以读取它指向的元素,
*迭代器名
就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。 - 迭代器都可以进行
++
操作。反向迭代器和正向迭代器的区别在于:- 对正向迭代器进行++操作时,迭代器会指向容器中的后一个元素;
begin() -> end() 从前往后遍历
- 对反向迭代器进行++操作时,迭代器会指向容器中的前一个元素。
rbegin() -> rend() 从后往前遍历
- 对正向迭代器进行++操作时,迭代器会指向容器中的后一个元素;
遍历vector容器的所有元素示例:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
for(int i = 0; i < 5; ++i){
v.push_back(i); // v = {0, 1, 2, 3, 4}
}
vector<int>::iterator iter; // 正向迭代 begin -> end,输出 {0, 1, 2, 3, 4}
for(iter = v.begin(); iter != v.end(); ++iter){
cout << *iter << endl;
}
vector<int>::reverse_iterator riter; // 反向迭代 rbegin -> rend,输出 {4, 3, 2, 1, 0}
for(riter = v.rbegin(); riter != v.rend(); ++riter){
cout << *riter << endl;
}
return 0;
}
提示:
后置++
要多生成一个局部对象 tmp,因此执行速度比前置++
的慢。同理,迭代器是一个对象,STL 在重载迭代器的++运算符时,后置形式也比前置形式慢。在次数很多的循环中,++i 和 i++ 可能就会造成运行时间上可观的差别了。对循环控制变量 i,要养成写++i、不写i++的习惯。
1.4 迭代器的功能分类
不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。
例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。
不同容器的迭代器功能:
容器 | 迭代器功能 |
---|---|
forward_list | 前向 |
unordered_set / unordered_multiset | 前向 |
unordered_map / unordered_multimap | 前向 |
vector | 随机访问 |
deque | 随机访问 |
array | 随机访问 |
list | 双向 |
set / multiset | 双向 |
map / multimap | 双向 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
priority_queue | 不支持迭代器 |
不同功能的迭代器说明:
迭代器类别 | 说明 |
---|---|
输入 | 从容器中读取元素。输入迭代器只能一次读入一个元素向前移动,输入迭代器只支持一遍算法,同一个输入迭代器不能两次遍历一个序列 |
输出 | 向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法,同一输出迭代器不能两次遍历一个序列 |
正向 | 组合输入迭代器和输出迭代器的功能,并保留在容器中的位置 |
双向 | 组合正向迭代器和逆向迭代器的功能,支持多遍算法 |
随机访问 | 组合双向迭代器的功能与直接访问容器中任何元素的功能,即可向前向后跳过任意个元素 |
不同功能的迭代器操作:
- 输入:
++p
,p++
,*p
,p1 = p2
,p1 == p2
,p1 != p2
- 输出:
++p
,p++
,*p
,p1 = p2
- 正向迭代:
++p
,p++
,*p
,p1 = p2
,p1 == p2
,p1 != p2
- 双向迭代:
++p
,p++
,*p
,p1 = p2
,p1 == p2
,p1 != p2
,--p
,p--
- 随机访问:
++p
,p++
,*p
,p1 = p2
,p1 == p2
,p1 != p2
,--p
,p--
,p+=i
,p-=i
,p+i
,p-i
,p1 < 、>、<=、>= p2
,p[i]
(返回 p 后面第 i 个元素的引用),p2-p1
(返回 p2 所指向元素和 p1 所指向元素的序号之差)
1.5 迭代器的辅助函数
STL 中有用于操作迭代器的三个函数模板,它们是:
advance(p, n)
:使迭代器 p 向前或向后移动 n 个元素。distance(p, q)
:计算两个迭代器之间的距离,即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面,则这个函数会陷入死循环。iter_swap(p, q)
:用于交换两个迭代器 p、q 指向的值。
参考:
http://c.biancheng.net/view/338.html
https://blog.csdn.net/CSDN_564174144/article/details/76231626
1.6 迭代器的失效问题
不能以指针来看待迭代器,指针是与内存绑定的,而迭代器是与容器里的元素绑定的,删除了之后,该迭代器就失效了,在对其重新赋值之前,不能再访问此迭代器。
STL 迭代器失效的几种情况总结
C++容器类插入和删除时迭代器的失效情况总结
- 序列式(数组式) 容器
vector
迭代器失效
(1)erase() 和 insert() 会使当前位置到容器末尾元素的迭代器全部失效 ;这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置,此时 iter 已经指向的是未知内存;解决方法是利用 erase方法可以返回下一个有效的 iterator。
(2)扩容时,所有迭代器都会失效。deque
迭代器失效
(1)插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用都会失效,但是如果在首尾位置添加元素,迭代器会失效,但是指针和引用不会失效;
(2)如果在首尾之外的任何位置删除元素,那么指向被删除元素外其他元素的迭代器全部失效;
(3)在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。
- 节点式容器:
- 关联式容器(如
map, set,multimap,multiset
)
(1)删除当前的iterator,仅仅会使当前的iterator失效,只要在erase 时,递增当前 iteratorerase(iter++)
或者 利用 erase 返回的有效迭代器iter = cont.erase(iter);
进行操作即可;
(2)插入不会使得任何迭代器失效。
这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。 - 链表式容器(如
list
)
(1)删除当前的iterator,仅仅会使当前的iterator失效,只要在erase 时,递增当前 iteratorerase(iter++)
或者 利用 erase 返回的有效迭代器iter = cont.erase(iter);
进行操作即可;
(2)插入不会使得任何迭代器失效。
这是因为list之类的容器,使用了链表来实现,插入、删除一个结点不会对其他结点造成影响。
- 关联式容器(如
- 哈希容器(
unordered_map, unordered_multimap, unordered_multiset, unordered_set
):
(1)删除当前的iterator,仅仅会使当前的iterator失效,只要在erase 时,递增当前 iteratorerase(iter++)
或者 利用 erase 返回的有效迭代器iter = cont.erase(iter);
进行操作即可;
(2)插入不会使得任何迭代器失效。
这是因为这些容器使用了哈希表来实现,插入、删除一个结点不会对其他结点造成影响。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/210096.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...