在现代C ++中编写自定义迭代器

迭代器是指向容器内元素的对象。像指针一样，迭代器可用于访问其指向的元素，并可在容器的内容中移动。 C ++标准库中的每个容器都提供了自己的迭代器以及一些检索它的方法。使用迭代器非常简单：从容器中获取实例，将其移动到需要的地方，然后获取指向的元素。

具体而言，迭代器是一个简单的类，提供了许多运算符：增量++，解引用*和其他一些使其与指针和可以对其执行的算术运算非常相似的运算符。实际上，迭代器是指针的泛化，在编写迭代器本身时通常将其用作基础。

迭代器是标准库容器的构建块之一，但是当您要提供对您自己编写的自定义容器的元素进行迭代的功能时，它们也很有用：这是我在本文中要研究的内容。向容器中添加迭代器将使其与基于范围的for循环和C ++算法库兼容：基于迭代器的一组用于搜索，排序，计数和操作容器的函数。

在深入研究之前，让我们定义一个愚蠢的自定义容器，我们希望通过迭代器来为其增添趣味：

Integers类是原始整数数组的包装：我们希望能够通过迭代器访问该私有数组的元素，以及对其进行循环或将其传递给任何标准库算法。让我们从做出一些设计决策开始。

第一步是选择我们要实现的迭代器的类型。现代C ++定义了六种类型：

只能向前扫描一次容器，不能更改其指向的值（只读）；

只能向前扫描一次容器，不能读取它指向的值（只写）；

可以多次向前扫描容器，可以读写指向的值；

与上一个相同，但也可以不顺序访问容器（即通过跳转）;

与上一个相同，除了逻辑上相邻的元素在内存中也物理上相邻。

这六个类别是分层的：双向迭代器也是前向迭代器，随机访问迭代器既是双向迭代又是前向迭代器，依此类推。通常，所有迭代器都是输入迭代器（1），这使它们成为只读，也称为常量迭代器。同时支持读取和写入操作的迭代器也是输出迭代器（2），称为可变迭代器。

输入和输出迭代器通常用于低级组件，例如输入和输出流（所谓的单遍算法），因此具有局限性。我们想对自定义容器做更多的事情，因此我们将跳过这两个并直接跳转到可变的Forward Iterator。

首先要做的是为迭代器分配一些属性。在C ++ 17之前，这是通过使用标签分发机制对其进行标记来完成的，而C ++ 20使用的是概念：在本文中，我将遵循传统方法。

iterator_category —我们在上面看到的六个迭代器类别之一。完整列表在这里。我们需要std :: forward_iterator_tag标记；

different_type —一个有符号整数类型，可用于标识迭代器步骤之间的距离。我们的迭代器基本上是指针的包装器，并利用指针算术，因此默认的std :: ptrdiff_t是一个不错的选择。

#include＆lt; iterator＆gt; //对于std :: forward_iterator_tag＃include＆lt; cstddef＆gt; //对于std :: ptrdiff_tstruct迭代器{使用iterator_category = std :: forward_iterator_tag;使用difference_type = std :: ptrdiff_t;使用value_type = int;使用指针= int *; //或使用reference = int＆amp ;;的value_type *； //或value_type＆amp;};

上面的某些标签一开始似乎没有用。实际上，您会注意到在定义迭代器的过程中永远不会提及它们。如果您的容器从＆lt; algorithm＆gt;传递给标准库函数之一，则使用标记来选择最有效的算法。图书馆。错误的标签表示性能欠佳！迭代器类别还用于设置算法要求，例如：std :: fill需要一个正向迭代器，而std :: reverse需要一个双向迭代器。传递错误的迭代器将导致编译错误。

所有迭代器必须是可构造的，可复制构造的，可分配复制的，可破坏的和可交换的。让我们将这些要求转换为迭代器的代码：

简单！我们只需要一个自定义构造函数即可初始化私有成员变量m_ptr，该变量指向Integers容器的元素。定制构造函数满足可构造要求，而其他所有构造函数均由编译器提供的隐式声明的构造函数和运算符覆盖。

我们正在构建一个可变的正向迭代器，该继承器从输入和输出迭代器继承属性。生成的迭代器必须支持以下操作：

++ iterator和iterator ++-可递增，将其向前移动一步，包括前缀和后缀版本。后者必须返回可取消引用的东西；

