Detailed code examples of Java iterators

1. Summary

　 The iterator pattern lives and dies with collections. Generally speaking, as long as we implement a container, we need to also provide the iterator of the container. The advantage of using iterators is that it encapsulates the internal implementation details of the container, provides a unified traversal method for different collections, and simplifies client access and acquisition of data in the container. On this basis, we can use Iterator to complete the traversal of the collection. In addition, the for loop and foreach syntax can also be used to traverse the collection class. ListIterator is a bidirectional iterator unique to the List container family. The main points of this article include:

• Iterator pattern

• Iterator and Iterable Interface

• Loop traversal: similarities and differences of foreach, Iterator, for

• ListIterator brief description (detailed explanation of container List)

2. Iterator pattern

　The iterator pattern lives and dies with collections. Generally speaking, as long as we implement a container, we need to provide the iterator of the container at the same time, just like Collection (List, Set, etc.) in Java. These containers have their own iterators. If we want to implement a new container, of course we also need to introduce the iterator pattern and implement an iterator for our container. The benefits of using iterators are: Encapsulates the internal implementation details of the container. It can provide a unified traversal method for different collections, simplifying client access and obtaining data in the container.

　However, because containers and iterators are so closely related, most languages ​​also provide corresponding iterators while implementing containers, and in most cases, the containers and iterators provided by these languages devices can meet our needs. Therefore, in reality, it is relatively rare that we need to implement the iterator pattern ourselves. We often only need to use existing containers and iterators in the language.

1. Definition and structure

• Definition

  　 Iterator (Iterator) mode, also called Cursor (Cursor) mode. The definition given by GOF is: Provide a method to access each element in a container (container) object without exposing the internal details of the container object.

  　It can be seen from the definition that the Iterator pattern is born for containers. We know that access to container objects must involve traversal algorithms. You can just plug the traversal methods into the container object, or you can not provide any traversal algorithm at all and let the people who use the container implement it themselves. Both cases seem to solve the problem. However, in the former case, the container bears too many functions. It is not only responsible for the maintenance of elements within its own "container" (adding, deleting, modifying, checking, etc.), but also provides an interface for traversing itself; and finally The important thing is that due to the problem of saving the traversal state , multiple traversals cannot be performed on the same container object at the same time, and the reset operation needs to be added. The second method saves trouble, but exposes the internal details of the container.

• Iterator pattern role composition

  　Iterator role (Iterator): The iterator role is responsible for defining the interface for accessing and traversing elements；

  　 Concrete Iterator role (Concrete Iterator): Concrete iterator role To implement the iterator interface , and to record the current position in the traversal ;

  　Container role (Container): The container role is responsible for defining the interface for creating specific iterator roles；

  　Concrete Container: Concrete Container Role Implements the interface to create a concrete iterator role - This Concrete Iterator Role is related to the structure of the container Related .

• Structure diagram
  　　　　　　　

  　 As can be seen from the structure, the iterator pattern adds the role of iterator between the client and the container. The addition of the iterator role can effectively avoid the exposure of internal details of the container, and also makes the design comply with the single responsibility principle.
  　　
  　 It is particularly important to note that in the iterator pattern, the specific iterator role and the specific container role are coupled together - The traversal algorithm is closely related to the internal details of the container. In order to free the client program from the dilemma of coupling with the specific iterator role and avoid modifications to the client program caused by the replacement of the specific iterator role, the iterator pattern abstracts the specific iterator role, making the client program more general and Reusability, this is called polymorphic iteration .

• Applicability

  　1. Access the contents of a container object without exposing its internal representation;

  　2. Supports multiple traversals of container objects;

  　3. Provides a unified interface for traversing different container structures (i.e., supports polymorphic iteration).

2. Example

Since the regulations of the iterator pattern itself are relatively loose, the specific implementations are varied. We only give one example here. Before giving an example, let's first enumerate how to implement the iterator pattern.

• The iterator role defines the interface for traversal, but does not specify who controls the iteration. In the Java Collection framework, the client program controls the traversal process, which is called an external iterator; there is another implementation method that controls iteration by the iterator itself, which is called Internal iterator . External iterators are more flexible and powerful than internal iterators, and the usability of internal iterators in the Java language environment is very weak;

