迭代器 (iterator) 是 C++ 程序中常用的一种设计模式，它最重要的作用是为访问容器提供了统一的接口。
C++ STL 有许多容器，例如 vector、list、deque、map、unordered_map 。 而我们常常对不同的容器有相同的操作，比如在容器中查找一个元素、找出满足条件的所有元素并返回。为了不必为每个容器写一个操作函数，我们希望容器提供一个访问元素的统一接口，从而复用操作函数。 这个接口就是迭代器。
在本文中，我们将从最简单的迭代器入手，了解 C++ 中迭代器的种类，并写出符合 C++ STL 风格的迭代器。
最简单的迭代器
C++ 的迭代器与 Python 的迭代器不同，它并不提出一套新的接口，而是尽可能模仿指针的行为。而一个指针最基本的功能是访问它指向的元素。仅支持这一个功能还不够，为了能够 迭代，还需要至少支持指针的自增操作 ++i。
我们可以为一个整数数组写一个最简单的迭代器，它仅提供访问数组元素和自增的功能：
class ArrayIterator {
public:
// 从一个数组创建一个迭代器，并且让迭代器指向 pos 指定的位置
ArrayIterator(int* array, int pos): array_(array), pos_(pos) {}
// 访问当前数组元素
int& operator*() const {
return array_[pos_];
}
// 移动到下一个数组元素
ArrayIterator& operator++() {
pos_++;
return *this;
}
private:
int* array_;
int pos_;
};
下面，我们可以用这个迭代器来访问数组元素，就像使用指针一样，但功能比指针局限得多：
void access_array() {
int array[] = { 1, 2, 3, 4 };
ArrayIterator it(array, 0);
printf("array[0] = %d\n", *it); // 访问第0元素
++it; // 指向下一个元素
printf("array[1] = %d\n", *it); // 访问第1元素
}
从这个例子我们可以看出，迭代器在接口上尽可能模拟指针的行为。这正是 C++ 迭代器的主要设计思路。
迭代器的种类
指针非常灵活，不但可以指向某个内存位置，还可以加上一个偏移量来访问内存的其他位置。而不是所有的容器都支持这些操作，比如随机访问任意位置对于指针都是 O(1) 时间复杂度，而对于链表，则是 O(n) 时间复杂度。因此，让链表的迭代器支持加偏移量的操作就不合理，因为对于 i + n 这个运算，人们会默认它的复杂度为常数。
将所有功能一一去除，一个迭代器需要至少支持两个功能才有用：
访问当前元素 *i前缀自增操作 ++i （前缀自增和后缀自增是两个操作符）
我们根据迭代器能够提供的额外功能，将其分成五类：
1. 输入迭代器 (input iterator)
输入迭代器用于从一个对象中不断读出元素。
除了迭代器基本操作，还需要支持：
比较两个迭代器是否指向相同元素 i == j 和 i != j访问元素的成员 i->m后缀自增操作 i++
输入迭代器不需要保证自增操作之后，之前的迭代器依然有意义。典型的例子是用于读取流文件的迭代器：每次自增之后，都无法回复到原来的位置。也包括随机数生成器的迭代器：每次自增之后，随机数生成器的状态都发生了变化。
2. 输出迭代器 (output iterator)
输出迭代器用于向一个对象不断添加元素。
除了迭代器基本操作，还需要支持：
修改元素 *i = v后缀自增操作 i++
输出迭代器也不保证自增之后，之前的迭代器有意义，并且它还不保证修改元素之后访问元素有意义。典型的例子是用于写入流文件的迭代器和向容器中插入元素的 插入迭代器 (insert iterator)。
3. 前向迭代器 (forward iterator)
前向迭代器用于访问一个容器中的元素。
因此，它必须提供输入迭代器的所有操作，如果它用于访问一个非 const 容器，还需要支持输出迭代器的所有操作。
在此基础上，它需要保证自增之后，其他的迭代器仍然有意义（比输入迭代器要求更高）。它也需要保证可以不受限制地修改和访问当前元素（比输出迭代器要求更高）。
典型的例子包括各种容器的迭代器，比如 vector、list、map 的迭代器。
4. 双向迭代器 （bidirectional iterator）
双向迭代器首先是一个前向迭代器，除此之外，它还需要支持自减操作 --i 和 i-- 。
一个线性存储元素的容器应该提供双向迭代器，例如 vector 和 list。
5. 随机访问迭代器 (random access iterator)
随机访问迭代器是所有迭代器种类中最强大的，它除了需要支持前向迭代器的所有操作，还支持加上任意偏移量并得到新的迭代器，即 i + n，其中 n 可以是正数也可以是负数，分别表示向前或向后随机访问。
它需要支持的完整操作包括：
加上或减去一个偏移量 i + n 和 i - n自加或自减一个偏移量 i += n 和 i -= n计算两个迭代器的距离 i - j使用下标形式的加上一个偏移量 i[n]，其效果等价于 *(i + n)比较两个迭代器的先后顺序 a < b a <= b a > b a >= b
我们可以发现，随机访问迭代器在功能上已经等价于指针。
一般来说，只有 vector 这类线性且连续存储元素的容器才会提供随机访问迭代器。
如何写出通用的操作函数
迭代器的用途是让程序员写出通用的操作函数。比如，不管是什么容器，我们通常都有将它的所有元素拷贝到另一容器的需求。在有迭代器之前，我们需要为每种容器都写一个循环，而有了迭代器，我们可以写出一个通用的拷贝函数。
为此，我们首先需要使用函数模版，因为迭代器的类型是未知的。我们需要两个输入迭代器，分别表示拷贝的起点和终点，以及一个输出迭代器。因此，我们的拷贝函数接受三个参数，其中前两个参数的类型是相同的。
template
// requires InputIterator
OutputIt copy(InputIt first, InputIt last, OutputIt d_first) {
while (first != last) {
*d_first++ = *first++;
}
return d_first;
}
如果将 InputIt 和 OutputIt 替换成指针，函数仍然可以编译，这说明我们的实现是正确的。
我们在 template 和函数名之间插入了一行注释，用于说明 InputIt 和 OutputIt 应该满足什么条件，即 InputIt 必须是输入迭代器，OutputIt 必须是输出迭代器。虽然目前该代码被注释掉，没有实际用途，但是 C++20 可能会支持 concepts，去掉注释之后，这行声明就是使用 concepts 约束模版类型的语法。使用 requires 表达式后，C++ 编译器会在模版实例化时帮助我们检查 InputIt 和 OutputIt 的具体类型是否满足这两类迭代器的条件。
C++ 已经为我们实现了一组通用的操作函数，定义在头文件
计数：count count_if检查条件：all_of any_of none_of遍历：for_each for_each_n查找：find find_if find_if_not拷贝：copy copy_if copy_n填充同一元素：fill fill_n元素变换（map 操作）：transform
头文件
作者：番茄吐司君 链接：https://www.jianshu.com/p/40e40aef2305 来源：简书 简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。