【Java】Iteratorを紐解いてみた

## はじめに

  実装中、リスト内で条件に合致する要素のみを削除したい、という実装を行う際、chatGPTから、for文よりもIteratorを使用した方が良い、と指摘を受けました。  
  Iteratorについてはなんとなく聞いたことがありましたが、色々調べてみると、反復処理内で要素削除を行いたい場合において非常に有用であり、興味深かったのでまとめてみました。
  
  ※誤りありましたら、ご指摘いただけますと幸いです。

## Iteratorとは

  IteratorはJavaのインタフェースでありで、Javaにおいてコレクションの要素を順次処理するために使用されるインタフェースです。  
  主に java.util パッケージに含まれており、コレクション（リスト、セットなど）の要素にアクセスする際に役立つかと思います。  
  
  特定の要素に直接アクセスするのではなく、要素を1つずつ順に取得できるという点がポイントです。  

  [インタフェース Iterator](https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/Iterator.html#next())

### Iteratorインタフェースの主なメソッド3つ
1. boolean hasNext()
  反復処理において、次に要素がある場合にtrueを返します。

2. E next()
  反復処理において次の要素を返し、要素が存在しない場合、NoSuchElementException をスローします。

3. default void remove()
  取得した直前の要素をコレクションから削除します。


## Iteratorを使用して反復処理内で削除を行う
  Iteratorを使用して、反復処理内で削除を行う場合は下記のようになります。

  ```java
  public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);

        // Iteratorの作成
        Iterator<Integer> iterator = list.iterator();

        // コレクションをループして要素を表示
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            // numが10以上の場合要素を削除する
            if (element >= 10) {
                iterator.remove();
            }
        }
        System.out.println(list);
    }

    /* 

        出力結果
        [1]

    */
  ```

  上記コードでは、list内に1,10,100の3種類の数値を入れ、10より大きい値は削除しています。  
  問題なく動作していますね。というか、拡張for文で普通に回してもいいような気すらします。  

  ちなみに、直感的には分かりにくいかもしれませんが、whileループ内、一番初めのhasNext()メソッドでは、list[0]の1から評価が始まります。  
  同時に次行のnext()メソッドにはlist[0]の1が入ります。  

  一応確認として、次のコードでは、list内の各要素を出力を行っています。1,10,100と順番に出力されていることが分かります。

   ```java
  public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);

        // Iteratorの作成
        Iterator<Integer> iterator = list.iterator();

        // コレクションをループして要素を表示
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            System.out.println(element);
        }
    }

    /* 

        出力結果
        1
        10
        100
        
    */
  ```


## ケース① 拡張for文を使用して反復処理内で削除を行う
  さて、次は拡張for文を使用して、反復処理内で削除を行ってみます。

  ```java
  public static void main(String[] args) {
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);

        for (Integer num : list) {
            // numが10以上の場合要素を削除する
            if (num >= 10) {
                list.remove(num);
            }
        }
        System.out.println(list);
    }

    /* 

        出力結果
        [1, 100]

    */
  ```
  
  意図と反する結果となりました。  
  本来は1のみがlistの中に入っていてほしいのですが、100は削除されず、残ってしまっています。


## ケース② さらに、拡張for文を使用した処理で、削除対象を変えてみると、、
  上記で意図と反する結果になったことに加え、削除対象を変えてみると、エラーが発生します。

  ```java
  public static void main(String[] args) {
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);

        for (Integer num : list) {
            // numが100以上の場合要素を削除する
            if (num >= 100) {
                list.remove(num);
            }
        }
        System.out.println(list);
    }

    /* 

        出力結果
        Exception in thread "main" java.util.ConcurrentModificationException
        at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
        at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
        at com.example.practicesb.controller.DemoController.main(DemoController.java:16)

    */
  ```
  
  先程のコードでは、10より大きい値は削除するという形でしたが、今回条件を100以上に変えたところ**ConcurrentModificationException** という例外が発生しました。


## これらの原因を探るべく、拡張for文を紐解いてみる
  これらの原因は、普段何気なく使っている拡張for文の裏側にあります。  
  まず、拡張for文ですが、内部的にはIteratorを使用しているという前提があります。  
  だからいつもの記述をするだけで、順次要素を呼び出せているわけですね。  

  拡張for文のJava言語仕様を確認してみると、下記のようになっています。

  ```java
    for ( I #i = Expression .iterator(); #i.hasNext(); ) {
        {VariableModifier} T Identifier = ( TargetType ) #i.next();
        ステートメント
    }
  ```

  [Java言語仕様 14.14.2. 強化されたforステートメント](https://docs.oracle.com/javase/specs/jls/se20/html/jls-14.html#jls-14.14.2)  
  
  ここでキーになるのが、**hasNext()メソッド**と**next()メソッド**の呼び出される順序です。  
  先に**hasNext()メソッド**が呼ばれ、**next()メソッド**が次に呼び出されています。この部分は後で重要になりますので今はスキップします。  

  続いて、next()メソッドの実装です。

  ```java
    public E next() {
        checkForComodification();
        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];
    }
  ```

  一番初めに**checkForComodification()メソッド**を呼び出していることが分かります。  
  では、更に**checkForComodification()メソッド**も調べてみましょう。

  ```java
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

  ```

  どうやら、**modCount** という値と **expectedModCount** の値が異なる場合に、**ConcurrentModificationException**を出力していることが分かりました。

  **modCount** と **expectedModCount** ですが、簡単に言うと、  
    
  **modCount** → 実際にコレクションが変更された回数で、remove()やadd()等もカウントされる。
  **expectedModCount** → Iterator作成時点でのmodCountが記録されており、Iteratorによりコレクションが変更された回数（Iteratorにより、という部分が重要）  
    
  というような違いがあります。


  ## ケース②でConcurrentModificationExceptionが発生したわけ  
  Iteratorを使用してremove()メソッドを呼び出す場合は、expectedModCount と modCountの値は必ず等しくなるはずです。（Iteratorによりコレクションが変更されているため） 
  先程の例を再度見てみましょう。 

  ```java
  public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);
        // この時点でmodCountは3

        // そしてexpectedModCountもこの時点では3
        Iterator<Integer> iterator = list.iterator();

        // コレクションをループして要素を表示
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            // numが10以上の場合要素を削除する
            if (element >= 10) {
                //ここでremove()が呼ばれ、modCountは4
                //Iteratorによりコレクションが変更されているので、expectedModCountも4
                iterator.remove();
            }

            // 100を削除する場合も同様両者1ずつインクリメントされる
        }
        System.out.println(list);
    }

    /* 

        出力結果
        [1]

    */
  ```
    
  しかし拡張for文を使用した場合、**Iteratorのremove()メソッドを拡張for文から直接呼び出すことはできません。**  
  そのため、expectedModCount と modCount の値にズレが生じます。  
  下記を見てみましょう。

  ```java
  ```java
    public static void main(String[] args) {
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);
        // この時点でmodCountは3

        // そしてexpectedModCountもこの時点では3（for文作成時もexpectedModCountは作成される）
        for (Integer num : list) {
            // numが100以上の場合要素を削除する
            if (num >= 100) {
                //ここでremove()が呼ばれ、modCountは4
                //しかしIteratorのremove()メソッドは呼び出せず、expectedModCountは3のまま
                //modCount != expectedModCount となったのでConcurrentModificationExceptionが発生
                list.remove(num);
            }
        }
        System.out.println(list);
    }

    /* 

        出力結果
        Exception in thread "main" java.util.ConcurrentModificationException
        at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
        at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
        at com.example.practicesb.controller.DemoController.main(DemoController.java:16)

    */
  ```


  ## じゃあどうしてケース①でConcurrentModificationExceptionが発生しなかったのか？  
  これまで記載した内容通りであれば、ケース①の場合であってもケース②同様、expectedModCount と modCount の値にズレが生じるはずです。  

  しかし、コンパイルは成功しています。が、削除したかったはずの100は削除できていません。  
  これはなぜでしょうか。  

  ここで、先程拡張for文のJava言語仕様解説時に明記した、**hasNext()メソッド**と**next()メソッド**の呼び出される順序が重要になってきます。  
    
  **hasNext()メソッド**では、現在位置（インデックス）とリストのサイズ（インデックスの最大値）が合っていない場合に、次の要素へアクセスするような制御構造になっています。  
    
  そして、remove()で削除された場合、それ以降にある値は、**前詰めで要素が移動します。**
  これらを踏まえた上で、もう一度ケース①のコードを見てみましょう。 

  ```java
  public static void main(String[] args) {
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(100);

        // リストサイズ（インデックスの最大値）は2
        for (Integer num : list) {
            // numが10以上の場合要素を削除する
            if (num >= 10) {
                /*
                    【1回目】
                    現在位置（インデックス）は1です。
                    list[1]の10を削除します。

                    削除後、10の後ろにある100は前詰めで移動するので、
                    list[0] = 1
                    list[1] = 100
                    list[2] = なし
                    となります。
                */
                list.remove(num);
            }

            /*
                【1回目の削除実行後】
                ここから次のループに進むため、現在位置は2になるわけですが、
                リストサイズも2であることから、ループは終了します。
                しかし、100はlist[1]に存在するため、評価されません。
            */
        }
        System.out.println(list);
    }

    /* 

        出力結果
        [1, 100]

    */
  ``` 

  このようになっているため、結論、**リストの最後から2番目の要素を削除した場合は例外が発生しない**ことが分かります。  
  しかし、例外こそ発生しませんが、意図して挙動にはなりません。  
  よって、Iteratorを使用すべきだと言えます。


## まとめ
  実際に実装していて感じた疑問点や違和感を解消できてよかったです。  
  裏側の仕組みは別に知らなくても実装はできますが、やはり理解しているのとしていないのでは、またどこかで躓くケースもあるかと思います。  
    
  分からない、疑問に思う部分は随時調べることの癖付けの意も込めて、定期的にまとめていきたいと思います。

## 参考にさせていただいた記事
  [【Java】ConcurrentModificationExceptionから学ぶListと拡張for文の仕組み](https://qiita.com/ist-a-ku/items/91995810a0eb79da1dbd)
  [Iteratorでコレクションの要素を安全に削除する](https://qiita.com/yudai_suita/items/4db007d4ca933fda8dfc)