迭代器适配器

通过学习 C++ STL 标准库中的容器我们知道，无论是序列式容器还是关联式容器（包括哈希容器），要想遍历容器中存储的数据，就只能用使用该容器模板类中提供的迭代器。

C++ STL 标准库中迭代器大致分为 5 种类型，分别是输入迭代器、输出迭代器、前向迭代器、双向迭代器以及随机访问迭代器。值得一提的是，这 5 种迭代器是 STL 标准库提供的最基础的迭代器，很多场景中遍历容器的需求，它们并不适合。

举个例子，假设有一个 list 容器，现在需要逆序输出该容器中存储的所有元素。要知道，list 容器模板类提供的是双向迭代器，如果使用该类型迭代器实现逆序操作，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> values{1,2,3,4,5};
    //找到遍历的开头位置和结尾位置
    std::list<int>::iterator begin = --values.end();
    std::list<int>::iterator end = --values.begin();
    //开始遍历
    while (begin != end)
    {
        cout << *begin << " ";
        --begin;
    }
    return 0;
}

程序执行结果为：

5 4 3 2 1

相比上面这种实现思路，C++ STL 标准库中还提供有更简单的方法，就是使用迭代器适配器。

关于适配器，在讲解容器适配器时就已经做过详细的讲解，这里不再做过多赘述。

所谓迭代器适配器，其本质也是一个模板类，比较特殊的是，该模板类是借助以上 5 种基础迭代器实现的。换句话说，迭代器适配器模板类的内部实现，是通过对以上 5 种基础迭代器拥有的成员方法进行整合、修改，甚至为了实现某些功能还会添加一些新的成员方法。由此，将基础迭代器“改头换面”，就变成了本节要讲的迭代器适配器。

本质上讲，迭代器适配器仍属于迭代器，可以理解为是基础迭代器的“翻新版”或者“升级版”。同时，“xxx 迭代器适配器”通常直接称为“xxx 迭代器”。

STL迭代器适配器种类

C++ 11 标准中，迭代器适配器供有 4 类，它们各自的名称和功能如表中所示。

名称 功能
反向迭代器（reverse_iterator） 又称“逆向迭代器”，其内部重新定义了递增运算符（++）和递减运算符（–），专门用来实现对容器的逆序遍历。
安插型迭代器（inserter或者insert_iterator） 通常用于在容器的任何位置添加新的元素，需要注意的是，此类迭代器不能被运用到元素个数固定的容器（比如 array）上。
流迭代器（istream_iterator / ostream_iterator) 流缓冲区迭代器（istreambuf_iterator / ostreambuf_iterator） 输入流迭代器用于从文件或者键盘读取数据；相反，输出流迭代器用于将数据输出到文件或者屏幕上。输入流缓冲区迭代器用于从输入缓冲区中逐个读取数据；输出流缓冲区迭代器用于将数据逐个写入输出流缓冲区。
移动迭代器（move_iterator） 此类型迭代器是 C++ 11 标准中新添加的，可以将某个范围的类对象移动到目标范围，而不需要通过拷贝去移动。

反向迭代器适配器（reverse_iterator）

反向迭代器适配器（reverse_iterator），可简称为反向迭代器或逆向迭代器，常用来对容器进行反向遍历，即从容器中存储的最后一个元素开始，一直遍历到第一个元素。

值得一提的是，反向迭代器底层可以选用双向迭代器或者随机访问迭代器作为其基础迭代器。不仅如此，通过对 ++（递增）和 –（递减）运算符进行重载，使得：

  • 当反向迭代器执行 ++ 运算时，底层的基础迭代器实则在执行 – 操作，意味着反向迭代器在反向遍历容器；
  • 当反向迭代器执行 – 运算时，底层的基础迭代器实则在执行 ++ 操作，意味着反向迭代器在正向遍历容器。

反向迭代器的创建

实现反向迭代器的模板类定义在  头文件，并位于 std 命名空间中。因此，在使用反向迭代器时，需包含如下语句：

1
2
#include <iterator>
using namespace std;