• In the iterator pattern, there is no stipulation on who should implement the traversal algorithm. It seems that it should be done for granted. Implemented in the iterator role. Because it is convenient to use different traversal algorithms on one container, and it is also convenient to apply one traversal algorithm to different containers. But this destroys the encapsulation of the container - the container role must expose its own private properties, which in Java means exposing its private properties to other classes;

  　　

  Then we put it in the container role It is implemented here, so that the role of the iterator is reduced to just storing a function for traversing the current position. But the traversal algorithm is tightly tied to a specific container. In the Java Collection framework, the specific iterator role provided is the internal class defined in the container role, thus protecting the container's encapsulation. But at the same time, the container also provides a traversal algorithm interface, and you can extend your own iterator.

  　Let’s take a look at the implementation of iterators in Java Collection:

//迭代器角色，仅仅定义了遍历接口public interface Iterator<E> {
    boolean hasNext();
    E next();    void remove();
}//容器角色，这里以 List 为例,间接实现了 Iterable 接口public interface Collection<E> extends Iterable<E> {
    ...
    Iterator<E> iterator();
    ...
}
public interface List<E> extends Collection<E> {}
//具体容器角色，便是实现了 List 接口的 ArrayList 等类。为了突出重点这里指罗列和迭代器相关的内容
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {…… 
//这个便是负责创建具体迭代器角色的工厂方法public Iterator<E> iterator() {
　return new Itr();
}
//具体迭代器角色，它是以内部类的形式出来的。 AbstractList 是为了将各个具体容器角色的公共部分提取出来而存在的。
//作为内部类的具体迭代器角色
private class Itr implements Iterator<E> {　
int cursor = 0;
　int lastRet = -1;  
　//集合迭代中的一种“快速失败”机制，这种机制提供迭代过程中集合的安全性. ArrayList 中存在 modCount 属性，增删操作都会使 modCount++，
　//通过两者的对比,迭代器可以快速的知道迭代过程中是否存在 list.add() 类似的操作，存在的话快速失败!　int expectedModCount = modCount;  
　
　public boolean hasNext() {
　　return cursor != size();
　}

　public Object next() {
　　checkForComodification();   
　　//快速失败机制　　try {
　　　Object next = get(cursor);
　　　lastRet = cursor++;
　　　return next;
　　} catch(IndexOutOfBoundsException e) {
　　　checkForComodification();   
　　　//快速失败机制　　　
　　　throw new NoSuchElementException();
　　}
　}

　public void remove() {
　　if (lastRet == -1)
　　　throw new IllegalStateException();
　　　checkForComodification();   //快速失败机制　　try {
　　　AbstractList.this.remove(lastRet);
　　　if (lastRet < cursor)
　　　　cursor--;
　　　lastRet = -1;
　　　expectedModCount = modCount;   
　　　//快速失败机制　　
　　　} 
　　　catch(IndexOutOfBoundsException e) {
　　　throw new ConcurrentModificationException();
　　}
　}  //快速失败机制　final void checkForComodification() {
　　if (modCount != expectedModCount)
　　　throw new ConcurrentModificationException();   
　　　//抛出异常，迭代终止　
　　　}
}

Copy after login

• Usage of iterator pattern

  　The client program must first obtain the specific container role, and then obtain the specific container role through the specific container role Iterator role. In this way, specific iterator roles can be used to traverse the container...

Supports different Way to traverse a container role. The effect will be different depending on the implementation (for example, iterator and listIterator in List).

Simplified the container interface. But in order to improve scalability in Java Collection, the container still provides a traversal interface.

　　3) 简化了遍历方式。对于对象集合的遍历，还是比较麻烦的，对于数组或者有序列表，我们尚可以通过游标来取得，但用户需要在对集合了解很清楚的前提下，自行遍历对象，但是对于 哈希表 来说，用户遍历起来就比较麻烦了。而引入了迭代器方法后，用户用起来就简单的多了。

　　4) 可以提供多种遍历方式。比如，对于有序列表，我们可以根据需要提供正序遍历，倒序遍历两种迭代器，用户用起来只需要得到我们实现好的迭代器，就可以方便的对集合进行遍历了。

　　5) 对同一个容器对象，可以同时进行多个遍历。因为遍历状态是保存在每一个迭代器对象中的。

　　6) 封装性良好，用户只需要得到迭代器就可以遍历，而对于遍历算法则不用去关心。

　　7) 在 Java Collection 中，迭代器提供一种快速失败机制 ( ArrayList是线程不安全的,在ArrayList类创建迭代器之后，除非通过迭代器自身remove或add对列表结构进行修改，否则在其他线程中以任何形式对列表进行修改，迭代器马上会抛出异常，快速失败)，防止多线程下迭代的不安全操作。

