在 Java 中设计迭代器

Question

我遇到过很多需要迭代器的问题。通常，它们很简单，您已经拥有可以遵循的底层数据结构。其他时候，它会变得更复杂。

一个示例是使用中序遍历在没有父链接的情况下迭代 BST。这需要您执行以下操作：

在构造函数中创建堆栈。
迭代到最左边的节点。
为了方便 return 从 hasNext() 访问更多节点。
存储下一个要访问的节点，以便于从 next() return。

您可以在 hasNext() 或 next() 中定位下一个节点。您还可以在构造函数中或在对 hasNext() 的第一次调用中找到第一个节点。

我的问题

对于在迭代器实现中在哪里完成大部分工作，是否有标准或最佳实践？一种方式 "cleaner" 比另一种方式好吗？

Answer 1

首先，Iterator的合约要求如果元素多了hasNextreturntrue，next如果hasNext()==false.

这意味着有两种使用迭代器的方式：while (it.hasNext()) it.next()和try { while (true) it.next(); } catch ...。后者不是一个好的做法，但必须支持。我提到这个是因为你不能依赖 hasNext 在 next 之前被调用过。我发现这个要求通常是迭代器实现中不必要的复杂性的罪魁祸首。

我的选择是使用一个值为 next 的局部变量。如果 next==null 下一个值未知（我们必须找到它），或者我们已经到达迭代的末尾（hasNext() 将 return false 和 next() 将失败）。还要考虑当下一个值未知时，我们可能已经到了迭代的末尾，但我们还没有意识到。

Node next;

public boolean hasNext() {
   //if the next value already known, do nothing
   if (next==null) {         
     //otherwise lookup the next value
     next=findNext();
   }
   //return true if the next value was found
   return next!=null;
}

public Node next() {
  if (next==null&&!hasNext()) {
     //here we have reached the end of the iteration
     throw new NoSuchElementException();
  } else {
     //either we alredy knowed the next element 
     //or it was found by hasNext
     Node result = next;
     next=null;
     return result;
  }   
}

private Node findNext() {
   //the actual iteration
}

关于中序遍历的情况，你应该保留一个堆栈（注意 Stack 的实现是基于数组和同步的，可能最好使用 Dequeue 这样的as LinkedList，从 Java 6) 起还支持 push 和 pop，以及每次 findNext 时知道如何恢复迭代的辅助状态打电话。

Answer 2

BSTin-order遍历可以通过简单的递归DFS实现（左child->节点->右child）。

回答你的问题：总的来说，我认为迭代器设计没有"best practices"，因为你的数据结构可以任意复杂。一些通用规则：

您的迭代器在任何情况下都必须支持 hasNext() 和 next() 操作。如果你的数据结构是不可变的（或者移除不是典型的），remove() 方法应该抛出 OperationNotSupportedException()。
next() 方法应该在执行开始时检查 hasNext() 值并抛出 NoSuchElementException if hasNext() returns false.
如果你的数据结构有一个迭代器，它应该实现 Iterable<Type> 接口并实现 public Iterator<Type> iterator() 方法。
所以如果你实现了Iterable接口，客户端代码可以使用foreach运算符来处理你的数据结构。如果这种行为是不可取的（例如，将 foreach 与二分图结构一起使用会导致多个客户端错误，因为它不清楚您究竟在迭代什么），您可能应该考虑另一种实现连续迭代的方法。
如果您的数据结构使用列表或集合，您的迭代器实现可以使用适当的集合迭代器。

在任何情况下，您都应该谨慎设计迭代器。每个迭代器都与其数据结构紧密相连，应该一起设计。

在 Java 中设计迭代器

Designing an iterator in Java

java

iterator

iterable