Java迭代器

# 第12章 迭代器

## 本章学习目标

- 理解foreach循环语法糖的概念
- 掌握使用Iterator迭代器遍历集合
- 理解Iterator迭代器的快速失败机制
- 掌握列表迭代器ListIterator的使用

## 12.1 foreach循环

foreach循环是增强for循环。foreach循环的语法格式:

```java
for(元素类型 元素名 : 集合名等){
}
//这里元素名就是一个临时变量,自己命名就可以
```
```java
public class TestForeach {
   @Test
   public void test01(){
       Collection<String> coll = new ArrayList<>();
       coll.add("小李广");
       coll.add("扫地僧");
       coll.add("石破天");
       for (String o : coll) {
           System.out.println(o);
       }
   }
}
```

foreach循环只是一种语法糖,foreach循环可以用来遍历数组与Collection集合。

- 当foreach循环变量数组时,底层使用的仍然是普通for循环。
- 当foreach循环变量Collection集合时,底层使用的是Iterator迭代器(见下一小节)。

代码示例:

```java
package com.atguigu.api;
public class TestForeach {
   public static void main(String[] args) {
       int[] nums = {1,2,3,4,5};
       for (int num : nums) {
           System.out.println(num);
       }
       System.out.println("-----------------");
       String[] names = {"张三","李四","王五"};
       for (String name : names) {
           System.out.println(name);
       }
   }
}
```

普通for循环与增强for循环的区别:

- 普通for循环可以用来重复执行某些语句,而增强for循环只能用来遍历数组或Collection集合
- 普通for循环可以用来遍历数组或者List集合,且必须指定下标信息。而增强for循环在遍历数组或Collection集合时,不用也不能指定下标信息。
- 普通for循环在遍历数组或List集合时,可以替换元素,但是增强for循环不可以替换元素。

## 12.2 Iterator迭代器

### 12.2.1 Iterable接口

Collection<E>接口继承了java.lang.Iterable<T>接口,凡是实现Iterable<T>接口的集合都可以使用foreach循环进行遍历。Iterable<T>接口包含:

- 抽象方法:`public Iterator iterator()`,黄永玉获取对应的迭代器对象,用来遍历集合中的元素。所有Collection系列的集合都重写了该方法,即都支持foreach循环和Iterator迭代器的遍历方式。
- 默认方法:`public default void forEach(Consumer<? super T> action)`,该方法是Java8引入的,通过传入的Consumer接口的实现类对象,完成集合元素的迭代。

`java.util.function.Consumer`接口的抽象方法:

- void accept(T t):对元素t执行给定的操作

```java
package com.atguigu.iter;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.function.Consumer;
public class TestForEachMethod {
   @Test
   public void test1(){
       Collection coll = new ArrayList();
       coll.add("小李广");
       coll.add("扫地僧");
       coll.add("石破天");
       coll.forEach(new Consumer() {
           @Override
           public void accept(Object o) {
               System.out.println(o);
           }
       });
   }
}
```

 

### 12.2.2 Iterator接口

在程序开发中,经常需要遍历集合中的所有元素。针对这种需求,JDK专门提供了一个接口`java.util.Iterator<E>`。`Iterator<E>`接口也是Java集合中的一员,但它与`Collection<E>`、`Map<K,V>`接口有所不同,`Collection<E>`接口与`Map<K,V>`接口主要用于存储元素,而`Iterator<E>`主要用于迭代访问(即遍历)`Collection<E>`中的元素,因此`Iterator<E>`对象也被称为迭代器。

* **迭代**:即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素,如果有,就把这个元素取出来。继续再判断,如果还有就再取出来,直到把集合中的所有元素全部取出。这种获取元素的方式,专业术语称为迭代。

Iterator接口的常用方法如下:

* `public E next()`:返回迭代的下一个元素。
* `public boolean hasNext()`:如果仍有元素可以迭代,则返回 true。

接下来我们通过案例学习如何使用Iterator迭代集合中元素:


package com.atguigu.iterator;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class TestIterator {
   @Test
   public void test01(){
       Collection<String> coll = new ArrayList<>();
       coll.add("小李广");
       coll.add("扫地僧");
       coll.add("石破天");
       Iterator<String> iterator = coll.iterator();
       System.out.println(iterator.next());
       System.out.println(iterator.next());
       System.out.println(iterator.next());
       System.out.println(iterator.next());
   }
   @Test
   public void test02(){
       Collection<String> coll = new ArrayList<>();
       coll.add("小李广");
       coll.add("扫地僧");
       coll.add("石破天");
       Iterator<String> iterator = coll.iterator();//获取迭代器对象
       while(iterator.hasNext()) {//判断是否还有元素可迭代
           System.out.println(iterator.next());//取出下一个元素
       }
   }
}

> 提示:在进行集合元素取出时,如果集合中已经没有元素了,还继续使用迭代器的next方法,将会发生java.util.NoSuchElementException没有集合元素的错误。