　由此，也可以得出迭代器模式的适用范围：

　　1) 访问一个容器对象的内容而无需暴露它的内部表示；

　　2) 支持对容器对象的多种遍历；

　　3) 为遍历不同的容器结构提供一个统一的接口（多态迭代）。

三、Iterator 迭代器与 Iterable 接口

1、Iterator 迭代器接口 ： java.util 包

　　Java 提供一个专门的迭代器接口 Iterator，我们可以对某个容器实现该 Interface，来提供标准的 Java 迭代器。

• 用 Iterator 模式实现遍历集合

  　　Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

  　　例如，如果没有使用 Iterator，遍历一个数组 的方法是使用索引：

for(int i=0; i<array.size(); i++) { ... get(i) ... }

　　而 遍历一个HashSet 又 必须使用 while 循环或 foreach，但不能使用for循环：

while((e=e.next())!=null) { ... e.data() ... }

　　对以上两种方法，客户端都必须事先知道集合的类型（内部结构），访问代码和集合本身是紧耦合的，无法将访问逻辑从集合类和客户端代码中分离出来，从而导致每一种集合对应一种遍历方法，客户端代码无法复用。更恐怖的是，如果以后需要把 ArrayList 更换为 LinkedList，则原来的客户端代码必须全部重写。

　　为解决以上问题，Iterator模式总是用同一种逻辑来遍历集合：

<p style="margin-bottom: 7px;">for(Iterator it = c.iterater(); it.hasNext(); ) { ... } <br/></p>

　　奥秘在于 客户端自身不维护遍历集合的”指针”，所有的内部状态（如当前元素位置，是否有下一个元素）都由 Iterator 来维护，而这个 Iterator 由集合类通过工厂方法生成，因此，它知道如何遍历整个集合。而且，客户端从不直接和集合类打交道，它总是控制Iterator，向它发送”向前”，”向后”，”取当前元素”的指令，就可以间接遍历整个集合。

　　首先看看 java.util.Iterator 接口的定义：

public interface Iterator {
    boolean hasNext(); 
    Object next(); 
    void remove(); // 可选操作 }

　　依赖前两个方法就能完成遍历，典型的代码如下：

for(Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); // 对o的操作... }

　　多态迭代 ： 每一种集合类返回的 Iterator 具体类型可能不同，Array 可能返回 ArrayIterator，Set 可能返回 SetIterator，Tree 可能返回 TreeIterator，但是它们都实现了 Iterator 接口，因此，客户端不关心到底是哪种 Iterator，它只需要获得这个 Iterator 接口即可，这就是面向对象的威力。

2、Iterable 接口 ： java.lang 包

　　Java 中还提供了一个 Iterable 接口，Iterable接口实现后的功能是“返回”一个迭代器 。我们常用的实现了该接口的子接口有: Collection系列，包括 List, Queue, Set 在内。特别值得一提的是，Map 接口没有实现 Iterable 接口。该接口的 iterator() 方法返回一个标准的 Iterator 实现。

• 实现 Iterable 接口来实现适用于 foreach 遍历的自定义类

  　　Iterable 接口包含一个能够产生 Iterator 的 iterator() 方法，并且 Iterable 接口被 foreach 用来在序列中实现移动。因此，实现这个接口允许对象成为 foreach 语句的目标，也就可以通过 foreach语法遍历你的底层序列。

  　　在 JDK1.5 以前，用 Iterator 遍历序列的语法：

for(Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); // 对o的操作... }

　　在 JDK1.5 以及以后的版本中，引进了 foreach，对上面的代码在语法上作了简化 ( 但是限于只读，如果需要remove，还是直接使用 Iterator )：

for(Type t : collection) { ... }

3、思辨

• 为什么一定要去实现 Iterable 这个接口呢？ 为什么不直接实现 Iterator接口 呢？

  　　看一下 JDK 中的集合类，比如 List一族或者Set一族，都是实现了 Iterable 接口，但并不直接实现 Iterator 接口。仔细想一下这么做是有道理的：因为 Iterator接口的核心方法 next() 或者 hasNext() 是依赖于迭代器的当前迭代位置的。若 Collection 直接实现 Iterator 接口，势必导致集合对象中包含当前迭代位置的数据(指针)。当集合在不同方法间被传递时，由于当前迭代位置不可预置，那么 next() 方法的结果会变成不可预知。除非再为 Iterator接口 添加一个 reset() 方法，用来重置当前迭代位置。但即使这样，Collection 也只能同时存在一个当前迭代位置（不能同时多次迭代同一个序列：必须要等到当前次迭代完成并reset后，才能再一次从头迭代）。 而选择实现 Iterable 接口则不然，每次调用都会返回一个从头开始计数的迭代器（Iterator），因此，多个迭代器间是互不干扰的。

四、foreach，Iterator，for

• foreach 和 Iterator 的关系

