C++ 迭代器,了解一下?
声明:本文为转载文章,转载自洛谷日报#34,原作者为Xeonacid。
由于作者是个C++鶸,如果本文有任何错误,烦请不吝指出。(有的地方已知描述是不完整的,但是与指针行为一致,或鉴于多数看这篇文章的都是算法竞赛选手,抑或考虑实际,刻意忽略掉辣)
迭代器是个啥?
迭代器(Iterator):一种“能够迭代某序列内所有元素”的对象
指针都知道吧?不知道的先出门左转了解一下
迭代器:指针的抽象,指针是迭代器的子集
1 |
迭代器能干啥?
所有迭代器都能做的操作:
1 | int main(){ |
emmmm…这些跟指针没什么差别对吧。
真的没差别吗?
其实是有的…
指针不可能随便解引用或者交换一下,甚至你什么都没做,就非法化了对吧。但是就“迭代器”本身,不加任何限制的情况下,其只是一个可以做上述操作的类而已啦,随时有可能被非法化。
1 |
|
很简单对吧,直接从迭代器类型本身拿来了这几个成员,标准库提供了对于指针的特化,毕竟指针没有这些成员。
只有使1
2
3
4
5
6
7
8
9
10
什么?你问我这五个鬼东西干啥用的?~~把他们翻译成中文就好了~~ ←真的如此,STL的命名还是挺清楚的哇
其中标准库自带了五个用于```iterator_category```的空类型,分别对应下方的前五种迭代器:
```cpp
struct output_iterator_tag { };
struct input_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
迭代器分类
- 输出迭代器(OutputIterator)
- 输入迭代器(InputIterator)
- 向前迭代器(ForwardIterator)
- 双向迭代器(BidirectionalIterator)
- 随机访问迭代器(RandomAccessIterator)
- 相接迭代器(ContiguousIterator)
- 可变迭代器(MutableIterator)
迭代器分类的依据是其可以进行的操作
由上至下越来越像指针,
越来越正常
输出迭代器
1 | typedef output_iterator_tag iterator_category; |
可自增(前置/后置、无操作)
可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
返回的还是这个迭代器本身,所以不要做出```a = *it```这种操作,~~伦家明明是输出迭代器不要把窝搞成输入嘛~~~
实际上这个不是输出迭代器标准定义,但是STL中输出迭代器的实例就是这样的
仅资瓷单趟算法
啥是单趟算法?只需要遍历这个序列一次的算法,不需要把当前位置迭代器记存一个副本,等以后再使用。
因为该序列上同一时间可能只有一个位置的迭代器是合法的
输出迭代器这个名字看起来就是用于输出内容的,STL有两个小玩意叫做```std::ostream_iterator```和```std::ostreambuf_iterator```,把输出流包装了一下
```cpp
// 构造一个输出T类型的输出迭代器
// 第一个参数为绑定到的流
// 第二个参数为每次输出后输出的字符串,可省
std::ostream_iterator<T> it(std::cout, " ");
T t;
it = t; //这些都等同于 std::cout << t << " "
*it = t;
it++ = t;
++it = t;
*it++ = t;
// 跟上面那个一样,不过变成输出字符类型,也没有第二个参数了
std::ostreambuf_iterator<char> it(std::cout);
it = 'A'; // 等同于 std::cout << 'A'
*it = 'A';
...
STL还有几个用于插入序列的迭代器适配器,以及配套的为了方便的函数模板
1 | std::deque<int> q; |
输入迭代器
这玩意从名字看上去就与上面那个有许多相似之处,实际上也是
1 | typedef input_iterator_tag iterator_category; |
可后置自增
可默认构造
实际上输入迭代器标准定义不可默认构造,向前迭代器才可以,但是STL中输入迭代器的实例都是可以的
1 |
|
PS:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
~~C++真是一门难学的语言~~
可比较相等和不等
```operator*```返回当前元素
可使用```operator->```访问成员
仅资瓷单趟算法
把输出迭代器的栗子的输出改成输入就好了
emmmmm...等等,那EOF咋判断?
默认构造的输入流迭代器就代表EOF,判一下相等/不等就好了
```cpp
std::vector<int> v;
std::istream_iterator<int> i1(std::cin), i2;
while(i1 != i2) v.push_back(*i1++);
同一个位置的元素可以读多次,不过不能倒回来读
1 | std::istream_iterator<int> i1(std::cin); |
1 |
|
一行结束,简单多了对吧。输出的也同理
别问我这个在算法竞赛中的应用是什么,我知道你们都不会在比赛中用流式输入输出的,但是这些都是C++这门语言的重要组成部分,毕竟C++不是只用来算法竞赛的对吧
向前迭代器
终于到比较正常的用的比较多的了
1 | typedef forward_iterator_tag iterator_category; |
是输入迭代器
1 |
|
可以看成不可自减和随机访问的指针
1
2
3
4
## 双向迭代器
```cpp
typedef bidirectional_iterator_tag iterator_category;
是向前迭代器
可自减
行为与自增都类似
可以看成不可随机访问的指针
1
2
3
4
## 随机访问迭代器
```cpp
typedef random_access_iterator_tag iterator_category;
是向前迭代器
可以在常量时间内移动任意位置
可以做加减法
可以比较大小
可以使用1
2
3
4
5
6
7
8
9
10
11
12
指向数组元素的指针会用吧?一样的
```std::vector, std::array, std::deque, std::string```的```iterator```、指向数组元素的指针
## 相接迭代器
是迭代器
其所指向的逻辑相邻元素也在内存中物理上相邻
任意合法的```*(a + n)```等价于```*(std::addressof(*a) + n)
顺便提一句,为什么是1
2
3
4
因为```operator&```是可以重载的...它可以返回任何奇怪的东西
所以C++11引入了```std::addressof```函数,专门用于返回一个对象的地址,其实现用了一些小trick,C++11及之后所有的标准库实现取地址用的都是这个函数而不是```operator&
那么问题来了,如何在C++11之前将一个重载了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

~~C++真是一门难学的语言~~
```std::vector, std::array, std::basic_string_view```的```iterator```、指向数组元素的指针
## 可变迭代器
是输入迭代器
是输出迭代器
也就是可以读也可以写的
所有STL容器的```iterator```(```const_iterator```除外)、指针(常量指针除外)
## 类型总结

来源cppreference
## 相对用的比较多的迭代器适配器
```std::reverse_iterator
反向迭代器,原迭代器+变-、-变+,提供原迭代器提供的所有功能
STL容器的
1
2
```std::move_iterator
原迭代器需至少为输入迭代器,其reference
为右值引用
关于std::move
和右值引用…那应该是另一篇文章的内容了
迭代器非法化
See https://zh.cppreference.com/w/cpp/container#.E8.BF.AD.E4.BB.A3.E5.99.A8.E9.9D.9E.E6.B3.95.E5.8C.96
适配器均取决于其底层容器
(溜了溜了)
emmmm…还是说几个常见的吧
所有只读操作无
std::vector
扩大重分配、std::deque
插入+扩大重分配+非首尾擦除:全部
std::vector
插入/擦除(无重分配):插入位置及其后
std::deque
首尾擦除(无重分配):首尾
链表+有序关联容器:插入无,擦除仅被擦除元素
(毕竟它们是节点形式出现的)
哈希容器:
插入导致重哈希:全部
插入未导致重哈希:无
擦除:仅被擦除元素
一点废话
在不需要返回值的情况下尽可能使用前置递增/递减,而非后置
后置比前置慢
这个对于内置类型是假的,开不开优化都一样
但是对于非内置类型就不一定了
像迭代器这种实现相对比较简单的类(绝大部分容器的迭代器底层都只是一个或几个指针),开了优化可能会被优化成一样
但是如果是复杂一点的就不一定了2333333
小建议:(求不喜勿喷)干脆全改成前置好了,反正不会慢对吧,要不然写的时候还要想一下是不是内置类型,也挺麻烦的
使用std::array
而非原生数组
窝个人觉得,OOP的封装性的优势在这体现地淋漓尽致,不用管底层怎么搞的,用就好辣
其成员函数什么的都是STL的命名格式,会用一个STL容器就会用其他的(:з」∠)
一维数组还好办,二维及以上的话指针、sizeof
什么的比封装好的麻烦多了(表喷窝TAT,再熟练也改变不了它麻烦的事实呀)
常数这个无需担心,std::array
只是把原生数组封装了一下,效率没有任何差别,成员函数都是内联的
然鹅…这个东西是C++11才有的,C++98的话也可以自己封装一下嘛,几分钟就写完了(逃)
参考资料
ISO/IEC 14882:2017 Programming languages – C++:952-986.
(德)约祖蒂斯(Josuttis,N.M.)著;侯捷译.C++标准库:第2版[M].北京:电子工业出版社,2015.6:433-474.
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