用Java设计迭代器

Question

我遇到了许多需要迭代器的问题.通常,它们是简单的事情,您已经拥有了可以遵循的基础数据结构.其他时候,它变得更加复杂.

一个例子是使用有序遍历在没有父链接的情况下迭代BST.这要求您执行以下操作:

• 在构造函数中创建一个堆栈.
• 迭代到最左边的节点.
• 存储有更多节点可供访问,以便从hasNext()轻松返回.
• 存储下一个要访问的节点,以便从next()轻松返回.

您可以完成工作以在hasNext()或next()中找到下一个节点.您还可以在构造函数中或第一次调用hasNext()时找到第一个节点.

---

我的问题

在迭代器实现中,有哪些标准或最佳实践可用于执行大部分工作？一种方式比另一种"更清洁"吗？

Answer 1

首先,合同Iterator要求如果有更多元素则hasNext返回true,并且如果有next则会抛出异常hasNext()==false.

这意味着有两种使用迭代器的样式:while (it.hasNext()) it.next()和try { while (true) it.next(); } catch ....后者不是一个好习惯,但必须得到支持.我之所以提到这一点,是因为你不能依赖hasNext之前的召唤next.我发现这个要求通常是迭代器实现中不必要的复杂性的罪魁祸首.

我的选择是拥有一个带有next值的局部变量.如果next==null无论是下一个值是未知的(我们必须找到它),或者我们已经达到了迭代结束(hasNext()返回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诸如LinkedList,它也支持push和popJava 6一样),以及辅助状态了解每次findNext调用时如何恢复迭代.