关于Iterators

[nine-point-eight-p]

Something about iterators

第五次作业D题要求实现一个[range-based for](Range-based for loop (since C++11) - cppreference.com)。以前的同学也讨论过range-based for，参见[关于数组退化及基于范围的for循环 · Issue #11 · thu-coai/THUOOP · GitHub (github.com)](https://github.com/thu-coai/THUOOP/issues/11)。range-based for一般需要：

• 容器拥有begin和end函数，返回值是一个可以自己定义的迭代器，分别指向第一个元素和最后一个元素。既可以是成员函数，也可以是非成员函数。
• 容器的迭代器重载了*、++、!=运算符，既可以是成员函数，也可以是非成员函数。

题目也给出了提示，要求我们的容器提供begin和end函数，同时自己写一个迭代器。如下：

struct Iterator
{
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    // Add more using statement here
    // hint: using value_type = ?
    //       using reference = ?

    //Define your constructor and functions that are needed for a Iterator.


    private:
    // Add what where variable you want here to make the Iterator functional.

}; 

为什么有一些奇怪的using？怎么样才能写一个功能正常的迭代器？我们来粗略地梳理一下迭代器的相关设计（但是作业还是得你自己写~）。让我们从STL的迭代器说起。

STL中的迭代器

迭代器（Iterator）用于访问一个容器的内部元素。某种意义上，这也可以说是指针的一种封装。STL的每个容器都提供了自己的迭代器。

迭代器的分类

首先，所有的迭代器都支持拷贝构造、拷贝赋值，同时可以自增（前缀或后缀）。根据具体的功能不同，STL划分了迭代器的种类。功能较强的迭代器包括了功能较弱的迭代器的功能。从实现的角度来说，它们的区别在于支持的语法不同，详见cppreference（本文参考资料中）。

• Input/Output iterator（输入/输出迭代器）：可以执行单次的单向遍历，只能进行输入/输出操作。
• Forward iterator（前向迭代器）：具有输入迭代器的所有功能；如果不是常量迭代器（constant iterator，不能改变所指向的数据的值），则也具有输出迭代器的功能。只能进行单向遍历。所有标准容器都至少支持前向迭代器类型。
• Bidirectional iterator（双向迭代器）：具有前向迭代器的所有功能，但也可以向后迭代，即可以进行双向的遍历。
• Random-access iterator（随机访问迭代器）：具有双向迭代器的所有功能，但还可以“非顺序“地访问容器的元素，即迭代器可以通过一个偏移量直接访问距离较远的元素（直观来说就是类似于指针和整数之间的加减）。“随机”这个说法或许不太恰当，容易误解，它其实只是强调非顺序地进行访问。

迭代器的实现与属性

从头文件<iterator>一路可以追踪到<bits/stl_iterator_base_types.h>。在这里我们可以看到抽象的迭代器的样貌。首先是以上各类迭代器的tag：

// stl_iterator_base_types.h
/**
  *  @defgroup iterator_tags Iterator Tags
  *  These are empty types, used to distinguish different iterators.  The
  *  distinction is not made by what they contain, but simply by what they
  *  are.  Different underlying algorithms can then be used based on the
  *  different operations supported by different iterator types.
  */
//@{ 
///  Marking input iterators.
struct input_iterator_tag { };

///  Marking output iterators.
struct output_iterator_tag { };

/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { };

/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { };

/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };

无论是注释还是继承关系，都再次反映了它们之间的关系。紧接着就是一个泛化的迭代器类，涉及了迭代器很重要的五种属性，也包括上面的tag：

/**
*  @brief  Common %iterator class.
*
*  This class does nothing but define nested typedefs.  %Iterator classes
*  can inherit from this class to save some work.  The typedefs are then
*  used in specializations and overloading.
*
*  In particular, there are no default implementations of requirements
*  such as @c operator++ and the like.  (How could there be?)
*/
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
       typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
  /// One of the @link iterator_tags tag types@endlink.
  typedef _Category  iterator_category;
  /// The type "pointed to" by the iterator.
  typedef _Tp        value_type;
  /// Distance between iterators is represented as this type.
  typedef _Distance  difference_type;
  /// This type represents a pointer-to-value_type.
  typedef _Pointer   pointer;
  /// This type represents a reference-to-value_type.
  typedef _Reference reference;
};

