剑指信奥 ｜ C++ 之 STL - 迭代器（上）

各个容器统一的访问接口

什么是迭代器

还记得我们在介绍 C++ STL 的概念时，提到了 STL 包含四个组件吗？

它们分别是 容器、迭代器、算法、函数，到目前为止，我们关于容器部分的内容已经基本结束了，它们分别是：

• string
• vector
• stack
• queue
• list
• set
• map

这些容器的主要作用就是用来存储数据，依据它们底层不同的数据结构，存储的方式也各不相同，因此带来增查改删各种操作时间和空间上的差异，人们在使用时就可以根据具体的需求做出最佳的选择。

虽然都是不同的容器，但从这几次课的学习，我们不难发现，我们对容器的很多操作都是类似的，比如在容器中查找一个特定的元素，查找满足需求的一部分元素，修改元素等等。

如果为每一种容器都重新定义一套函数，实在是麻烦而且没有必要，如果能有一个统一的方式能对所有的容器提供访问功能就好了，而这，就是我们今天要学习的内容 — 迭代器 iterator

迭代器（iterator）有时又称游标（cursor）是程序设计的软件设计模式。 

迭代器是可在容器（container，例如链表或阵列）上遍历的接口，设计人员无需关心容器内存分配的实现细节。

Wikipedia

所以，迭代器就是访问容器的统一接口。

一个迭代器的示例

在开始介绍迭代器的具体内容之前，我们先来看一个迭代器使用的实例：

#include <iostream>
#include <vector>

using namespace std;

int main() {

    // 容器的初始化
    vector<int> container{1, 2, 3};

    // 迭代器的定义
    vector<int>::const_iterator i;

    // for 循环 1
    cout << "--- for 1 ---" << endl;
    for (i = container.begin(); i != container.end(); i++) {
        cout << *i << "\t";
    }

    // for 循环 2
    cout << endl << "--- for 2 ---" << endl;
    for (i = container.begin(); i < container.end(); i++) {
        cout << *i << "\t";
    }

    // while 循环
    cout << endl << "--- while ---" << endl;
    i = container.begin();
    while (i != container.end()) {
        cout << *i << "\t";
        i++;
    }

    return 0;
}

/*
 output:
    --- for 1 ---
    1	2	3
    --- for 2 ---
    1	2	3
    --- while ---
    1	2	3
 */

在这段代码中，我们先是初始化了一个具有 3 个元素的向量，然后使用 vector<int>::iterator = i; 的方式声明了一个关于这个容器的迭代器 i。

之后，以两种 for 循环和一个 while 循环的方式输出了这个容器的所有元素，三次遍历的输出结果都是一样的。

现在，我们改动上述代码中的 3 行，仔细观察一下是在哪里：

#include <iostream>
#include <deque>

using namespace std;

int main() {

    // 容器的初始化
    deque<int> container{1, 2, 3};

    // 迭代器的定义
    deque<int>::const_iterator i;

    // for 循环 1
    cout << "--- for 1 ---" << endl;
    for (i = container.begin(); i != container.end(); i++) {
        cout << *i << "\t";
    }

    // for 循环 2
    cout << endl << "--- for 2 ---" << endl;
    for (i = container.begin(); i < container.end(); i++) {
        cout << *i << "\t";
    }

    // while 循环
    cout << endl << "--- while ---" << endl;
    i = container.begin();
    while (i != container.end()) {
        cout << *i << "\t";
        i++;
    }

    return 0;
}

/*
 output:
    --- for 1 ---
    1	2	3	
    --- for 2 ---
    1	2	3	
    --- while ---
    1	2	3	
 */

找到了吗？是这样的 3 行：

1. #include <vector> 改为 #include <deque>
2. vector<int> container{(1, 2, 3}; 改为 deque<int> container{1, 2, 3};
3. vector<int>::const_iterator i; 改为 deque<int>::const_iterator i;

简单一点说，我们是把容器由向量 vector 改为了双端队列 deque，三处循环代码没有任何改变，同样实现了容器的遍历。

这就体现了迭代器的作用：为容器提供统一的访问接口。

迭代器的定义分类

迭代器是有分类的，我们先看一段代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {

    // 容器的初始化
    vector<int> container{1, 2, 3};

    // 迭代器的定义
    vector<int>::iterator i; // 正向迭代器

    // for 循环 1
    cout << "--- for 1 ---" << endl;
    for (i = container.begin(); i != container.end(); i++) {
        *i += 1; // 修改元素的值
    }

    // for 循环 2
    cout << endl << "--- for 2 ---" << endl;
    for (i = container.begin(); i < container.end(); i++) {
        cout << *i << "\t";
    }

    return 0;
}

/*
 output:
    --- for 1 ---
    
    --- for 2 ---
    2	3	4	
 */

这段代码和之前第一个代码片段很像，不同在以下两行：

1. vector<int>::const_iterator i; 改为 vector<int>::iterator i;
2. cout << *i << "\t"; 改为 *i += 1;

首先，我们修改了迭代器的类型。

我们把 const_iterator 改为 iterator。

其次，在第一个 for 循环中，把输出语句改为了赋值语句。

这里 const_iterator 是 常量正向迭代器 的含义，它只能实现元素的访问，不能修改元素，而 iterator 是 正向迭代器 的含义，它不仅能实现元素的访问，还可以修改元素的值。

所以，迭代器按照定义方式分为以下四类：

1. 正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

2. 常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

3. 反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

我们知道了，各种迭代器都可以访问元素，而非常量迭代器还可以修改元素，那么正向迭代器和反向迭代器有什么区别呢？

今天课程的最后，我们看一个反向迭代器的示例：

#include <iostream>
#include <vector>

using namespace std;

int main() {

    vector<int> container{1, 2, 3};

    // 迭代器的定义
    vector<int>::reverse_iterator i; // 反向迭代器

    // for 循环 1
    cout << "--- for 1 ---" << endl;
    for (i = container.rbegin(); i != container.rend(); i++) {
        cout << *i << "\t";
        *i *= 2; // 修改元素的值
    }

    // for 循环 2
    cout << endl << "--- for 2 ---" << endl;
    for (i = container.rbegin(); i < container.rend(); i++) {
        cout << *i << "\t";
    }

    return 0;
}

/*
 output:
    --- for 1 ---
    3	2	1	
    --- for 2 ---
    6	4	2	
 */

我们这次定义了一个非常量反向迭代器，在 for 循环 1 中，首先输出元素，紧接着修改了每个元素值为原来的 2 倍，再次使用 for 循环 2 输出修改后的值。

输出结果表明，元素是逆序输出的，体现了反向的含义，需要注意的是，反向迭代器的两端使用的是 rbegin() 和 rend() 函数，而循环里的 ++ 将指向容器里的前一个元素。

关于迭代器第一部分的内容，我们就说到这，下次课我们继续聊聊迭代器后续的内容。