注意，第二行代码不是必需的，但如果不用，则程序中只要创建该迭代器时，必须手动注明 std 命名空间（强烈建议初学者使用）。

反向迭代器的模板类定义如下：

1
2
template <class Iterator>
    class reverse_iterator;

注意，Iterator 模板参数指的是模板类中所用的基础迭代器的类型，只能选择双向迭代器或者随机访问迭代器。

这意味着，如果想使用反向迭代器实现逆序遍历容器，则该容器的迭代器类型必须是双向迭代器或者随机访问迭代器。

reverse_iterator 模板类中共提供了 3 种创建反向迭代器的方法，这里以 vector 容器的随机访问迭代器作为基础迭代器为例。

1.
调用该类的默认构造方法，即可创建了一个不指向任何对象的反向迭代器，例如：

1
std::reverse_iterator<std::vector<int>::iterator> my_reiter;

由此，我们就创建好了一个没有指向任何对象的 my_reiter 反向迭代器。

2.
当然，在创建反向迭代器的时候，我们可以直接将一个基础迭代器作为参数传递给新建的反向迭代器。例如：

1
2
3
4
//创建并初始化一个 myvector 容器
std::vector<int> myvector{1,2,3,4,5};
//创建并初始化 my_reiter 迭代器
std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.end());

我们知道，反向迭代器是通过操纵内部的基础迭代器实现逆向遍历的，但是反向迭代器的指向和底层基础迭代器的指向并不相同。以上面创建的 my_reiter 为例，其内部的基础迭代器指向的是 myvector 容器中元素 5 之后的位置，但是 my_reiter 指向的却是元素 5。

也就是说，反向迭代器的指向和其底层基础迭代器的指向具有这样的关系，即反向迭代器的指向总是距离基础迭代器偏左 1 个位置；反之，基础迭代器的指向总是距离反向迭代器偏右 1 个位置处。它们的关系如图所示。

其中，begin 和 end 表示基础迭代器，r(begin) 和 r(end) 分别表示有 begin 和 end 获得的反向迭代器。

3.
除了第 2 种初始化方式之外，reverse_iterator 模板类还提供了一个复制（拷贝）构造函数，可以实现直接将一个反向迭代器复制给新建的反向迭代器。比如：

1
2
3
4
5
//创建并初始化一个 vector 容器
std::vector<int> myvector{1,2,3,4,5};
//调用复制构造函数初始化反向迭代器的 2 种方式
std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.rbegin());
//std::reverse_iterator<std::vector<int>::iterator> my_reiter = myvector.rbegin();

由此，my_reiter 反向迭代器指向的就是 myvector 容器中最后一个元素（也就是 5）之后的位置。

reverse_iterator模板类的成员

前面在学习每一种容器时，都提供有大量的成员函数。但迭代器模板类不同，其内部更多的是对运算符的重载。

reverse_iterator重载的运算符：

重载运算符 功能
operator* 以引用的形式返回当前迭代器指向的元素。
operator+ 返回一个反向迭代器，其指向距离当前指向的元素之后 n 个位置的元素。此操作要求基础迭代器为随机访问迭代器。
operator++ 重载前置 ++ 和后置 ++ 运算符。
operator+= 当前反向迭代器前进 n 个位置，此操作要求基础迭代器为随机访问迭代器。
operator- 返回一个反向迭代器，其指向距离当前指向的元素之前 n 个位置的元素。此操作要求基础迭代器为随机访问迭代器。
operator– 重载前置 – 和后置 – 运算符。
operator-= 当前反向迭代器后退 n 个位置，此操作要求基础迭代器为随机访问迭代器。
operator-> 返回一个指针，其指向当前迭代器指向的元素。
operator[n] 访问和当前反向迭代器相距 n 个位置处的元素。

插入迭代器适配器（insert_iterator）

插入迭代器适配器（insert_iterator），简称插入迭代器或者插入器，其功能就是向指定容器中插入元素。值得一提的是，根据插入位置的不同，C++ STL 标准库提供了 3 种插入迭代器，如表所示。

C++ STL插入迭代器适配器种类:

