迭代器

在开始处理复杂的数据结构时，都会遇到 遍历(traversal) 的问题。这可以用不同的方法来处理，但最常见的遍历方法，比如，vector，是使用一种称为 迭代器(iterator) 的东西。

简单地说，迭代器是一个对象，它可以指向集合中的一个元素，也知道如何移动到集合中的下一个元素。因此，只需要实现++操作符和!=操作符(这样就可以比较两个迭代器并检查它们是否指向相同的东西)。

c++标准库大量使用迭代器，因此我们将讨论它们的使用方式，然后我们将看看如何制作我们自己的迭代器以及迭代器的局限。

标准库中的迭代器

假设你有一个名字列表，例如:

  1. vector<string> names {"john","jane", "jill", "jack"}

如果想要获得names中的第一个名字，可以调用begin()函数。这个函数不会返回第一个名字的值或引用给你; 相反，它会返回一个迭代器给你:

  1. vector<string>::iterator it = names.begin();

begin()既是vector的成员函数，也是全局函数。全局的begin()对于不能包含成员函数c语言风格的数组（而不是std::array)）特别有用。

你可以把begin()返回一个的迭代器看作指针: 对于vector来说，功能上是相似的。例如，可以对迭代器进行提领操作(dereference)来打印实际的名称:

  1. cout << "first name is " << *it << "\n";
  2. // first name is john

迭代器it是可以 前进(advance) 的，即移动到下一个元素。迭代器上的自增操作++强调的是向前移动的概念，也就是说，和指针向前移动的++操作(即递增内存地址)是不相同的。

  1. ++it; // now points to jane

也可以使用迭代器(像指针一样)修改它所指向的元素:

  1. it->append(" goodall"s);
  2. cout << "full name is " << *it << "\n";
  3. // full name is jane goodall

begin()函数对应的当然是end()函数，但它不是指向最后一个元素，而是指向最后一个元素之后的元素：

  1.         1 2 3 4
  2. begin() ^       ^ end()

可以使用end()作为终止条件。例如，让我们使用it来打印列表中其余的名称：

  1. while (++it != names.end())
  2. {
  3.     cout << "another name: " << *it << "\n";
  4. }
  5. // another name: jill
  6. // another name: jack

除了begin()和end()之外，还有rbegin()和rend()，它们允许我们在集合中反向移动。在本例中，你可能已经猜到，rbegin()指向最后一个元素，而rend()指向第一个之前的一个元素:

  1. for (auto ri = rbegin(names); ri != rend(names); ++ri)
  2. {
  3.     cout << *ri;
  4.     if (ri + 1 != rend(names)) // iterator arithmetic
  5.     cout << ", ";
  6. }
  7. cout << endl;
  8. // jack, jill, jane goodall, john

上面的代码有两点需要注意。首先，即使向后遍历vector，我们仍然在迭代器上使用++操作符。其次，我们可以对it做算术操作: ri + 1指向的是ri前一个元素，而不是后一个元素。

STL中也提供不允许修改对象的常量迭代器:它们通过cbegin()/cend()返回，与之对应的是crbegin()/crend()：

  1. vector<string>::const_reverse_iterator jack = crbegin(names);
  2. // won't work
  3. *jack += "reacher";

最后，值得一提的是, 现代c++里面基于范围的for循环(range based for loop)，从容器的begin()一直迭代到end()。

  1. for (auto& name : names)
  2.     cout << "name = " << name << "\n";

注意迭代器在这里是自动提领的: 变量名name是一个引用，但也可以按值进行迭代。

遍历二叉树

让我们回顾一下数据结构里面遍历二叉树的练习。首先，我们定义树中的的节点：

  1. template<typename T>
  2. struct Node 
  3. {
  4.     T value;
  5.     Node<T>* left;
  6.     Node<T>* right;
  7.     Node<T>* parent;
  8.     BinaryTree<T>* tree;
  9. };

每个节点都有指向其左孩子结点、右孩子结点，父结点(如果有的话)以及整个树的指针。可以单独构造一个叶节点，也可以使用其子节点来构造内部结点。

  1.  explicit Node(const T& value) 
  2.         : value(value)
  3.         , left(nullptr)
  4.         , right(nullptr)
  5.         , parent(nullptr)
  6.         , tree(nullptr) 
  7.     { }
  9. Node(const T& value, Node<T>* left, Node<T>* right)
  10.     : value(value)
  11.     , left(left)
  12.     , right(right)
  13.     , parent(nullptr)
  14.     , tree(nullptr) 
  15.     {
  16.         this->left->tree = this->right->tree = tree;
  17.         this->left->parent = this->right->parent = this;
  18.     }
  19. };

最后，我们引入一个通用的成员函数来设置树指针。这是通过在所有节点的子节点上递归完成的:

  1. void set_tree(BinaryTree<T>* t)
  2. {
  3.     tree = t;
  4.     if(left) 
  5.         left->set_tree(t);
  6.     if(right)
  7.         right->set_tree(t);
  8. }

有了这些，我们现在可以定义一个称为BinaryTree的结构，它正是这个结构允许迭代:

  1. template <typename T> 
  2. struct BinaryTree
  3. {
  4.     Node<T>* root = nullptr;
  5.     explicit BinaryTree(Node<T>* const root)
  6.         : root{ root }
  7.     {
  8.         root->set_tree(this);
  9.     }
  10. };

