1. 什么时候需要使用自定义的迭代器？

常见、基本的数组类型

• 对于常见、基本的数组类型，如：int 、char ，我们可以简单地使用下标来进行遍历：

  int array[5] = {1,2,3,4,5};
  
  // 方法1：使用下标遍历
  for (int ind = 0; ind < 5; ++ind) {
      cout << array[ind] << " ";
  }
  

  也可以使用范围来进行遍历，达到和使用下标同样的遍历效果：

  // 方法2：使用范围遍历
  for (int &n: array) {
      cout << n << " ";
  }
  

回到顶部

STL 容器

• 对于 STL 容器来说，如：vector 、list ，我们同样也可以使用下标和范围来进行遍历：

  vector<int> vec = {1,2,3,4,5};
  
  // 方法1：使用下标遍历
  for (int ind = 0; ind < vec.size(); ++ind) {
      cout << vec[ind] << " ";
  }
  
  // 方法2：使用范围遍历
  for (int &n: vec) {
      cout << n << " ";
  }
  

  除了以上两种方法，STL 容器还可以使用迭代器（iterator）进行遍历：

  vector<int>::iterator iter;
  
  // 方法3：使用迭代器遍历
  // .begin() 是指向 vector 首元素的位置的迭代器
  // .end() 是指向 vector 最后一个元素的位置的下一个位置的迭代器
  for (iter = vec.begin(); iter != vec.end(); ++iter) {
      cout << *iter << " ";
  }
  

回到顶部

自定义数据类型

• 下面给出一个简单的自定义类：

  class Group {
  private:
  	vector<vector<int>> students_marks;
      ......
  }
  

  其中，students_marks 是一个用来记录学生若干次的分数的 vector，students_marks[0] 也是一个 vector，用来记录第一个学生的分数，其中 students_marks[0][0] 表示第一个学生的第一个分数。

• 如果要对 students_marks 进行遍历，由于不存在 vector<int> 类型的迭代器，因此方法2和方法3无法使用，只能使用下标遍历法：

  // 定义一个函数，用来输出 vector 中所有元素
  void printvec(vector<int> &vec) {
      for(int ind = 0; ind < vec.size(); ++ind) {
          cout << vec[ind] << " ";
      }
  }
  
  // 使用下标对 vector<int> 类型的元素进行遍历
  for (int ind = 0; ind < students_marks.size(); ++ind) {
      printvec(students_marks[ind]);
  }
  

• 如果要使用以下方法对 students_marks 进行遍历：

  // 定义 Group 类型的 G
  Group G;
  
  // 使用范围遍历
  for(auto v: G) {
      printvec(v);
  }
  

  则需要自己手动编写指向 vector<int> 数据类型的迭代器。

回到顶部

2. 开始编写自定义迭代器之前需要思考的问题

1. 迭代器进行遍历的对象是什么？
2. 迭代器遍历的范围是什么？
3. 迭代器指向的数据是什么类型？

只要想明白这三个问题，就不难实现自定义类型的迭代器。

以上面的类 Group 为例，

我们想遍历的是 students_marks ，将每个学生的分数输出。

对应问题1，迭代器遍历的对象是 vector<vector<int>> students_marks 。

对应问题2，假设总共有 k 个学生，则 students_marks.size() = k ，遍历的范围是从 students_marks[0] 到 students_marks[k-1] 。

对应问题3，迭代器指向的数据是 students_marks[x] ，类型是 vector<int> 。

回到顶部

3. 如何编写及实现自定义类型的迭代器？

在后面的步骤中，一些常用的名词将会以以下标识符代称：

回到顶部

1. 在 object 所处的 class 中定义一个迭代器（iterator）的结构体（struct）：

   class OBJECT_class {
   private:
   	OBJECT_type OBJECT;
       
   public:
       struct Iterator {
           
       }
       
       ......
   }
   

   ---

2. 设定迭代器的属性：

   struct Iterator {
       using iterator_category = std::forward_iterator_tag;
       using difference_type = std::ptrdiff_t;
       using value_type = VALUE_type;
       using reference = const VALUE_type&;
       using pointer = VALUE_type*;
   }
   

   • iterator_category 是迭代器的类型，如果是正常、基础的情况下，选择 forward_iterator_tag 就可以了
   • difference_type 选择 ptrdiff_t
   • 其余的 value_type 、reference 和 pointer 都是自定义的，根据实际情况填写

   ---

3. 定义迭代器的成员变量、构造函数、基础函数

   struct Iterator {
       using iterator_category = std::forward_iterator_tag;
       using difference_type = std::ptrdiff_t;
       using value_type = VALUE_type;
       using reference = const VALUE_type&;
       using pointer = VALUE_type*;
       
       // 构造函数
       Iterator(pointer p) :ptr(p) {}
       
       // 拷贝赋值函数
       Iterator& operator=(const Iterator& it) {
           ptr = it.ptr;
       }
       
       // 等于运算符
       bool operator==(const Iterator& it) const {
           return ptr == it.ptr;
       }
       
       // 不等于运算符
       bool operator!=(const Iterator& it) const {
           return ptr != it.ptr;
       }
       
       // 前缀自加
       Iterator& operator++() {
           ptr++;
           return *this;
       }
       
       // 后缀自加
       Iterator operator ++(int) {
           Iterator tmp = *this;
           ++(*this);
           return tmp;
       }
       
       // 前缀自减
       Iterator& operator--() {
           ptr--;
           return *this;
       }
       
       // 后缀自减
       Iterator operator --(int) {
           Iterator tmp = *this;
           --(*this);
           return tmp;
       }
       
       // 取值运算
       VALUE_type& operator*() {
           return *ptr;
       }
       
   private:
       // 定义一个指针
       pointer ptr; 
   }
   

   • 以上的函数不是必要也不是完整的，如果不需要用到的可以不写，额外需要用到的函数可以自行编写。
   • 但是在大多数情况下，上面这些函数基本上足矣。

   ---

4. 设定遍历的范围：

   class OBJECT_class {
   private:
   	OBJECT_type OBJECT;
       
   public:
       struct Iterator {
           
           ......
           ......
               
       private:
           pointer ptr;
           
       }
       
       // 遍历的第一个元素的位置
       Iterator begin() {
           VALUE_type* head = &OBJECT[0];
           return Iterator(head);
       }
       
       // 遍历的最后一个元素的下一个位置
       Iterator end() {
           VALUE_type* head = &OBJECT[0];
           return Iterator(head + OBJECT.size());
       }
       
       ......
   }
   

   • head 是指向第一个 VALUE 的指针

   ---

回到顶部