迭代器适配器 功能
back_insert_iterator 在指定容器的尾部插入新元素，但前提必须是提供有 push_back() 成员方法的容器（包括 vector、deque 和 list）。
front_insert_iterator 在指定容器的头部插入新元素，但前提必须是提供有 push_front() 成员方法的容器（包括 list、deque 和 forward_list）。
insert_iterator 在容器的指定位置之前插入新元素，前提是该容器必须提供有 insert() 成员方法。

back_insert_iterator迭代器

back_insert_iterator 迭代器可用于在指定容器的末尾处添加新元素。

需要注意的是，由于此类型迭代器的底层实现需要调用指定容器的 push_back() 成员方法，这就意味着，此类型迭代器并不适用于 STL 标准库中所有的容器，它只适用于包含 push_back() 成员方法的容器。

C++ STL 标准库中，提供有 push_back() 成员方法的容器包括 vector、deque 和 list。

另外，back_insert_iterator 迭代器定义在  头文件，并位于 std 命名空间中，因此在使用该类型迭代器之前，程序应包含如下语句：

1
2
#include <iterator>
using namespace std;

注意，第二行代码不是必需的，但如果不用，则程序中只要创建该类型的迭代器，就必须手动注明 std 命名空间（强烈建议初学者使用）。

和反向迭代器不同，back_insert_iterator 插入迭代器的定义方式仅有一种，其语法格式如下：

std::back_insert_iterator back_it (container);

其中，Container 用于指定插入的目标容器的类型；container 用于指定具体的目标容器。

front_insert_iterator迭代器

和 back_insert_iterator 正好相反，front_insert_iterator 迭代器的功能是向目标容器的头部插入新元素。

并且，由于此类型迭代器的底层实现需要借助目标容器的 push_front() 成员方法，这意味着，只有包含 push_front() 成员方法的容器才能使用该类型迭代器。

C++ STL 标准库中，提供有 push_front() 成员方法的容器，仅有 deque、list 和 forward_list。

另外，front_insert_iterator 迭代器定义在  头文件，并位于 std 命名空间中，因此在使用该类型迭代器之前，程序应包含如下语句：

1
2
#include <iterator>
using namespace std;

值得一提的是，定义 front_insert_iterator 迭代器的方式和 back_insert_iterator 完全相同，并且 C++ STL 标准库也提供了 front_inserter() 函数来快速创建该类型迭代器。

insert_iterator迭代器

当需要向容器的任意位置插入元素时，就可以使用 insert_iterator 类型的迭代器。

需要说明的是，该类型迭代器的底层实现，需要调用目标容器的 insert() 成员方法。但幸运的是，STL 标准库中所有容器都提供有 insert() 成员方法，因此 insert_iterator 是唯一可用于关联式容器的插入迭代器。

和前 2 种插入迭代器一样，insert_iterator 迭代器也定义在  头文件，并位于 std 命名空间中，因此在使用该类型迭代器之前，程序应包含如下语句：

1
2
#include <iterator>
using namespace std;

不同之处在于，定义 insert_iterator 类型迭代器的语法格式如下：

1
std::insert_iterator<Container> insert_it (container,it);

其中，Container 表示目标容器的类型，参数 container 表示目标容器，而 it 是一个基础迭代器，表示新元素的插入位置。

和前 2 种插入迭代器相比，insert_iterator 迭代器除了定义时需要多传入一个参数，它们的用法完全相同。除此之外，C++ STL 标准库中还提供有 inserter() 函数，可以快速创建 insert_iterator 类型迭代器。

本节讲解了 3 种插入迭代器，虽然它们都可以借助重载的赋值运算符，实现向目标容器的指定位置插入新元素，但在实际应用中，它们通常和 copy() 函数连用，即作为 copy() 函数的第 3 个参数。有关copy()函数，后续讲解

流迭代器(istream_iterator和ostream_iterator)

流迭代器也是一种迭代器适配器，不过和之前讲的迭代器适配器有所差别，它的操作对象不再是某个容器，而是流对象。即通过流迭代器，我们可以读取指定流对象中的数据，也可以将数据写入到流对象中。

