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);
       }
   }
}
```

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

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

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


在调用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);
       }
   }
}
```