现在我们可以为树定义一个迭代器。迭代二叉树有三种常见的方法，我们首先要实现的是前序遍历preorder:

  • 一旦遇到该元素，就返回该元素。
  • 递归地遍历左子树
  • 递归地遍历右子树

让我们从一个构造函数开始:

  1. template <typename U>
  2. struct PreOrderIterator
  3. {
  4.     Node<U>* current;
  5.     explicit PreOrderIterator(Node<U>* current)
  6.         : current(current)
  7.     {
  9.     }
  10.     // 其他成员
  11. };

需要定义operator !=来与其他迭代器进行比较。因为迭代器的相当于指针，所以这很简单:

  1. bool operator!=(const PreOrderIterator<U>& other)
  2. {
  3.     return this->current != other.current;
  4. }

我们需要定义*操作符来实现提领:

  1. Node<U>& operator*() { return *current; }

现在，最后一个问题是如何从我们的二叉树中把迭代器给暴露出来。如果将前序遍历其定义为树的默认迭代器，则可以如下所示补充成员函数：

  1. typedef PreOrderIterator<T> iterator;
  3. iterator begin()
  4. {
  5.     Node<T>* n = root;
  6.     if(n)
  7.         while(n->left)
  8.             n = n->left;
  9.     return iterator { n };
  10. }
  12. iterator end()
  13. {
  14.     return iterator {nullptr};
  15. }

现在，困难的部分来了:遍历树。这里的挑战是我们使用递归算法，遍历发生在++操作符中，所以我们最终实现如下所示:

  1. PreOrderIterator<U>& operator++()
  2. {
  3.     if(current->right)
  4.     {
  5.         current = current->right;
  6.         while(current->left)
  7.             current = current->left;
  8.     }
  9.     else
  10.     {
  11.         Node<T>* p = current->parent;
  12.         while(p && current == p->right)
  13.         {
  14.             current = p;
  15.             p = p->parent;
  16.         }
  17.         current = p;
  18.     }
  19.     return *this;
  20. }

这太乱了!而且，它看起来一点也不像树遍历的经典实现，因为我们没有递归。

值得注意的是，begin()迭代器并不是从整个树的根开始; 相反，它从最左边可用的节点开始。

现在所有的部分都准备好了，下面是我们如何执行遍历:

  1. BinaryTree<string> family{
  2.     new Node<string>{
  3.         "me", 
  4.         new Node<string>{
  5.             "mother",
  6.             new Node<string>{"mother's mother"},
  7.             new Node<string>{"mother's father"}},
  8.         new Node<string>{"father"}
  9.     }
  10. };
  12. for (auto it = family.begin(); it != family.end(); ++it)
  13. {
  14.     cout << (*it).value << "\n";
  15. }

您也可以将这种遍历形式暴露为一个单独的对象，即:

  1. class pre_order_traversal
  2. {
  3.     BinaryTree<T>& tree;
  4.     public:
  5.         pre_order_traversal(BinaryTree<T>& tree) : tree{ tree } {}
  6.         iterator begin() { return tree.begin(); }
  7.         iterator end() { return tree.end(); }
  8. } pre_order;

可以这样来遍历：

  1. for (const auto& it: family.pre_order)
  2. {
  3.     cout << it.value << "\n";
  4. }

类似地，可以定义in_order和post_order遍历算法来暴露合适的迭代器。

迭代与协程

我们遇到一个严重的问题:在遍历代码中，operator++难以读懂，它与你在Wikipedia上读到的关于树遍历的任何内容都不匹配。它能起作用，但它之所以能起作用，只是因为我们将迭代器初始化为最左边的节点，而不是从根节点开始，这样做是有问题和令人困惑的。

为什么我们会有这个问题?因为++操作符是不可恢复的:它不能在两次调用之间保持其堆栈，因此，不能实现递归。现在，我们是否有一种两全其美的方法：可执行正确递归的可恢复函数? 我们可以用协程(coroutines)来实现。

利用协程，我们可以像这样实现后序遍历:

  1. generator<<Node<T>*> post_order_impl(Node<T>* node)
  2. {
  3.     if(node)
  4.     {
  5.         for(auto x : post_order_impl(node->left))
  6.             co_yield x;
  7.         for(auto y : post_order_impl(node->right))
  8.             co_yield y;
  9.         co_yield node;
  10.     }
  11. }
  12. generator<Node<T>*> post_order()
  13. {
  14.     return post_order_impl(root);
  15. }

这不是很棒吗?算法终于又可读了!而且，看不到begin()/end(): 我们只是返回一个 生成器(generator) ，逐步返回co_yield提供生成的值。在生成每个值之后，我们可以挂起当前操作并执行其他操作(例如，打印值)，然后在不丢失上下文的情况下恢复迭代。这使的递归成为可能并允许我们写出如下的代码:

  1. for(auto it : family.post_order())
  2. {
  3.     cout << it->value << endl;
  4. }

协程是c++的未来，它解决了许多传统迭代器丑陋或不合适的问题。

总结

迭代器设计模式在c++中无处不在，有显式的也有隐式的(例如基于范围的)形式。不同类型的迭代器可以用于迭代不同的对象:例如，反向迭代器可以应用于vector，但不能应用于单链表。

实现自己的迭代器就像提供++和!=操作符一样简单。大多数迭代器都是简单的指针的外观(façades)，在它们被丢弃之前，用于遍历集合一次。

协程修复了迭代器中出现的一些问题:它们允许在调用之间保持状态，这是其他语言(如c#)很久以前就实现了的。因此，协程允许我们编写递归算法。