对于集合类型来说,foreach循环其实就是使用Iterator迭代器来完成元素的遍历的。

```java
package com.atguigu.iterator;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
public class TestForeach {
   @Test
   public void test01(){
       Collection<String> coll = new ArrayList<>();
       coll.add("小李广");
       coll.add("扫地僧");
       coll.add("石破天");
       for (String o : coll) {
           System.out.println(o);
       }
   }
}
```

image-20220128010114124.png

 

### 12.2.3 迭代器的实现原理

我们在之前案例已经完成了Iterator遍历集合的整个过程。当遍历集合时,首先通过调用集合的iterator()方法获得迭代器对象,然后使用hashNext()方法判断集合中是否存在下一个元素,如果存在,则调用next()方法将元素取出,否则说明已到达了集合末尾,停止遍历元素。

Iterator迭代器对象在遍历集合时,内部采用指针的方式来跟踪集合中的元素,为了让初学者能更好地理解迭代器的工作原理,接下来通过一个图例来演示Iterator对象迭代元素的过程:

![](images/迭代器原理图.bmp)

在调用Iterator的next方法之前,迭代器指向第一个元素,当第一次调用迭代器的next方法时,返回第一个元素,然后迭代器的索引会向后移动一位,指向第二个元素,当再次调用next方法时,返回第二个元素,然后迭代器的索引会再向后移动一位,指向第三个元素,依此类推,直到hasNext方法返回false,表示到达了集合的末尾,终止对元素的遍历。

 

### 12.2.4 使用Iterator迭代器删除元素

`java.util.Iterator<T>`迭代器接口中还有一个默认方法:void remove() ;

那么,既然Collection已经有remove(xx)方法了,为什么Iterator迭代器还要提供删除方法呢?

因为在JDK1.8之前Collection接口没有removeIf方法,即无法根据条件删除。

例如:要删除以下集合元素中的偶数

```java
package com.atguigu.iterator;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class TestIteratorRemove {
   @Test
   public void test01(){
       Collection<Integer> coll = new ArrayList<>();
       coll.add(1);
       coll.add(2);
       coll.add(3);
       coll.add(4);
//        coll.remove(?)//没有removeIf方法无法实现删除“偶数”
       Iterator<Integer> iterator = coll.iterator();
       while(iterator.hasNext()){
           Integer element = iterator.next();
           if(element%2 == 0){
               iterator.remove();
           }
       }
       System.out.println(coll);
   }
}
```

### 12.2.5 Iterator迭代器的快速失败机制

如果在`Iterator`迭代器创建后的任意时间从结构上修改了集合(通过迭代器自身的 remove 或 add 方法之外的任何其他方式),则迭代器将抛出 `ConcurrentModificationException`。因此,面对并发的修改,迭代器很快就完全失败,而不是冒着在将来不确定的时间任意发生不确定行为的风险。

这样设计是因为,迭代器代表集合中某个元素的位置,内部会存储某些能够代表该位置的信息。当集合发生改变时,该信息的含义可能会发生变化,这时操作迭代器就可能会造成不可预料的事情。因此,果断抛异常阻止,是最好的方法。这就是Iterator迭代器的快速失败(fail-fast)机制。

注意,迭代器的快速失败行为不能得到保证,迭代器只是尽最大努力地抛出 `ConcurrentModificationException`。因此,编写依赖于此异常的程序的方式是错误的,正确做法是:*迭代器的快速失败行为应该仅用于检测 bug。

```java
package com.atguigu.iter;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class TestRemoveElement {
   @Test
   public void test1(){
       Collection other = new ArrayList();
       other.add("atguigu");
       other.add("hello");
       other.add("java");
       //删除包含a字母的元素
       Iterator iterator = other.iterator();
       while(iterator.hasNext()){
           Object next = iterator.next();//取出元素
           String s = (String) next;//向下转型
           if(s.contains("a")){
               //删除s
               other.remove(s);
           }
       }
       System.out.println(other);//ConcurrentModificationException
   }
   @Test
   public void test2(){
       Collection other = new ArrayList();
       other.add("hello");
       other.add("atguigu");
       other.add("java");
       //删除包含a字母的元素
       Iterator iterator = other.iterator();
       while(iterator.hasNext()){
           Object next = iterator.next();//取出元素
           String s = (String) next;//向下转型
           if(s.contains("a")){
               //删除s
               other.remove(s);
           }
       }
       System.out.println(other);//[hello, java]
   }
   @Test
   public void test3(){
       //现在不鼓励大家用这种方式删除了,但是如果你要用,要注意写法
       //现在推荐用removeIf方法
       Collection other = new ArrayList();
       other.add("hello");
       other.add("atguigu");
       other.add("java");
       //删除包含a字母的元素
       Iterator iterator = other.iterator();
       while(iterator.hasNext()){
           Object next = iterator.next();//取出元素
           String s = (String) next;//向下转型
           if(s.contains("a")){
               //删除s
//                other.remove(s);//错误的
               iterator.remove();//改为迭代器的删除方法
           }
       }
       System.out.println(other);//[hello, java]
   }
}
```

