0%

【STL】迭代器

STL的中心思想是:将数据容器和算法分隔开,彼此独立设计,最后再用黏合剂将它们撮合在一起。容器和算法的泛型化,可以用 C++ 的 class template 和 function template 来实现,而迭代器(Iterator)就是二者的黏合剂了。

1 迭代器的实现

迭代器是一种智能指针,它将指针进行了一层封装,既包含了原生指针的灵活和强大,也加上很多重要的特性,使其能发挥更大的作用以及能更好的使用。指针最常见也最为重要的行为就是内容提领 (dereference) 和成员访问 (member access),迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载,使其具有了遍历复杂数据结构的能力,其遍历机制取决于所遍历的数据结构。

迭代器的“智能”体现在,针对不同的数据容器能够使用统一的方法、函数进行操作,以达到相同的目的。比如:

1
2
3
4
5
6
7
8
9
10
11
template<typename T>  
class Iterator
{
public:
Iterator& operator++();

...

private:
T *m_ptr;
};

对于不同的数据容器,以上 Iterator 类中的成员函数 operator++ 的实现会各不相同,例如,对于数组的可能实现如下:

1
2
3
4
5
6
7
//对于数组的实现  
template<typename T>
Iterator& operator++()
{
++m_ptr;
retrun *this;
}

对于链表,它会有一个类似于 next 的成员函数用于获取下一个结点,其可能实现如下:

1
2
3
4
5
6
template<typename T>  
Iterator& operator++()
{
m_ptr = m_ptr->next();//next()用于获取链表的下一个节点
return *this;
}

iterator 的实现首先要对其所指向的对象的实现细节有非常丰富的了解,所以 iterator 为了不暴露所指向对象的信息,干脆就将 iterator 的实现由各个容器的设计者来实现好了。STL 将迭代器的实现交给了容器,每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同,内部实现却不相同,这也直接体现了泛型编程的概念。

2 迭代器的类别

不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。

常用的迭代器按功能强弱分为:

  • 输入迭代器:只读
  • 输出迭代器:只写
  • 正向迭代器:正向遍历迭代器,假设 p 是一个正向迭代器,则 p 支持以下操作:++p,p++,*p。此外,两个正向迭代器可以互相赋值,还可以用==!=运算符进行比较。
  • 双向迭代器:双向迭代器具有正向迭代器的全部功能。除此之外,若 p 是一个双向迭代器,则--pp-- 都是有定义的。--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>

---- 本文结束 知识又增加了亿点点!----

文章版权声明 1、博客名称:LycTechStack
2、博客网址:https://lz328.github.io/LycTechStack.github.io/
3、本博客的文章部分内容可能来源于网络,仅供大家学习与参考,如有侵权,请联系博主进行删除处理。
4、本博客所有文章版权归博主所有,如需转载请标明出处。