  　　foreach 是 jdk5.0 新增加的一个循环结构，可以用来处理集合中的每个元素而不用考虑集合的下标。

格式如下 :

 for(variable:collection){ statement; }

　　 定义一个变量用于暂存集合中的每一个元素，并执行相应的语句(块)。Collection 必须是一个数组或者是一个实现了 lterable 接口的类对象。

　　 可以看出，使用 foreach 循环语句的优势在于更加简洁，更不容易出错，不必关心下标的起始值和终止值。forEach 不是关键字,关键字还是 for ，语句是由 iterator 实现的，它们最大的不同之处就在于 remove() 方法上。

　　 特别地，一般调用删除和添加方法都是具体集合的方法，例如：

List list = new ArrayList(); 
list.add(...); 
list.remove(...);
...

　　但是，如果在循环的过程中调用集合的 remove() 方法，就会导致循环出错，因为循环过程中 list.size() 的大小变化了，就导致了错误(Iterator的快速失败机制)。 所以，如果想在循环语句中删除集合中的某个元素，就要用迭代器 iterator 的 remove() 方法，因为它的 remove() 方法不仅会删除元素，还会维护一个标志，用来记录目前是不是可删除状态，例如，你不能连续两次调用它的remove()方法，调用之前至少有一次 next() 方法的调用。因此，foreach 就是为了让用 iterator 循环访问的形式简单，写起来更方便。当然功能不太全,所以若是需要使用删除操作，那么还是要用它原来的形式。

• 使用for循环与使用迭代器iterator的对比

  从效率角度分析：

  　　采用 ArrayList 对随机访问比较快，而for循环中的get()方法，采用的即是随机访问的方法，因此在ArrayList里，for循环较快；

  　　采用 LinkedList 则是顺序访问比较快，iterator 中的next()方法，采用的即是顺序访问的方法，因此在LinkedList里，使用iterator较快。

  从数据结构角度分析：

  　　使用 for循环 适合访问有序结构，可以根据下标快速获取指定元素；而 Iterator 适合访问无序结构，因为迭代器是通过 next() 和 Pre() 来定位的，可以访问没有顺序的集合.

  　　 使用 Iterator 的好处在于可以使用相同方式去遍历集合中元素，而不用考虑集合类的内部实现（只要它实现了 java.lang.Iterable 接口），如果使用 Iterator 来遍历集合中元素，一旦不再使用 List 转而使用 Set 来组织数据，那遍历元素的代码不用做任何修改，如果使用 for 来遍历，那所有遍历此集合的算法都得做相应调整,因为List有序,Set无序,结构不同,他们的访问算法也不一样.

五、ListIterator 简述

1、简述

　　 ListIterator 系列表迭代器，实现了Iterator接口。该迭代器允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。ListIterator 没有当前元素；它的光标位置始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。长度为 n 的列表的迭代器有 n+1 个可能的指针位置，如下面的插入符举例说明：

　　 注意，remove() 和 set(Object) 方法不是根据光标位置定义的；它们是根据对调用 next() 或 previous() 所返回的最后一个元素的操作定义的。

2、与 Iterator 区别

　　 Iterator 和 ListIterator 主要区别有：

• ListIterator 有 add()方法，可以向 List 中添加对象，而 Iterator 不能 ；

• ListIterator 和 Iterator 都有 hasNext()和next()方法，可以实现顺序向后遍历。但是 ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向（顺序向前）遍历，而 Iterator 就不可以 ；

• ListIterator 可以利用 nextIndex() 和 previousIndex() 定位当前的索引位置，而 Iterator 没有此功能 ；

• ListIterator 可以通过 listIterator() 方法和 listIterator(int index) 方法获得，而 Iterator 只能由 iterator() 方法获得 ；

• 二者都可以实现删除对象，但是ListIterator可以使用set()方法实现对象的修改。Iterator 仅能遍历，不能修改。因为ListIterator的这些功能，可以实现对LinkedList, ArrayList等List数据结构的操作。

The above is the detailed content of Detailed code examples of Java iterators. For more information, please follow other related articles on the PHP Chinese website!