介于流对象又可细分为输入流对象（istream）和输出流对象（ostream），C++ STL 标准库中，也对应的提供了 2 类流迭代器：

  • 将绑定到输入流对象的迭代器称为输入流迭代器（istream_iterator），其可以用来读取输入流中的数据；
  • 将绑定到输出流对象的迭代器称为输出流迭代器（ostream_iterator），其用来将数据写入到输出流中。

接下来，就分别讲解这 2 个流迭代器的用法。

输入流迭代器（istream_iterator）

输入流迭代器用于直接从指定的输入流中读取元素，该类型迭代器本质上就是一个输入迭代器，这意味着假设 p 是一个输入流迭代器，则其只能进行 ++p、p++、*p 操作，同时输入迭代器之间也只能使用 == 和 != 运算符。

实际上，输入流迭代器的底层是通过重载 ++ 运算符实现的，该运算符内部会调用operator >>读取数据。也就是说，假设 iit 为输入流迭代器，则只需要执行 ++iit 或者 iit++，即可读取一个指定类型的元素。

值得一提的是，istream_iterator 定义在头文件，并位于 std 命名空间中，因此使用此迭代器之前，程序中应包含如下语句：

1
2
#include <iterator>
using namespace std;

第二行代码不是必需的，但如果不用，则程序中在创建该类型的迭代器时，必须手动注明 std 命名空间（强烈建议初学者使用）。

创建输入流迭代器的方式有 3 种，分别为：

1.
调用 istream_iterator 模板类的默认构造函数，可以创建出一个具有结束标志的输入流迭代器。要知道，当我们从输入流中不断提取数据时，总有将流中数据全部提取完的那一时刻，这一时刻就可以用此方式构建的输入流迭代器表示。

例如：

1
std::istream_iterator<double> eos;

由此，即创建了一个可读取 double 类型元素，并代表结束标志的输入流迭代器。

2.
除此之外，还可以创建一个可用来读取数据的输入流迭代器，比如：

1
std::istream_iterator<double> iit(std::cin);

这里创建了一个可从标准输入流 cin 读取数据的输入流迭代器。值得注意的一点是，通过此方式创建的输入流迭代器，其调用的构造函数中，会自行尝试去指定流中读取一个指定类型的元素。

  1. istream_iterator 模板类还支持用已创建好的 istream_iterator 迭代器为新建 istream_iterator 迭代器初始化，例如，在上面 iit 的基础上，再创建一个相同的 iit2 迭代器：```c
    std::istream_iterator iit2(iit1);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

    由此，就创建好了一个和 iit1 完全相同的输入流迭代器。

    ## 输出流迭代器（ostream_iterator）

    和输入流迭代器恰好相反，输出流迭代器用于将数据写到指定的输出流（如 cout）中。另外，该类型迭代器本质上属于输出迭代器，假设 p 为一个输出迭代器，则它能执行 `++p`、`p++`、`*p=t` 以及 `*p++=t` 等类似操作。

    其次，输出迭代器底层是通过重载赋值（=）运算符实现的，即借助该运算符，每个赋值给输出流迭代器的元素都会被写入到指定的输出流中。

    值得一提的是，实现 ostream_iterator 迭代器的模板类也定义在头文件，并位于 std 命名空间中，因此在使用此类型迭代器时，程序也应该包含以下 2 行代码：

    #include 

    using namespace std;

    ostream_iterator 模板类中也提供了 3 种创建 ostream_iterator 迭代器的方法。

    1. 
    通过调用该模板类的默认构造函数，可以创建了一个指定输出流的迭代器：
    ```c
    std::ostream_iterator<int> out_it(std::cout);

由此，我们就创建了一个可将 int 类型元素写入到输出流（屏幕）中的迭代器

2.
在第一种方式的基础上，还可以为写入的元素之间指定一个分隔符，例如：

1
std::ostream_iterator<int> out_it(std::cout，",");

和第一种写入方式不同之处在于，此方式在向输出流写入 int 类型元素的同时，还会附带写入一个逗号（,）。

3.
另外，在创建输出流迭代器时，可以用已有的同类型的迭代器，为其初始化。例如，利用上面已创建的 out_it，再创建一个完全相同的 out_it1：