这些代码里的注释其实已经十分清晰地介绍了相应的属性。小结一下：

• category：迭代器的类型，即上文中的迭代器tag。
• value_type：迭代器所指向的数据类型。
• difference_type：迭代器之间的“距离”的类型。相应的模板默认参数为std::ptrdiff_t，一般为long long int。
• pointer：迭代器所指向的数据类型的指针类型，即value_type*。
• reference：迭代器所指向的数据类型的引用类型，即value_type&。

这也就是作业题目里那些using的来源。有没有觉得using/typedef和变量定义有相似之处？只不过这里的“变量”是类型名。我们可以说，这里using/typedef实际上就是在定义迭代器的相关属性，这些属性是一些类型。

属性的价值（有点复杂但是有用？的部分）

当然，定义迭代器的属性不会由编译器做强制要求，也就是说不写未必不能跑，写错了也没人管（e.g. category标称是bidirectional，却只实现了forward的功能）。然而，正确书写的属性将有助于使用迭代器的算法了解该迭代器的相关信息。具体来说，只要一个迭代器“定义”（using/typedef）了这几种属性，便可以用iterator_traits获取它的这些属性。

那为什么算法要了解这些属性呢？是为了保障功能。举例来说，category看起来似乎没什么用，但它标志了迭代器的类型，也就是它读写/移动的模式，这对于算法来说很有意义。举一些具体的例子，例如：

• <algorithm>中定义了std::find，功能是查找某一区间内第一个出现的特定元素。因为只需要读取，它只要求使用input iterator。当然我们传入功能更强、更高级的迭代器也没有问题。
• <algorithm>中还定义了std::reverse，功能是反转某一区间的元素，它需要一个bidirectional iterator才能工作。
• std::advance是<iterator>中定义的关于迭代器基本操作的函数之一，功能是使迭代器前进（或者后退）指定长度的距离。它可以操作最基本的input iterator，也可以操作更高级的迭代器。然而，根据迭代器的种类不同，函数将选择不同的实现：简单的input iterator只能通过++来移动，需要O(n)时间；而强大如random-access iterator，理应直接用+或-移动到目的地，只需要O(1)时间。

不同的函数/算法对迭代器有不同的需求，怎样实现？我们就用上了迭代器准备好的那些属性。借助iterator_traits，我们可以获取想要的信息并予以应对。以上面提到的这些为例，我们粗略地看看代码。

• std::advance（这个例子较简单，没有深究concept如何运用iterator_traits，想看更深入的原理请参见下一个例子）：

  // stl_iterator_base_funcs.h
  template<typename _InputIterator, typename _Distance>
  inline _GLIBCXX14_CONSTEXPR void
  __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    __glibcxx_assert(__n >= 0);
    while (__n--)
  ++__i;
  }
  
  template<typename _BidirectionalIterator, typename _Distance>
  inline _GLIBCXX14_CONSTEXPR void
  __advance(_BidirectionalIterator& __i, _Distance __n,
        bidirectional_iterator_tag)
  {
    // concept requirements
    __glibcxx_function_requires(_BidirectionalIteratorConcept<
                _BidirectionalIterator>)
    if (__n > 0)
      while (__n--)
    ++__i;
    else
      while (__n++)
    --__i;
  }
  
  template<typename _RandomAccessIterator, typename _Distance>
  inline _GLIBCXX14_CONSTEXPR void
  __advance(_RandomAccessIterator& __i, _Distance __n,
            random_access_iterator_tag)
  {
    // concept requirements
    __glibcxx_function_requires(_RandomAccessIteratorConcept<
                _RandomAccessIterator>)
    if (__builtin_constant_p(__n) && __n == 1)
  ++__i;
    else if (__builtin_constant_p(__n) && __n == -1)
  --__i;
    else
  __i += __n;
  }

  我们可以非常清晰地看到，根据迭代器种类不同，函数有三种不同的实现。每种实现中都会用__glibcxx_function_requires对迭代器的种类做一个校验，如果符合就会采用这种实现，否则就尝试更低级的实现（笔者认为这可能利用了SFINAE，但是不确定）。

  • 第一种实现：基础的input iterator。通过assert要求偏移量必须是非负数，因为input iterator只能正向移动。若满足要求，采用循环++移动至目的地。
  • 第二种实现：进阶的bidirectional iterator。偏移量不再限制，因为可以双向移动。若偏移量为正，采用循环++移至目的地；若为负，则用循环--。
  • 第三种实现：高级的random-access iterator。__builtin_constant指的是编译期常量。当偏移量是编译期常量且为正负1时，直接返回++或--后的结果；否则直接+=偏移量，一步到位，肯定比之前的都快。

  显然，写好迭代器的tag才能真正发挥出这个函数的功能。

