# 迭代器
# 1. 迭代器是什么
对于vector,我们可以用下标遍历:
for(int i = 0; i < v.size(); i++)
cout << v[i] << endl;
1
2
2
也可以用迭代器遍历:
for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
cout << *it << endl;
1
2
2
a.begin()
是一个迭代器,指向的是第一个元素a.end()
是一个迭代器,指向的是最后一个元素再后面一位上述迭代器具有自增运算符,自增则迭代器向下一个元素移动
迭代器与指针相似,如果对它使用解引用运算符,即
*it
,就能取到对应值了
# 2. 为何需要迭代器
很多数据结构并不是线性的(例如红黑树),对于非线性数据结构,下标是无意义的。无法使用下标来遍历整个数据结构。
迭代器的作用就是定义某个数据结构的遍历方式,通过迭代器的增减,代表遍历到的位置,通过迭代器便能成功遍历非线性结构了。
例如,set 的实现是红黑树,我们是没法用下标来访问元素的。但是通过迭代器,我们就能遍历 set 中的元素了:
for(set<int>::iterator it = st.begin(); it != st.end(); ++it)
cout << *it << endl;
1
2
2
# 3. 迭代器用法
对于 vector 容器,它的迭代器功能比较完善,以它举例:
.begin()
:头迭代器.end()
:尾迭代器.rbegin()
:反向头迭代器.rend()
:反向尾迭代器- 迭代器 + 整型:将迭代器向后移动
- 迭代器 - 整型:将迭代器向前移动
- 迭代器
++
:将迭代器向后移动一位 - 迭代器
--
:将迭代器向后移动一位 - 迭代器
-
迭代器:两个迭代器的距离 prev(it)
:返回it的前一个迭代器next(it)
:返回it的后一个迭代器
对于其他容器,由于其结构特性,上面的功能不一定都有(例如 set 的迭代器是不能相减求距离的)。
# 4. 常见问题
.end()
和.rend()
指向的位置是无意义的值
对于一个长度为 10 的数组:for(int i = 0; i < 10; i++)
,第 10 位是不可访问的
对于一个长度为 10 的容器:for(auto it = a.begin(); it != a.end(); ++it)
,.end 是不可访问的
不同容器的迭代器功能可能不一样
迭代器细化的话有正向、反向、双向,每个容器的迭代器支持的运算符也可能不同,因此不同容器的迭代器细节很有可能是不一样的。
删除操作时需要警惕
为什么3没删掉?
vector<int> a{1, 2, 3, 4};
for(auto it = a.begin(); it != a.end(); ++it)
if(*it == 2 || *it == 3)
a.erase(it);
// a = [1, 3, 4]
//原因:当删除2后,it指向3,然后++it,就直接跳过访问3了
1
2
3
4
5
6
2
3
4
5
6
为什么RE了?
vector<int> a{1, 2, 3, 4};
for(auto it = a.begin(); it != a.end(); ++it)
if(*it == 4)
a.erase(it);
//原因:当删除4后,it等于a.end()了,然后++it,就越界了
1
2
3
4
5
2
3
4
5