1
std::ostream_iterator<int> out_it1(out_it);

流缓冲区迭代器（streambuf_iterator）

我们知道在 C++ STL 标准库中，流迭代器又细分为输入流迭代器和输出流迭代器，流缓冲区迭代器也是如此，其又被细分为输入流缓冲区迭代器和输出流缓冲区迭代器：

  • 输入流缓冲区迭代器（istreambuf_iterator）：从输入流缓冲区中读取字符元素；
  • 输出流缓冲区迭代器（ostreambuf_iterator）：将连续的字符元素写入到输出缓冲区中。

流缓冲区迭代器和流迭代器最大的区别在于，前者仅仅会将元素以字符的形式（包括 char、wchar_t、char16_t 及 char32_t 等）读或者写到流缓冲区中，由于不会涉及数据类型的转换，读写数据的速度比后者要快。

输入流缓冲区迭代器（istreambuf_iterator）

istreambuf_iterator 输入流缓冲区迭代器的功能是从指定的流缓冲区中读取字符元素。

值得一提的是，该类型迭代器本质是一个输入迭代器，即假设 p 是一个输入流迭代器，则其只能进行 ++p、p++、*p 操作，同时迭代器之间也只能使用 == 和 != 运算符。

另外，实现该类型迭代器的模板类也定义在<iterator>头文件，并位于 std 命名空间中。因此，在创建并使用该类型迭代器之前，程序中应包含如下代码：

1
2
#include <iterator>
using namespace std;

第二行代码不是必需的，但如果不用，则程序中在创建该类型的迭代器时，必须手动注明 std 命名空间（强烈建议初学者使用）。

创建输入流缓冲区迭代器的常用方式，有以下 2 种：

  1. 通过调用 istreambuf_iterator 模板类中的默认构造函数，可以创建一个表示结尾的输入流缓冲区迭代器。要知道，当我们从流缓冲区中不断读取数据时，总有读取完成的那一刻，这一刻就可以用此方式构建的流缓冲区迭代器表示。

举个例子：

1
std::istreambuf_iterator<char> end_in;

其中，<> 尖括号中用于指定从流缓冲区中读取的字符类型。

  1. 当然，我们还可以指定要读取的流缓冲区，比如：```c
    std::istreambuf_iterator in{ std::cin };
    1
    2
    3

    除此之外，还可以传入流缓冲区的地址，比如：```c
    std::istreambuf_iterator<char> in {std::cin.rdbuf()};

其中，rdbuf() 函数的功能是获取指定流缓冲区的地址。

无论是传入流缓冲区，还是传入其地址，它们最终构造的输入流缓冲区迭代器是一样的。

输出流缓冲区迭代器（ostreambuf_iterator）

和 istreambuf_iterator 输入流缓冲区迭代器恰恰相反，ostreambuf_iterator 输出流缓冲区迭代器用于将字符元素写入到指定的流缓冲区中。

实际上，该类型迭代器本质上是一个输出迭代器，这意味着假设 p 为一个输出迭代器，则它仅能执行 ++p、p++、*p=t 以及 *p++=t 操作。

另外，和 ostream_iterator 输出流迭代器一样，istreambuf_iterator 迭代器底层也是通过重载赋值（=）运算符实现的。换句话说，即通过赋值运算符，每个赋值给输出流缓冲区迭代器的字符元素，都会被写入到指定的流缓冲区中。

需要指出的是，istreambuf_iterator 类模板也定义在<iterator>头文件，并位于 std 命名空间中，因此使用该类型迭代器，程序中需要包含以下代码：

1
2
#include <iterator>
using namespace std;

在此基础上，创建输出流缓冲区迭代器的常用方式有以下 2 种：

1.
通过传递一个流缓冲区对象，即可创建一个输出流缓冲区迭代器，比如：

1
std::ostreambuf_iterator<char> out_it (std::cout);

同样，尖括号 <> 中用于指定要写入字符的类型，可以是 char、wchar_t、char16_t 以及 char32_t 等。

