Java迭代器

# 第12章 迭代器

## 本章學習目標

- 理解foreach循環(huán)語法糖的概念
- 掌握使用Iterator迭代器遍歷集合
- 理解Iterator迭代器的快速失敗機制
- 掌握列表迭代器ListIterator的使用

## 12.1 foreach循環(huán)

foreach循環(huán)是增強for循環(huán)。foreach循環(huán)的語法格式：

```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循環(huán)只是一種語法糖，foreach循環(huán)可以用來遍歷數(shù)組與Collection集合。

- 當foreach循環(huán)變量數(shù)組時，底層使用的仍然是普通for循環(huán)。
- 當foreach循環(huán)變量Collection集合時，底層使用的是Iterator迭代器（見下一小節(jié)）。

代碼示例：

```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循環(huán)與增強for循環(huán)的區(qū)別：

- 普通for循環(huán)可以用來重復執(zhí)行某些語句，而增強for循環(huán)只能用來遍歷數(shù)組或Collection集合
- 普通for循環(huán)可以用來遍歷數(shù)組或者List集合，且必須指定下標信息。而增強for循環(huán)在遍歷數(shù)組或Collection集合時，不用也不能指定下標信息。
- 普通for循環(huán)在遍歷數(shù)組或List集合時，可以替換元素，但是增強for循環(huán)不可以替換元素。

## 12.2 Iterator迭代器

### 12.2.1 Iterable接口

Collection<E>接口繼承了java.lang.Iterable<T>接口，凡是實現(xiàn)Iterable<T>接口的集合都可以使用foreach循環(huán)進行遍歷。Iterable<T>接口包含：

- 抽象方法：`public Iterator iterator()`，黃永玉獲取對應的迭代器對象，用來遍歷集合中的元素。所有Collection系列的集合都重寫了該方法，即都支持foreach循環(huán)和Iterator迭代器的遍歷方式。
- 默認方法：`public default void forEach(Consumer<? super T> action)`，該方法是Java8引入的，通過傳入的Consumer接口的實現(xiàn)類對象，完成集合元素的迭代。

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

- void accept(T t)：對元素t執(zhí)行給定的操作

```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接口

在程序開發(fā)中，經(jīng)常需要遍歷集合中的所有元素。針對這種需求，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集合元素的通用獲取方式。在取元素之前先要判斷集合中有沒有元素，如果有，就把這個元素取出來。繼續(xù)再判斷，如果還有就再取出來，直到把集合中的所有元素全部取出。這種獲取元素的方式，專業(yè)術語稱為迭代。

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());//取出下一個元素
       }
   }
}

> 提示：在進行集合元素取出時，如果集合中已經(jīng)沒有元素了，還繼續(xù)使用迭代器的next方法，將會發(fā)生java.util.NoSuchElementException沒有集合元素的錯誤。

對于集合類型來說，foreach循環(huán)其實就是使用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 迭代器的實現(xiàn)原理

我們在之前案例已經(jīng)完成了Iterator遍歷集合的整個過程。當遍歷集合時，首先通過調用集合的iterator()方法獲得迭代器對象，然后使用hashNext()方法判斷集合中是否存在下一個元素，如果存在，則調用next()方法將元素取出，否則說明已到達了集合末尾，停止遍歷元素。

Iterator迭代器對象在遍歷集合時，內部采用指針的方式來跟蹤集合中的元素，為了讓初學者能更好地理解迭代器的工作原理，接下來通過一個圖例來演示Iterator對象迭代元素的過程：


在調用Iterator的next方法之前，迭代器指向第一個元素，當?shù)谝淮握{用迭代器的next方法時，返回第一個元素，然后迭代器的索引會向后移動一位，指向第二個元素，當再次調用next方法時，返回第二個元素，然后迭代器的索引會再向后移動一位，指向第三個元素，依此類推，直到hasNext方法返回false，表示到達了集合的末尾，終止對元素的遍歷。

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

`java.util.Iterator<T>`迭代器接口中還有一個默認方法：void remove() ;

那么，既然Collection已經(jīng)有remove(xx)方法了，為什么Iterator迭代器還要提供刪除方法呢？

因為在JDK1.8之前Collection接口沒有removeIf方法，即無法根據(jù)條件刪除。

例如：要刪除以下集合元素中的偶數(shù)

```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方法無法實現(xiàn)刪除“偶數(shù)”
       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`迭代器創(chuàng)建后的任意時間從結構上修改了集合（通過迭代器自身的 remove 或 add 方法之外的任何其他方式），則迭代器將拋出 `ConcurrentModificationException`。因此，面對并發(fā)的修改，迭代器很快就完全失敗，而不是冒著在將來不確定的時間任意發(fā)生不確定行為的風險。

這樣設計是因為，迭代器代表集合中某個元素的位置，內部會存儲某些能夠代表該位置的信息。當集合發(fā)生改變時，該信息的含義可能會發(fā)生變化，這時操作迭代器就可能會造成不可預料的事情。因此，果斷拋異常阻止，是最好的方法。這就是Iterator迭代器的快速失?。╢ail-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(){
       //現(xiàn)在不鼓勵大家用這種方式刪除了，但是如果你要用，要注意寫法
       //現(xiàn)在推薦用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]
   }
}
```

那么迭代器如何實現(xiàn)快速失?。╢ail-fast）機制的呢？

* 在ArrayList等集合類中都有一個modCount變量。它用來記錄集合的結構被修改的次數(shù)。
* 當我們給集合添加和刪除操作時，會導致modCount++。
* 然后當我們用Iterator迭代器遍歷集合時，創(chuàng)建集合迭代器的對象時，用一個變量記錄當前集合的modCount。例如：`int expectedModCount = modCount;`，并且在迭代器每次next()迭代元素時，都要檢查 `expectedModCount != modCount`，如果不相等了，那么說明你調用了Iterator迭代器以外的Collection的add,remove等方法，修改了集合的結構，使得modCount++，值變了，就會拋出ConcurrentModificationException。

下面以AbstractList<E>和ArrayList.Itr迭代器為例進行源碼分析：

AbstractList<E>類中聲明了modCount變量，modCount是這個list被結構性修改的次數(shù)。子類使用這個字段是可選的，如果子類希望提供fail-fast迭代器，它僅僅需要在add(int, E),remove(int)方法（或者它重寫的其他任何會結構性修改這個列表的方法）中添加這個字段。調用一次add(int,E)或者remove(int)方法時必須且僅僅給這個字段加1，否則迭代器會拋出偽裝的ConcurrentModificationExceptions錯誤。如果一個實現(xiàn)類不希望提供fail-fast迭代器，則可以忽略這個字段。

Arraylist的Itr迭代器：

```java
  private class Itr implements Iterator<E> {
       int cursor;      
       int lastRet = -1; 
       int expectedModCount = modCount;//在創(chuàng)建迭代器時，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接口的實現(xiàn)類。
       演示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接口的實現(xiàn)類。
       演示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);
       }
   }
}
```