我遇到了许多需要迭代器的问题。通常,它们是简单的事情,您已经具有可以依赖的基础数据结构。其他时候,它变得更加复杂。
一个示例是使用有序遍历在没有父链接的情况下对BST进行迭代。这要求您执行以下操作:
您可以完成工作以在hasNext()或next()中找到下一个节点。您还可以在构造函数中或在对hasNext()的第一次调用中找到第一个节点。
我的问题
在迭代器实现中,有哪些标准或最佳实践可以在哪里完成大部分工作?一种方法比另一种“清洁”吗?
首先,如果有更多元素,的合同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
,也支持Java 6的aspush
和pop
as),以及辅助状态了解如何在每次findNext
调用时恢复迭代。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句