2.
还可以借助 rdbuf()，传递一个流缓冲区的地址，也可以成功创建输出流缓冲区迭代器：

1
std::ostreambuf_iterator<char> out_it (std::cout.rdbuf());

move_iterator移动迭代器

C++ 11 还为 STL 标准库增添了一种迭代器适配器，即本节要讲的 move_iterator 移动迭代器适配器。

move_iterator 迭代器适配器，又可简称为移动迭代器，其可以实现以移动而非复制的方式，将某个区域空间中的元素移动至另一个指定的空间。

实现移动迭代器的模板类定义在 <iterator> 头文件，并位于 std 命名空间中。因此，在使用该类型迭代器时，程序中应包含如下代码：

1
2
#include <iterator>
using namespace std;

第二行代码不是必需的，但如果不用，则程序中在创建该类型的迭代器时，必须手动注明 std 命名空间（强烈建议初学者使用）。

实现 move_iterator 移动迭代器的模板类定义如下：

1
2
template <class Iterator>
    class move_iterator;

可以看到，在使用此迭代器时，需要传入一个基础迭代器 Iterator。

注意，此基础迭代器的类型虽然没有明确要求，但该模板类中某些成员方法的底层实现，需要此基础迭代器为双向迭代器或者随机访问迭代器。也就是说，如果指定的 Iterator 类型仅仅是输入迭代器，则某些成员方法将无法使用。

move_iterator 模板类中，提供了 4 种创建 move_iterator 迭代器的方法。

1.
通过调用该模板类的默认构造函数，可以创建一个不指向任何对象的移动迭代器。比如：

1
2
3
4
//将 vector 容器的随机访问迭代器作为新建移动迭代器底层使用的基础迭代器
typedef std::vector<std::string>::iterator Iter;
//调用默认构造函数，创建移动迭代器
std::move_iterator<Iter>mIter;

如果程序中引入了 std 命名空间，则上面代码中所有的 std:: 都可以省略。

由此，我们就创建好了一个 mIter 移动迭代器，该迭代器底层使用的是 vector 容器的随机访问迭代器，但这里没有为此基础迭代器明确指向，所以 mIter 迭代器也不知向任何对象。

2.
当然，在创建 move_iterator 迭代器的同时，也可以为其初始化。比如：

1
2
3
4
5
6
//创建一个 vector 容器
std::vector<std::string> myvec{ "one","two","three" };
//将 vector 容器的随机访问迭代器作为新建移动迭代器底层使用的基础迭代器
typedef std::vector<std::string>::iterator Iter;
//创建并初始化移动迭代器
std::move_iterator<Iter>mIter(myvec.begin());

这里，我们创建了一个 mIter 移动迭代器，同时还为底层使用的随机访问迭代器做了初始化，即令其指向 myvec 容器的第一个元素。

3.
move_iterator 模板类还支持用已有的移动迭代器初始化新建的同类型迭代器，比如，在上面创建好 mIter 迭代器的基础上，还可以向如下这样为新建的移动迭代器初始化：

1
2
3
std::move_iterator<Iter>mIter2(mIter);
//还可以使用 = 运算符，它们是等价的
//std::move_iterator<Iter>mIter2 = mIter;

这样创建的 mIter2 迭代器和 mIter 迭代器完全一样。也就是说，mIter2 底层会复制 mIter 迭代器底层使用的基础迭代器。

4.
以上 3 种创建 move_iterator 迭代器的方式，其本质都是直接调用 move_iterator 模板类中的构造方法实现的。除此之外，C++ STL 标准库还提供了一个 make_move_iterator() 函数，通过调用此函数可以快速创建一个 move_iterator 迭代器。

C++ STL 标准库中，make_move_iterator() 是以函数模板的形式提供的，其语法格式如下：

1
2
template <class Iterator>
  move_iterator<Iterator> make_move_iterator (const Iterator& it);

其中，参数 it 为基础迭代器，用于初始化新建迭代器。同时，该函数会返回一个创建好的移动迭代器。

STL迭代器辅助函数

