Iterator 模式
作用
迭代器模式提供一种方法顺序访问一个集合对象中的各个元素,而又不暴露其内部的表示。
定义
在面向对象的编程中,迭代器模式是一种设计模式,其中迭代器用于遍历容器并访问容器的元素。迭代器模式将算法与容器分离。
有许多种方法可以把对象组成一个集合。底层的容器可以是数组,堆栈,链表,散列表等。当用户希望遍历这些对象的时候,我们不希望用户需要看到底层容器的实现。迭代器模式就是用来处理这种情况的。
看看实现
public interface Iterable<T> {
/**
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}
public interface Collection<E> extends Iterable<E> {
...
/**
* Returns an iterator over the elements in this collection. There are no
* guarantees concerning the order in which the elements are returned
* (unless this collection is an instance of some class that provides a
* guarantee).
*
* @return an <tt>Iterator</tt> over the elements in this collection
*/
Iterator<E> iterator();
...
}
public interface Iterator<E> {
/**
* Returns {@code true} if the iteration has more elements.
* (In other words, returns {@code true} if {@link #next} would
* return an element rather than throwing an exception.)
*
* @return {@code true} if the iteration has more elements
*/
boolean hasNext();
/**
* Returns the next element in the iteration.
*
* @return the next element in the iteration
* @throws NoSuchElementException if the iteration has no more elements
*/
E next();
/**
* Removes from the underlying collection the last element returned
* by this iterator (optional operation). This method can be called
* only once per call to {@link #next}. The behavior of an iterator
* is unspecified if the underlying collection is modified while the
* iteration is in progress in any way other than by calling this
* method.
*
* @implSpec
* The default implementation throws an instance of
* {@link UnsupportedOperationException} and performs no other action.
*
* @throws UnsupportedOperationException if the {@code remove}
* operation is not supported by this iterator
*
* @throws IllegalStateException if the {@code next} method has not
* yet been called, or the {@code remove} method has already
* been called after the last call to the {@code next}
* method
*/
default void remove() {
throw new UnsupportedOperationException("remove");
}
/**
* Performs the given action for each remaining element until all elements
* have been processed or the action throws an exception. Actions are
* performed in the order of iteration, if that order is specified.
* Exceptions thrown by the action are relayed to the caller.
*
* @implSpec
* <p>The default implementation behaves as if:
* <pre>{@code
* while (hasNext())
* action.accept(next());
* }</pre>
*
* @param action The action to be performed for each element
* @throws NullPointerException if the specified action is null
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
Iterator 接口中,最重要的就是 next
和 hasNext
两个方法了。实现了这两个方法,就可以完成遍历一个集合的操作。
for/in 语句
在 Java 中,我们经常可以看到这样的语句
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (int item : list) {
System.out.println(item);
}
在 Kotlin 中,也有这样的语句
for (item in listOf(1, 2, 3)) {
println(item)
}
实际上这些语句依赖了迭代器模式,在编译成字节码的时候,语句会被替换成以下语句的等同实现
Iterator var4 = CollectionsKt.listOf(new Integer[]{1, 2, 3}).iterator();
while(var4.hasNext()) {
int a = ((Number)var4.next()).intValue();
System.out.println(a);
}
正是迭代器将集合底层的具体实现做了屏蔽,我们在上层使用的时候才能有如此丝滑的体验:对于任何类型的集合,都可以用同样的方式实现其遍历。
要点
迭代器允许访问集合的元素,而不需要暴露它的内部结构
迭代器提供了一个通用的接口,让我们遍历集合的项
迭代器将遍历集合的工作封装进一个对象中
- 比如
java.util.LinkedList
的 Iterator 的实现类是其内部类java.util.LinkedList.ListItr
。这个类是private
的,实现了Iterator
接口,这个类的实现并不会对外暴露。
我们应该努力让一个类只分配一个责任
迭代器意味着没有次序,只是取出所有的元素,并不表示取出元素的先后就代表元素的大小次序。对于迭代器来说,数据结构可以是有次序的,或是没有次序的,,甚至数据是可以重复的。除非某个集合的文件有特别说明,否则不可以对迭代器取出的元素大小顺序作出假设。
多线程的情况
先了解一个概念:
Fail-fast
In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process.
举个🌰️
我有一个 LinkedList
1️⃣➡️️2️⃣➡️️3️⃣➡️️4️⃣➡️️5️⃣➡️️6️⃣
有两个线程同时对这个链表操作。我们将其称之为读线程和写线程。
读线程在使用 Iterator 遍历这个链表,假设当前在 3️⃣ 这个位置上,即 hasNext
返回 true, next
返回 4️⃣。
写线程对 2️⃣ 做了修改,将这个 Node 移除掉了。
那么对于读线程来说,迭代器会正常继续向后遍历这个链表,相当于这个链表没有发生过修改。
对于写线程来说,链表已经变成了 1️⃣➡️️3️⃣➡️️4️⃣➡️️5️⃣➡️️6️⃣。
那么对于某些任务,迭代器读取到 2️⃣ 可能就是错误的操作,2️⃣ 已经不再属于这个链表。
对于一个可能已经出现错误的操作,按照 Fail-fast 的原则,我们应该尽早上报这个错误。
为了发现这种情况。 Java 在 AbstractList
这个类里面添加了一个成员变量 modCount
,每当通过 List
提供的接口对其进行修改时,modCount++
。
protected transient int modCount = 0;
LinkedList
继承自 AbstractList
。
创建 java.util.LinkedList.ListItr
对象的时候,会记录当时链表的 modCount
,在每次操作 链表的时候,会先验证当前链表的 modCount
是否和迭代器中记录的一致。如果不一致,说明链表已经发生改变,无法保证迭代器能返回正确的结果。所以我们就看到了这样的错误 throw new ConcurrentModificationException();
注意:这种方式只能发现通过 List 提供的接口对其内容作出的修改。比如上面的例子中,我们持有 Node 2️⃣ ,直接修改其指向下一个节点的指针,将其设为 Null
,迭代器是不会发现这个情况的。
顺便提一嘴,ListIterator
继承自 Iterator
并添加了 add
和 remove
方法,他是怎么实现在迭代的过程中也可以修改 List 的内容的呢?
public interface ListIterator<E> extends Iterator<E> {
...
void add(E e);
void remove();
...
}
既然修改 List 内容是通过迭代器进行的,迭代器已经知晓了 List 内容发生了什么变化,不会出现上面的 List 内容被修改了,迭代器不知道的情况,那么妥善应对了 List 的变化后(这需要编写 Iterator 的开发者来实现,保证 Iterator 访问到的依然是正确的 List 内容),将 Iterator 中记录的 expectedModCount
修改为当前 List 的 modCount
即可,
Refs
Head First 设计模式
By Eric