• std::find（这个例子略复杂，步入concept内部的iterator_traits，不想看的同学可跳过）：

  // stl_algo.h
  /**
   *  @brief Find the first occurrence of a value in a sequence.
   *  @ingroup non_mutating_algorithms
   *  @param  __first  An input iterator.
   *  @param  __last   An input iterator.
   *  @param  __val    The value to find.
   *  @return   The first iterator @c i in the range @p [__first,__last)
   *  such that @c *i == @p __val, or @p __last if no such iterator exists.
   */
  template<typename _InputIterator, typename _Tp>
    inline _InputIterator
    find(_InputIterator __first, _InputIterator __last,
   const _Tp& __val)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) // HERE
      __glibcxx_function_requires(_EqualOpConcept<
  	typename iterator_traits<_InputIterator>::value_type, _Tp>) 
      __glibcxx_requires_valid_range(__first, __last);
      return std::__find_if(__first, __last,
  	    __gnu_cxx::__ops::__iter_equals_val(__val));
    }

  请看HERE一行。__glibcxx_function_requires是用来在编译时确保条件成立的，直观上有点类似于static_assert。我们姑且“望文生义”：函数要求两个条件成立，一是模板参数_InputIterator应当符合_InputIteratorConcept的要求；二是通过iterator_traits获取的迭代器的value_type应当与_Tp一致（显然，要不然你在find什么东西？）。后者比较清晰，前者有点模糊，所以顺藤摸瓜，看_InputIteratorConcept：

  // boost_concept_check.h
  template <class _Tp>
  struct _InputIteratorConcept
  {
  void __constraints() {
    __function_requires< _TrivialIteratorConcept<_Tp> >();
    // require iterator_traits typedef's
    typedef typename std::iterator_traits<_Tp>::difference_type _Diff;
  //      __function_requires< _SignedIntegerConcept<_Diff> >();
    typedef typename std::iterator_traits<_Tp>::reference _Ref;
    typedef typename std::iterator_traits<_Tp>::pointer _Pt;
    typedef typename std::iterator_traits<_Tp>::iterator_category _Cat;
    __function_requires< _ConvertibleConcept<
      typename std::iterator_traits<_Tp>::iterator_category, // HERE
      std::input_iterator_tag> >();
    ++__i;                            // require preincrement operator
    __i++;                            // require postincrement operator
  }
  _Tp __i;
  };

  眼花缭乱吗？没关系，反正追到这里就够了。请再看HERE一行，__function_requires要求std::iterator_traits<_Tp>::iterator_category，即_Tp的迭代器类型（指tag，即input、forward之类），是可以转化到std::input_iterator_tag的！结合上文，_Tp就是我们最开始传入的迭代器的类型名（指typename，不是input、forward之类）_InputIterator，也就是说，我们传入的迭代器的tag，要么就是std::input_iterator_tag，要么就是std::input_iterator_tag的派生类！还记得那几个tag之间的派生关系吗？这就意味着，传入的迭代器被限制为input iterator或包含其功能的更高级迭代器！

  我们的目的已经达到了。然而，在HERE下方，_InputIteratorConcept还测试了两种++运算符，这样就保证了_Tp不仅标称是input iterator，也确实有相应的移动功能。

这些说明应该已经足够了，其余可以自己发掘。可见，这些属性有助于算法进行工作，或许是校验以保证能正常访问元素，或许是获取适当的数据类型（比如算法是一个模板），等等。

小结

总而言之，一个自定义的iterator可以是这样的：