迭代器辅助函数 功能
advance(it, n) it 表示某个迭代器，n 为整数。该函数的功能是将 it 迭代器前进或后退 n 个位置。
distance(first, last) first 和 last 都是迭代器，该函数的功能是计算 first 和 last 之间的距离。
begin(cont) cont 表示某个容器，该函数可以返回一个指向 cont 容器中第一个元素的迭代器。
end(cont) cont 表示某个容器，该函数可以返回一个指向 cont 容器中最后一个元素之后位置的迭代器。
prev(it) it 为指定的迭代器，该函数默认可以返回一个指向上一个位置处的迭代器。注意，it 至少为双向迭代器。
next(it) it 为指定的迭代器，该函数默认可以返回一个指向下一个位置处的迭代器。注意，it 最少为前向迭代器。

advance()函数

advance() 函数用于将迭代器前进（或者后退）指定长度的距离，其语法格式如下：

1
2
template <class InputIterator, class Distance>
    void advance (InputIterator& it, Distance n);

其中 it 指的是目标迭代器，n 通常为一个整数。

需要注意的是，如果 it 为输入迭代器或者前向迭代器，则 n 必须为一个正数，即表示将 it 右移（前进） n 个位置；反之，如果 it 为双向迭代器或者随机访问迭代器，则 n 为正数时表示将 it 右移（前进） n 个位置，n 为负数时表示将 it 左移（后退） n 个位置。

另外，根据 it 类型是否为随机访问迭代器，advance() 函数底层采用了不同的实现机制：

  • 当 it 为随机访问迭代器时，由于该类型迭代器支持 p+n 或者 p-n（其中 p 就是一个随机访问迭代器）运算，advance() 函数底层采用的就是 it+n 操作实现的；
  • 当 it 为其他类型迭代器时，它们仅支持进行 ++ 或者 – 运算，这种情况下，advance() 函数底层是通过重复执行 n 个 ++ 或者 – 操作实现的。

值得一提的是，advance() 函数定义在<iterator>头文件，并位于 std 命名空间中。因此，程序在使用该函数之前，应包含如下 2 行代码：

1
2
#include <iterator>
using namespace std;

第二行代码不是必须的，但如果不引用，则后续在使用 advance() 函数时，需要额外标注 std 命名空间（强烈建议初学者使用）。

distance()函数

我们知道，作用于同一容器的 2 个同类型迭代器可以有效指定一个区间范围。在此基础上，如果想获取该指定范围内包含元素的个数，就可以借助本节要讲的 distance() 函数。

distance() 函数用于计算两个迭代器表示的范围内包含元素的个数，其语法格式如下：

1
2
template<class InputIterator>
  typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);

其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回[first, last)范围内包含的元素的个数。

注意，first 和 last 的迭代器类型，直接决定了 distance() 函数底层的实现机制：

  • 当 first 和 last 为随机访问迭代器时，distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数，其时间复杂度为O(1)常数阶；
  • 当 first 和 last 为非随机访问迭代器时，distance() 底层通过不断执行 ++first（或者 first++）直到 first==last，由此来获取 [first, last) 范围内包含元素的个数，其时间复杂度为O(n)线性阶。

另外，distance() 函数定义在头文件，并位于 std 命名空间中。因此在使用此函数前，程序中应包含如下代码：

1
2
#include <iterator>
using namespace std;

begin()和end()函数

无论是序列式容器还是关联式容器（包括哈希容器），不仅模板类内部提供有 begin() 和 end() 成员方法，C++ STL 标准库中还提供有同名且具有相同功能的 begin() 和 end() 函数。

首先需要说明的是，begin() 和 end() 是以函数模板的形式定义的，但它们的模板并没有位于某一个头文件中，而是很多头文件中都有它们的定义。

C++ STL 标准库中，包含 begin() 和 end() 函数模板的头文件包括：, , , , , , （正则表达式的头文件）, , , , 以及 。

不仅如此，begin() 和 end() 都位于 std 命名空间中。因此，在使用这 2 个函数之前，程序中应引入容纳它们函数模板的头文件以及 std 命名空间。

