概要
ArrayListの要素を削除するときの、下記2種類のremove()メソッドの挙動の違いを理解することを目的とし、Java API等の言語仕様説明を交えながらサンプルコードを動かします。
- ArrayListクラスのremove()メソッド
- ArrayListクラスのiterator()メソッドから取得したイテレータのremove()メソッド
実用性よりは知識を深めることに重点を置いた内容となっています。
対象
Java初級〜中級レベルの方に伝わる説明を心掛けています。
より具体的には…
- オブジェクト指向の入門レベルを一通り学び終えている人
- ArrayListの要素をループ内で思った通りに削除できなかった人
- 拡張for文でコレクションの要素を削除しようとしたら謎のエラーが出た人
- イテレータをあまり使ったことがない人
- 何となくでも「イテレータとは、ポインタとかカーソルとか矢印みたいに、コレクションの要素を指し示す何かそういうやつ」と分かっている人
1. コレクションの要素を削除するメソッドremove
ArrayList<E>クラスをはじめとするCollection<E>を実装するクラスでは、
要素を削除するためにremoveメソッドを使いますが、
removeメソッドには2種類あります。
以下、Collection<E>を実装するコレクションクラスの代表例としてArrayList<E>クラスを取り上げます。
1つは、コレクションクラス自身が実装するメソッドremoveです。
ArrayList<E>クラスの場合、
- remove(E object)
- remove(int index)
がオーバーロードされています。
List<String> list = new ArrayList<String>(fooList);
list.remove(2); // 2番目の要素を削除
list.remove("bar"); // 最初に見つかった"bar"という要素を削除
もう1つは、Iterator<E>インタフェースが定義するデフォルトメソッドremoveです。
Collection<E>の実装クラスはiterator()メソッドを持っており、このメソッドからイテレータを取得して使います。
List<String> list = new ArrayList<String>(fooList);
Iterator<String> iterator = list.iterator(); // イテレータを生成・取得
iterator.next(); // 現在のカーソル位置(0番目)を記録し、カーソルを1つ次(1番目)へ進める
iterator.next(); // 現在のカーソル位置(1番目)を記録し、カーソルを1つ次(2番目)へ進める
iterator.next(); // 現在のカーソル位置(2番目)を記録し、カーソルを1つ次(3番目)へ進める
iterator.remove(); // 記録した位置(2番目)の要素を削除
コレクションの要素を削除するとき、コレクションクラス自身のremoveメソッドを使うことが多いと思います。
ただし、これをループ内で行う場合は意図した挙動にならない場合があるので注意が必要です。
また、コレクションに対して拡張for文を使う場合にも注意が必要です。
2.ArrayListのremoveメソッドとIteratorのremoveメソッドの違いを体験する
さて、コレクションの要素をループ内で削除するとき、コレクションクラス自身が実装するremoveメソッドと、コレクションのイテレータが実装するremoveメソッドには、どのような挙動の違いが見られるのでしょうか。
ここでは例として「ArrayListの先頭から順に要素を1つずつ削除していき、ループを抜けるときにはすべての要素が削除されているプログラム」を作ります。
まずはArrayListを準備します。
List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
以降、従来のループを使う場合と拡張for文を使う場合のそれぞれについて確認していきます。
2-1. 従来のループを使う場合
test1：従来のループ内でArrayListのremoveを使う
public void test1(List<String> list){
for (int i = 0; i < list.size(); i++){
list.remove(i); // i番目の要素を削除・前詰め
}
}
上記はぱっと見うまくいきそうですがいかないひっかけの代表例です。
実行結果は次のようになります。
プログラム開始
0 1 2 3 4
A B C D E
[0:A]を削除しました。
0 1 2 3
B C D E
[1:C]を削除しました。
0 1 2
B D E
[2:E]を削除しました。
0 1
B D
プログラム終了
いくつかの要素が削除されずに残ってしまいました。
ArrayListの特徴のひとつは、要素を削除してできた隙間は後続の要素で前詰めされることです。
test1のループ変数 i は前詰めを一切考慮しておらず次の要素番号へと進んでしまうので、削除されない要素があるのです。この場合、意図通りに動かすには常に先頭の要素を削除するなど設計に工夫が必要です。
test2：従来のループ内でIteratorのremoveを使う
public void test2(List<String> list){
for (Iterator<String> iterator = list.iterator(); iterator.hasNext();){ // 次の要素が存在する限り、以下の処理を繰り返す
iterator.next(); // カーソルの現在位置を記録・カーソルを1つ次の位置に移動
iterator.remove(); // 記録した位置にある要素を削除・前詰め・カーソルを1つ前の位置に移動
}
}
実行結果は次のようになります。
プログラム開始
0 1 2 3 4
A B C D E
[0:A]を削除しました。
0 1 2 3
B C D E
[0:B]を削除しました。
0 1 2
C D E
[0:C]を削除しました。
0 1
D E
[0:D]を削除しました。
0
E
[0:E]を削除しました。
要素はありません。
プログラム終了
意図した通りに要素をすべて削除できました。
イテレータは、処理対象の要素の位置を"カーソル"を使って管理しています。
test2でイテレータ内部では
という制御を行っており、カーソルの位置は削除前後で変わりません。
そのため、要素を前詰めしながらでもtest1のように飛ばして進んでしまうことがないのです。
ArrayListが持つイテレータは、ArrayListの仕様に特化し、前詰めを考慮した処理を行えるようにカーソルの動きを制御してくれるのです。
2-2. 拡張for文を使う場合
test3：拡張for文内でArrayListのremoveを使う
public void test3(List<String> list){
for (String s : list){ // ループ2周目でConcurrentModificationException
list.remove(s); // 要素を削除・前詰め
}
}
実行結果は次のようになります。
プログラム開始
0 1 2 3 4
A B C D E
[0:A]を削除しました。
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)
(以下略)
ループ1回目の削除まで完了後、ConcurrentModificationExceptionという例外が発生してしまいました。
これは一体どのような例外なのでしょうか。これに関係する2つの仕様を確認します。
仕様1：拡張for文の内部構造は従来のfor文+イテレータである
拡張for文は、従来のループをより楽に書くために生まれた構文ですが、
実はコンパイル時に従来のfor文に変換されて実行されます。
ArrayList<String>型のコレクションを例とすると、およそ下記のように変換されます。
/* 変換前 */
for(String s : list){
// targetを使う処理
}
/* 変換後 */
for(Iterator<String> i = list.iterator(); i.hasNext();){
String s = i.next();
// targetを使う処理
}
参考：The Java Language Specification
変換後のコードではイテレータが使われています。
Iteratorのインスタンスを生成し、これのnext()メソッドを実行することによって次の要素を取り出しています。
仕様2：イテレータは他者によるコレクションの変更を許さない
このクラスのiteratorおよびlistIteratorメソッドによって返されるイテレータは、フェイルファストです。イテレータの作成後に、イテレータ自体のremoveまたはaddメソッド以外の方法でリストが構造的に変更されると、イテレータはConcurrentModificationExceptionをスローします。 このように、並行して変更が行われると、イテレータは、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。
引用：Oracle Java SE Document - クラスArrayList<E>
Iteratorの実装は、自分以外によってコレクションに変更を加えられていないかどうかを確認するために下記のような方法をとっています。
-
Iteratorの実装クラスは、ArrayListクラスの内部クラスとして定義されています。(コード)
-
Iteratorの実装クラスは、自身がもつメソッドによってコレクションに変更を加えた回数を記録するインスタンスフィールドexpectedModCountを持ちます。(コード)
-
ArrayListクラスもまた、自身がもつメソッドによってコレクションに変更を加えた回数を記録するインスタンスフィールドmodCountを持ちます。(コード)
-
Iteratorの実装クラスのremove()メソッドは、内部でArrayListクラスのremove()メソッドも呼び出す仕様のため、このメソッドが処理を終えた時にはexpectedModCountとmodCountの両方の回数がカウント(同期)されています。(コード)
-
Iteratorの実装クラスのnext()メソッドは、expectedModCountとmodCountが一致しているかを確認し、不一致の場合はConcurrentModificationException例外をスローする仕様です。(コード1) (コード2)
以上の仕様を踏まえ、
test3の拡張for文がコンパイルされて従来のfor文に変換された後のコードと動作をイメージしてみます。
public void test3_1(List<String> list){
// --------------------↓拡張for文のコンパイル後イメージ↓--------------------
for (Iterator<String> i = list.iterator(); i.hasNext();){
String s = i.next(); /* ループ2周目でConcurrentModificationException
ループ1周目でi以外によってコレクションに変更が加えられたため */
// --------------------↑拡張for文のコンパイル後イメージ↑--------------------
list.remove(s); // 要素を削除・前詰め・コレクションに変更を加えたことを記録
}
}
ループ1周目で、list.remove()でコレクションに変更が加えられ、ArrayListによる変更回数のみがカウントされることにより、イテレータiによる変更回数との間にズレが生じます。
そしてループ2周目の先頭で、i.next()メソッドが実行された時にこの不一致を認め、ConcurrentModificationExceptionをスローするのです。
test4：拡張for文内でIteratorのremoveを使う
public void test4(List<String> list){
for (String s : list){
Iterator iterator = list.iterator();
iterator.remove(); // 1周目でIllegalStateException
}
}
実行結果は次のようになります。
プログラム開始
0 1 2 3 4
A B C D E
Exception in thread "main" java.lang.IllegalStateException
at java.base/java.util.ArrayList$Itr.remove(ArrayList.java:980)
(以下略)
ループ1回目で、要素の削除前にIllegalStateExceptionという例外が発生してしまいました。
これは一体どのような例外なのでしょうか。これに関係するArrayListおよびそのイテレータの仕様を確認します。
仕様3：iterator.remove()する前にはiterator.next()が必須
Iteratorの実装クラスは、自身がもつnext()メソッドを呼び出した履歴を記録するインスタンスフィールドlastLetを持ちます。(コード)
Iteratorの実装クラスのremove()メソッドでは、初めにこのlastLetの値を確認し、呼び出し履歴が無い場合はIllegalStateException例外をスローする仕様です。(コード)
また、要素を削除するたびに全ての呼び出し履歴を消去します。(コード)
つまり、イテレータを使って要素を削除するときは、初めに少なくとも1回はnext()を呼んでいる必要があり、さらにこれを連続で行うときは、再びremove()を呼ぶまでに少なくとも1回は再びnext()を呼んでいる必要があります。
仕様4：iterator()は新しいイテレータを生成して返す
ArrayListクラスのiterator()メソッドは、呼ばれるたびにIteratorインスタンスをnewして返す仕様です。(コード)
例えば、下記のiterator1とiterator2には、listという同一のコレクションオブジェクトから取得した、別々のインスタンスが返っています。
var list = new ArrayList<String>();
var iterator1 = list.iterator();
var iterator2 = list.iterator();
以上の仕様をふまえ、
test4の拡張for文がコンパイルされて従来のfor文に変換された後のコードと動作をイメージしてみます。
public void test4_1(List<String> list){
// --------------------↓拡張for文のコンパイル後イメージ↓--------------------
for (Iterator<String> i = list.iterator(); i.hasNext();){
String s = i.next();
// --------------------↑拡張for文のコンパイル後イメージ↑--------------------
Iterator iterator = list.iterator(); // iとは異なるインスタンスが返っている
iterator.remove(); //iterator.next()の呼び出し履歴がないためIllegalStateException
}
}
iとiteratorはそれぞれ異なるインスタンスを参照しており、ループ1周目ではi.next()の呼び出し履歴はありますが、iterator.next()の呼び出し履歴はありません。
この状態でiterator.remove()が呼び出されるため、ループ1周目でIllegalStateException例外をスローするのです。
理論上、代わりにi.remove()を呼び出せば例外はスローされないはずですが、そもそもiに関する記述はコンパイル時にしか出現しないため、実際にこれを使うコードを記述することは不可能です。
test3とtest4から、拡張for文内ではコレクションに変更を加えることができないことが分かりました。
3. まとめ
「ループ内でArrayListの要素を先頭から順に全削除する」を4種類の方法で試みた結果をまとめます。
| ケース | ループ | メソッド | 評価 | 説明 |
|---|---|---|---|---|
| test1 | 従来型 | list.remove() | △ | 直感と異なる動きをする場合があるため注意が必要。 |
| test2 | 従来型 | iterator.remove() | ○ | イテレータがArrayListの特徴を加味した制御を行ってくれるので直感通りの動きが可能になる。 |
| test3 | 拡張for文 | list.remove() | × | 拡張for文ではループに使うコレクションに変更を加えることができない。 |
| test4 | 拡張for文 | iterator.remove() | × | 拡張for文ではループに使うコレクションに変更を加えることができない。 |
※上表では、listはArrayList<E>のオブジェクトを表し、iteratorはlist.iterator()で取得したIterator<E>のオブジェクトを表しています。
ループ内でArrayListの要素を削除するとき、test2の記述方法が最も楽で安全だということが分かりました。
public void test2(List<String> list){
for (Iterator<String> iterator = list.iterator(); iterator.hasNext();){ // 次の要素が存在する限り、以下の処理を繰り返す
iterator.next(); // カーソルの現在位置を記録・カーソルを1つ次の位置に移動
iterator.remove(); // 記録した位置にある要素を削除・前詰め・カーソルを1つ前の位置に移動
}
}
ArrayList以外のCollection<E>を実装するコレクションクラスでも、各クラスの特徴に合わせてイテレータの細かい実装が異なっていそうなので、仕様やソースコードを確認してみるのは面白そうです。