STL的中心思想是:将数据容器和算法分隔开,彼此独立设计,最后再用黏合剂将它们撮合在一起。容器和算法的泛型化,可以用 C++ 的 class template 和 function template 来实现,而迭代器(Iterator)就是二者的黏合剂了。
1 迭代器的实现
迭代器是一种智能指针,它将指针进行了一层封装,既包含了原生指针的灵活和强大,也加上很多重要的特性,使其能发挥更大的作用以及能更好的使用。指针最常见也最为重要的行为就是内容提领 (dereference) 和成员访问 (member access),迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载,使其具有了遍历复杂数据结构的能力,其遍历机制取决于所遍历的数据结构。
迭代器的“智能”体现在,针对不同的数据容器能够使用统一的方法、函数进行操作,以达到相同的目的。比如:
1 | template<typename T> |
对于不同的数据容器,以上 Iterator 类中的成员函数 operator++ 的实现会各不相同,例如,对于数组的可能实现如下:
1 | //对于数组的实现 |
对于链表,它会有一个类似于 next 的成员函数用于获取下一个结点,其可能实现如下:
1 | template<typename T> |
iterator 的实现首先要对其所指向的对象的实现细节有非常丰富的了解,所以 iterator 为了不暴露所指向对象的信息,干脆就将 iterator 的实现由各个容器的设计者来实现好了。STL 将迭代器的实现交给了容器,每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同,内部实现却不相同,这也直接体现了泛型编程的概念。
2 迭代器的类别
不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。
常用的迭代器按功能强弱分为:
- 输入迭代器:只读
- 输出迭代器:只写
- 正向迭代器:正向遍历迭代器,假设 p 是一个正向迭代器,则 p 支持以下操作:++p,p++,*p。此外,两个正向迭代器可以互相赋值,还可以用
==
和!=
运算符进行比较。 - 双向迭代器:双向迭代器具有正向迭代器的全部功能。除此之外,若 p 是一个双向迭代器,则
--p
和p--
都是有定义的。--p
使得 p 朝和++p
相反的方向移动。 - 随机访问迭代器:随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器,i 是一个整型变量或常量,则 p 还支持以下操作:
- p+=i:使得 p 往后移动 i 个元素。
- p-=i:使得 p 往前移动 i 个元素。
- p+i:返回 p 后面第 i 个元素的迭代器。
- p-i:返回 p 前面第 i 个元素的迭代器。
- p[i]:返回 p 后面第 i 个元素的引用。
此外,两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。p1<p2
的含义是:p1 经过若干次(至少一次)++
操作后,就会等于 p2。其他比较方式的含义与此类似。
对于两个随机访问迭代器 p1、p2,表达式p2-p1
也是有定义的,其返回值是 p2 所指向元素和 p1 所指向元素的序号之差(也可以说是 p2 和 p1 之间的元素个数减一)。
下表是不同容器的迭代器功能类型:
容器 | 迭代器功能 |
---|---|
vector | 随机访问 |
deque | 随机访问 |
list | 双向 |
set / multiset | 双向 |
map / multimap | 双向 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
priority_queue | 不支持迭代器 |
在以上功能的基础上,迭代器根据定义方式还分为:
- 正向迭代器:容器类名::iterator
- 常量正向迭代器:容器类名::const_iterator
- 反向迭代器:容器类名::reverse_iterator
- 常量反向迭代器:容器类名::const_reverse_iterator
反向迭代器和正向迭代器的区别在于:对正向迭代器进行++
操作时,迭代器会指向容器中的后一个元素;而对反向迭代器进行++
操作时,迭代器会指向容器中的前一个元素。
3 迭代器辅助函数
STL 中有用于操作迭代器的三个函数模板,它们是:
advance(p, n)
:使迭代器 p 向前或向后移动 n 个元素。distance(p, q)
:计算两个迭代器之间的距离,即迭代器 p 经过多少次++
操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面,则这个函数会陷入死循环。iter_swap(p, q)
:用于交换两个迭代器 p、q 指向的值。
要使用上述模板,需要包含头文件 <algorithm>
。