在实际的使用场景中，begin() 和 end() 函数往往会一起使用的。根据作用对象的不同，begin() 和 end() 函数可细分为以下 2 个功能。

begin()和end()参数为容器

当将某个具体容器（比如 cont）作为参数分别传给 begin() 和 end() 函数时，其中 begin() 底层会执行 cont.begin() 语句，而 end() 底层会执行 cont.end() 语句，它们最终会将得到的迭代器作为函数的返回值反馈回来。

当作用对象为容器时，end() 和 begin() 函数的语法格式是完全一样的，这里以 begin() 函数为例，有以下 2 种格式：

1
2
3
4
5
6
//① 非 const 修改的容器作为参数，begin() 函数返回的为非 const 类型的迭代器
template <class Container>
    auto begin (Container& cont)
//② 传入 const 修饰的容器，begin() 函数返回的为 const 类型的迭代器
template <class Container>
    auto begin (const Container& cont)

其中，cont 表示指定的容器；同时，函数会返回一个有特定指向的迭代器，且此迭代器的类型也取决于 cont 容器。

以上 2 种格式的区别仅在与传入的容器是否有 const 修饰，即如果有，则通过该函数获得的迭代器也有 const 修饰（不能用于修改容器中存储的数据）；反之就没有。

begin()和end()参数为数组

除了可以将指定容器作为参数传给 begin() 和 end() 之外，还可以指定数组作为参数传给它们。

将指定数组传给 begin() 函数，其会返回一个指向该数组首个元素的指针；将指定数组传给 end() 函数，其会返回一个指向数组中最后一个元素之后位置的指针。

同样，数组作为参数时，end() 函数的语法格式和 begin() 函数也完全一样，这里仅给出了 begin() 函数的语法格式：

1
2
template <class T, size_t N>
  T* begin (T(&arr)[N]);

其中 T 为数组中存储元素的类型，N 为数组的长度；(&arr)[N] 表示以引用的方式传递数组作为参数。

prev()和next()函数

若我们不想移动 it 迭代器本身，而仅仅是想在 it 迭代器的基础上，得到一个移动指定位置的新迭代器，显然 advance() 函数是不合适的，这时就可以使用 C++ STL 标准库提供的另外 2 个函数，即 prev() 和 next() 函数。

1.
prev 原意为“上一个”，但 prev() 的功能远比它的本意大得多，该函数可用来获取一个距离指定迭代器 n 个元素的迭代器。

prev() 函数的语法格式如下：

1
2
3
template <class BidirectionalIterator>
    BidirectionalIterator prev (BidirectionalIterator it, typename 
iterator_traits<BidirectionalIterator>::difference_type n = 1);

其中，it 为源迭代器，其类型只能为双向迭代器或者随机访问迭代器；n 为指定新迭代器距离 it 的距离，默认值为 1。该函数会返回一个距离 it 迭代器 n 个元素的新迭代器。

注意，当 n 为正数时，其返回的迭代器将位于 it 左侧；反之，当 n 为负数时，其返回的迭代器位于 it 右侧。

注意，prev() 函数自身不会检验新迭代器的指向是否合理，需要我们自己来保证其合理性。

2.
和 prev 相反，next 原意为“下一个”，但其功能和 prev() 函数类似，即用来获取一个距离指定迭代器 n 个元素的迭代器。

next() 函数的语法格式如下：

1
2
3
template <class ForwardIterator>
    ForwardIterator next (ForwardIterator it, typename 
iterator_traits<ForwardIterator>::difference_type n = 1);

其中 it 为源迭代器，其类似可以为前向迭代器、双向迭代器以及随机访问迭代器；n 为指定新迭代器距离 it 的距离，默认值为 1。该函数会返回一个距离 it 迭代器 n 个元素的新迭代器。

需要注意的是，当 it 为前向迭代器时，n 只能为正数，该函数最终得到的新迭代器位于 it 右侧；当 it 为双向迭代器或者随机访问迭代器时，若 n 为正数，则得到的新迭代器位于 it 右侧，反之位于 it 左侧。

注意，和 prev() 函数一样，next() 函数自身也不会检查新迭代器指向的有效性，需要我们自己来保证。