迭代器

一、实验内容

本节实验我们将为大家讲解迭代器，主要介绍 5 种常见迭代器：输入、输出迭代器，前向逆向迭代器，双向迭代器和随机迭代器。主要内容包括各自的构造方法和操作方法。

1.1 知识点

  • 输出迭代器
  • 输入迭代器
  • 前向迭代器
  • 双向迭代器
  • 随机迭代器
  • 迭代器辅助函数

1.2 实验环境

  • g++
  • ubuntu 16.04

1.3 代码获取

可以通过以下链接获取本课程的源码内容，本次实验内容主要包含在文件Iterator.h。

1
2
3
//获取代码
wget https://labfile.oss.aliyuncs.com/courses/1166/mySTL.zip
unzip -q mySTL.zip -d ./Code/

二、迭代器详述

迭代器（iterator）是一种对象，它能够用来遍历标准模板库容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口，所谓迭代器是一种概念上的抽象：那些行为上像迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有机的统一起来。迭代器基本分为五种，输入输出迭代器，前向逆向迭代器，双向迭代器和随机迭代器。

简单概括：迭代器是一种检查容器内元素并遍历元素的可带泛型数据类型。

下面，我们新建头文件Iterator.h是头文件，用来实现我们的迭代器，这里的代码需要引用到系统头文件#include <cstddef>，它主要用于定义一些类型。接下来我们定义 5 种迭代器的类型，将其写入Iterator.h文件中：

1
2
3
4
5
struct input_iterator_tag{};//返回输入迭代器
struct output_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 {};//返回随机迭代器

2.1 输入迭代器

通过对输入迭代器解除引用，它将引用对象，而对象可能位于集合中。通常用于传递地址。

1
2
3
4
5
6
7
8
template<class T, class Distance>
struct input_iterator {
    typedef input_iterator_tag iterator_category;//返回类型
    typedef T                  value_type;//所指对象类型
    typedef Distance           difference_type;//迭代器间距离类型
    typedef T*                 pointer;//操作结果类型
    typedef T&                 reference;//解引用操作结果类型
};

2.2 输出迭代器

该类迭代器和输入迭代器极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。通常用于返回地址。

1
2
3
4
5
6
7
struct output_iterator{
    typedef output_iterator_tag iterator_category;
    typedef void                value_type;
    typedef void                difference_type;
    typedef void                pointer;
    typedef void                reference;
};

2.3 前向迭代器

前向迭代器可以在一个正确的区间中进行读写操作，它拥有输入迭代器的所有特性，和输出迭代器的部分特性，以及单步向前迭代元素的能力。通常用于遍历。

1
2
3
4
5
6
7
template <class T, class Distance> struct forward_iterator{
    typedef forward_iterator_tag    iterator_category;
    typedef T                        value_type;
    typedef Distance                difference_type;
    typedef T*                        pointer;
    typedef T&                        reference;
};

2.4 双向迭代器

该类迭代器是在前向迭代器的基础上提供了单步向后迭代元素的能力，前向迭代器的高级版。

1
2
3
4
5
6
7
template <class T, class Distance> struct bidirectional_iterator{
    typedef bidirectional_iterator_tag    iterator_category;
    typedef T                        value_type;
    typedef Distance                difference_type;
    typedef T*                        pointer;
    typedef T&                        reference;
};

2.5 随机迭代器

该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。

1
2
3
4
5
6
7
template <class T, class Distance> struct random_access_iterator{
    typedef random_access_iterator_tag    iterator_category;
    typedef T                        value_type;
    typedef Distance                difference_type;
    typedef T*                        pointer;
    typedef T&                        reference;
};