#include <iterator> // For std::forward_iterator_tag
#include <cstddef>  // For std::ptrdiff_t

struct Iterator 
{
    using iterator_category = std::forward_iterator_tag;
    using difference_type   = std::ptrdiff_t;
    using value_type        = int;
    using pointer           = int*;  // or also value_type*
    using reference         = int&;  // or also value_type&
};

可以说，这样就确定了一个迭代器的“基调”。剩下的就只是成员数据和相关函数的实现了，数据可能是一个指向容器内部元素的指针，而函数可能有*、->、++、!=等等。实现哪些函数和想要做的迭代器的类别有关，只要我们在语法上实现了相应的功能，它就是一个该类别的迭代器。而如何实现函数则和相应的容器有关，例如++在vector和list中的实现就可能不一样。

设计模式：迭代器（Iterator Pattern）

迭代器不仅仅是一类对象，更重要的东西是其所蕴含的思想。从更抽象的设计模式的角度来考虑，容器是一种聚合对象，它应该提供一种方法使外部能够访问其元素，而又不暴露其内部结构。同时，考虑到可能有多种访问顺序，且或许存在同时进行多个访问的需求，这种访问的方法也不太适合放在容器的接口里。迭代器就是为了解决这些问题。它主要做了两件事：

• 将访问元素的顺序从容器上剥离出来。既简化了容器的接口，又可以通过不同的迭代器（指一般意义上的迭代器，可以内置一定的访问顺序，不是指STL或任何具体的迭代器）实现不同的遍历顺序（比如说只访问特定的元素）。
• 保存了访问的状态。这样多个迭代器的实例即可实现同时访问。

《设计模式》一书中更加详细地讨论了关于迭代器的一些其他事项，如多态迭代、由谁控制迭代、由谁定义遍历算法等，可以参阅，在此不再赘述。

不管是从上文中的实现来看，还是从设计模式来看，迭代器和容器的联系（或称耦合）是非常紧密的。“迭代器是沟通算法和容器的桥梁”，应该说十分贴切了。

参考资料

本文中没有详细涉及到的iterator_traits的原理等，同学们也可以进一步研究。

1. [Writing a custom iterator in modern C++ - Internal Pointers](https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp?msclkid=1fa5a93dd00211ec8f2ab993dddb33ed)（推荐，可以参考着写iterator）
2. [Range-based for loop (since C++11) - cppreference.com](https://en.cppreference.com/w/cpp/language/range-for)
3. [C++11新特性——range for (bbsmax.com)](https://www.bbsmax.com/A/6pdD98mOzw/)
4. [Iterator library - cppreference.com](https://en.cppreference.com/w/cpp/iterator)
5. [Algorithms library - cppreference.com](https://en.cppreference.com/w/cpp/algorithm)
6. [builtin_constant_p_ykqnjust的博客-CSDN博客___builtin_constant_p](https://blog.csdn.net/ykqnjust/article/details/5797960)
7. [C++STL源码阅读（四）：sort - 百度文库 (baidu.com)](https://wenku.baidu.com/view/4a1a53d9920ef12d2af90242a8956bec0975a591.html)（关于`__glibcxx_function_requires`，也涉及到了iterator）
8. 《设计模式：可复用面向对象软件的基础》，Erich Gamma等著，5.4节Iterator。

[hzhwcmhf]

建议在开头引用 thu-coai/THUOOP#11
最好先科普或者链接下，range-based for需要什么（据我所知只需要begin和end）
后面一些额外的using希望能给一些例子，让大家知道这些东西有什么用

[nine-point-eight-p]

已经修改了。range-based for对迭代器好像也有一些要求（三个重载），当年那位同学也是这么写的。

[hzhwcmhf]

你说的对，确实需要三个重载。
关于例子，能再详细一点，给个实际的代码展示这部分定义的区别呢？
我看好像stl里有std::advance这个函数，对于随机迭代器是O(1)，对于其他是线性的。这个具体实现是因为这些属性变化的吗？

[nine-point-eight-p]

advance的实现确实是因为属性而变化的。这次增加了两个代码分析实例。感觉跟写了两篇总结似的XD

[hzhwcmhf]

辛苦辛苦，现在把为什么需要这些额外信息的原因说的比较清楚啦