那么迭代器如何实现快速失败(fail-fast)机制的呢?

* 在ArrayList等集合类中都有一个modCount变量。它用来记录集合的结构被修改的次数。
* 当我们给集合添加和删除操作时,会导致modCount++。
* 然后当我们用Iterator迭代器遍历集合时,创建集合迭代器的对象时,用一个变量记录当前集合的modCount。例如:`int expectedModCount = modCount;`,并且在迭代器每次next()迭代元素时,都要检查 `expectedModCount != modCount`,如果不相等了,那么说明你调用了Iterator迭代器以外的Collection的add,remove等方法,修改了集合的结构,使得modCount++,值变了,就会抛出ConcurrentModificationException。

下面以AbstractList<E>和ArrayList.Itr迭代器为例进行源码分析:

AbstractList<E>类中声明了modCount变量,modCount是这个list被结构性修改的次数。子类使用这个字段是可选的,如果子类希望提供fail-fast迭代器,它仅仅需要在add(int, E),remove(int)方法(或者它重写的其他任何会结构性修改这个列表的方法)中添加这个字段。调用一次add(int,E)或者remove(int)方法时必须且仅仅给这个字段加1,否则迭代器会抛出伪装的ConcurrentModificationExceptions错误。如果一个实现类不希望提供fail-fast迭代器,则可以忽略这个字段。

Arraylist的Itr迭代器:

```java
  private class Itr implements Iterator<E> {
       int cursor;      
       int lastRet = -1; 
       int expectedModCount = modCount;//在创建迭代器时,expectedModCount初始化为当前集合的modCount的值
       public boolean hasNext() {
           return cursor != size;
       }
       @SuppressWarnings("unchecked")
       public E next() {
           checkForComodification();//校验expectedModCount与modCount是否相等
           int i = cursor;
           if (i >= size)
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.this.elementData;
           if (i >= elementData.length)
               throw new ConcurrentModificationException();
           cursor = i + 1;
           return (E) elementData[lastRet = i];
       }
          final void checkForComodification() {
           if (modCount != expectedModCount)//校验expectedModCount与modCount是否相等
               throw new ConcurrentModificationException();//不相等,抛异常
       }
}
```

ArrayList的remove方法:

```java
   public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   }

   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
   }
```

## 12.3 列表专用迭代器ListIterator

List 集合额外提供了一个 listIterator() 方法,该方法返回一个 ListIterator 列表迭代器对象, ListIterator 接口继承了 Iterator 接口,提供了专门操作 List 的方法:

* void add():通过迭代器添加元素到对应集合
* void set(Object obj):通过迭代器替换正迭代的元素
* void remove():通过迭代器删除刚迭代的元素
* boolean hasPrevious():如果以逆向遍历列表,往前是否还有元素。
* Object previous():返回列表中的前一个元素。
* int previousIndex():返回列表中的前一个元素的索引
* boolean hasNext()
* Object next()
* int nextIndex()

```java
package com.atguigu.list;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class TestListIterator {
   @Test
   public void test7() {
        /*
       ArrayList是List接口的实现类。
       演示ListIterator迭代器
        */
       List<String> list = new ArrayList<>();
       list.add("hello");
       list.add("java");
       list.add("world");
       list.add("mysql");
       list.add("java");
       ListIterator<String> stringListIterator = list.listIterator();
       while(stringListIterator.hasNext()){
           int index = stringListIterator.nextIndex();
           String next = stringListIterator.next();
           if(next.equals("java")){
               stringListIterator.set("JavaEE");
           }
       }
       System.out.println(list);//[hello, JavaEE, world, mysql, JavaEE]
   }
   @Test
   public void test6() {
        /*
       ArrayList是List接口的实现类。
       演示ListIterator迭代器
        */
       List<String> list = new ArrayList<>();
       list.add("hello");
       list.add("java");
       list.add("world");
       list.add("mysql");
       list.add("java");
       ListIterator<String> stringListIterator = list.listIterator();
       while(stringListIterator.hasNext()){
           int index = stringListIterator.nextIndex();
           String next = stringListIterator.next();
           System.out.println("index = " + index +",next = " + next);
       }
       System.out.println("---------------");
       while(stringListIterator.hasPrevious()){
           int index = stringListIterator.previousIndex();
           String previous = stringListIterator.previous();
           System.out.println("index = " + index +",previous = " + previous);
       }
       System.out.println("---------------");
       stringListIterator = list.listIterator(2);
       while(stringListIterator.hasNext()){
           int index = stringListIterator.nextIndex();
           String next = stringListIterator.next();
           System.out.println("index = " + index +",next = " + next);
       }
   }
}
```