struct Iterator {//这里的Iterator标签... //这里的Iterator构造函数... reference operator *（）const {return * m_ptr; }指针操作符-＆gt;（）{return m_ptr; } //前缀增量Iterator＆amp; operator ++（）{m_ptr ++;返回* this; } //后缀增量Iterator operator ++（int）{Iterator tmp = * this; ++（*此）;返回tmp; }朋友bool运算符==（const Iterator＆amp; a，const Iterator＆amp; b）{return a.m_ptr == b.m_ptr; }; =（const Iterator＆amp; a，const Iterator＆amp; b）{return a.m_ptr！= b.m_ptr; };私人：指针m_ptr;};

如您所见，每个运算符都涉及私有指针m_ptr的使用。另外，请注意两个比较运算符的好友声明：这是将运算符定义为非成员函数的便捷方法，但仍能够访问Iterator类的私有部分（此处为合理值）。

我们的迭代器很好。最后一步是使我们的自定义容器能够创建Iterator对象。这可以通过添加两个公共方法begin（）和end（）来完成，这些方法返回Iterator类的实例，分别代表第一个元素和最后一个元素：

class Integers {public：//此处的迭代器定义...迭代器begin（）{return Iterator（＆amp; m_data [0]）; }迭代器end（）{return迭代器（＆amp; m_data [200]）; } // 200超出范围};

end（）方法返回一个迭代器，该迭代器在原始数组的末尾指向无效的内存地址。这样的迭代器只是一个占位符，用于确定何时到达边界：永远不要直接访问它。

现在，定制容器及其迭代器都已准备就绪。让我们使用基于范围的for循环对其进行测试：

此代码将神奇地打印容器中每个整数的值。之所以起作用，是因为基于范围的for循环只是编译器为以下目的创建的语法糖：

对于（auto it = integers.begin（），end = integers.end（）; it！= end; ++ it）{const auto i = * it; std :: cout＆lt;＆lt;我＆lt;＆lt; ＆＃34; \ n＆＃34 ;;}

换句话说：创建了两个迭代器it和end。第一个指向容器的开头，另一个指向结尾。然后，在每个循环上，迭代器都会递增，直到等于结束，即直到达到容器的末尾为止。实际值是通过在打印之前在局部变量中取消引用来获得的。

请注意，编译器如何利用我们之前实现的所有运算符和函数：自定义容器中的begin（）和end（）方法，可以将两个迭代器与！=运算符进行比较，并可以使用前缀语法，最后可以取消引用以获取其指向的实际值。

该函数为容器中的所有元素分配值3。之所以起作用，是因为std :: fill通常是这样实现的：

模板＆lt; typename ForwardIterator，类型名T＆gt;无效填充（ForwardIterator首先，ForwardIterator最后，const T＆amp; value）{for（; first！= last; ++ first）* first = value;}

请注意，我们的迭代器不适用于算法库中的所有函数。例如，我们不能将其传递给std :: reverse，因为它需要双向迭代器。到目前为止，最困难的部分已经完成，因此，扩展迭代器只是在类中添加更多运算符并选择最佳标签来描述它的问题。

我们的自定义容器是一个老式数组的包装，可以使用指针算法进行导航。实际上，我们可以摆脱整个Iterator类，而只需分别从Integers :: begin（）和Integers :: end（）方法返回指向第一个和最后一个数组元素的指针。算法库中基于范围的循环和函数仍然可以正常工作。但是，现实世界中的容器通常基于比普通数组更复杂的数据结构-考虑一下链表或映射，其中的指针及其操作还不够。迭代器将所有复杂性抽象到了像指针一样方便的对象后面，并使您可以通过熟悉的操作访问复杂的数据结构。

在我们的示例中，Integers类可能是std :: array的包装器。在这种情况下，您根本不需要实现任何自定义迭代器，只需返回属于使用中的标准库容器的迭代器即可。例如：

类Integers {使用IntegersType = std :: array＆lt; int，32＆; // ... IntegersType :: iterator begin（）{return m_data.begin（）; } IntegersType :: iterator end（）{return m_data.end（）}私有：IntegersType m_data;};

上面的代码之所以有效，是因为C ++标准库中的所有容器都完成了我们对Integer容器所做的工作：它们都将其迭代器实现为类成员。 IntegersType别名用于简化类型名称，不是必需的。另外，在C ++ 17中，将auto作为迭代器类型返回似乎还不错。

默认情况下，Iterator可以更改其指向的元素。如果要使其不可变，通常的技巧是在自定义容器类中添加另一种迭代器类型-我们将其称为ConstantIterator。这种新的迭代器类型几乎与原始迭代器类型相同，除了它的取消引用运算符现在可以返回常量引用之外：

同样的情况适用于-＆gt;操作员。最后，自定义容器必须能够返回这种新的迭代器类型。这可以通过添加两个其他的公共方法cbegin（）和cend（）（其中前导c代表常量）来完成，这些方法返回ConstantIterator类的实例：

许多标准库容器都提供begin（）/ end（）和cbegin（）/ cend（）对。每种迭代器类型都应用相同的模式。例如，std :: array也具有rbegin（）/ rend（），其中r代表反向迭代器（是的，您也可以反向循环标准库数组）。

C ++ 20引入了一些概念，这是一种对模板函数或类可以接受的类型施加约束的明智方法。虽然迭代器的类别和属性保持不变，但执行方式的变化是：使用标记，直到C ++ 17，自C ++ 20以来的概念。例如，您可以使用std :: forward_iterator概念标记迭代器，而不是std :: forward_iterator_tag标记。同样的情况适用于所有迭代器属性。例如，正向迭代器必须是std :: incrementable。这种新机制有助于获得更好的迭代器定义，并使来自编译器的错误更易读。一旦概念实现变得更加广泛，我将对本文进行升级。

#include＆lt; iterator＆gt; #include＆lt; cstddef＆gt; class Integers {public：struct Iterator {using iterator_category = std :: forward_iterator_tag;使用difference_type = std :: ptrdiff_t;使用value_type = int;使用指针= int *;使用reference = int＆amp ;;迭代器（指针ptr）：m_ptr（ptr）{}参考运算符*（）const {返回* m_ptr; }指针操作符-＆gt;（）{return m_ptr; }迭代器和放大器; operator ++（）{m_ptr ++;返回* this; }迭代器操作符++（int）{迭代器tmp = * this; ++（*此）;返回tmp; }朋友bool运算符==（const Iterator＆amp; a，const Iterator＆amp; b）{return a.m_ptr == b.m_ptr; }; =（const Iterator＆amp; a，const Iterator＆amp; b）{return a.m_ptr！= b.m_ptr; };专用：指针m_ptr; };迭代器begin（）{return Iterator（＆amp; m_data [0]）; }迭代器end（）{return迭代器（＆amp; m_data [200]）; }专用：int m_data [200];};