Java Iterator

Toda coleção do Java pode ser percorrida, um elemento por vez, por um Iterator (iterador): um "cursor" que sabe onde está e qual é o próximo. Você já usa iteradores sem saber, porque o for-each é feito com eles. Nesta aula você vai usá-los diretamente, e vai descobrir por que remover elementos dentro de um for-each quebra o programa com ConcurrentModificationException, e como fazer isso do jeito certo.

Você vai aprender
  • O que é um Iterator e os seus três métodos: hasNext, next e remove.
  • Como o for-each usa um iterador por baixo dos panos.
  • Por que remover dentro de um for-each dá ConcurrentModificationException (e às vezes, pior, não dá).
  • As três formas certas de remover enquanto percorre: Iterator.remove, removeIf e o laço de trás para a frente.
  • O mesmo problema (e as mesmas soluções) em mapas.

A ideia: o dedo na lista de chamada

Quando a Ana faz a chamada, ela põe o dedo antes do primeiro nome e repete: "tem mais alguém?"; se tem, desce o dedo e lê o nome. Um iterador é exatamente esse dedo:

MétodoTraduçãoNa chamada
hasNext()"tem próximo?""Tem mais alguém abaixo do meu dedo?" Devolve true ou false, sem mexer o dedo.
next()"próximo"Desce o dedo um nome e devolve esse nome.
remove()"remover"Risca da lista o nome que o dedo acabou de ler.

Percorrer com um Iterator

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> alunos = new ArrayList<>(List.of("Ana", "Bruno", "Carla"));

        Iterator<String> it = alunos.iterator();
        while (it.hasNext()) {
            String aluno = it.next();
            System.out.println("Chamando " + aluno);
        }
        System.out.println("Ainda tem? " + it.hasNext());
    }
}
import java.util.Iterator;
O Iterator também mora em java.util.
Iterator<String> it = alunos.iterator();
Pede à lista um iterador novo. O dedo começa antes do primeiro elemento. O <String> diz que o next() vai devolver String.
while (it.hasNext())
"Enquanto houver um próximo…" (veja while).
String aluno = it.next();
Avança e pega o elemento. Chame next() uma vez por volta: cada chamada avança o dedo.
$ javac Main.java
$ java Main
Chamando Ana
Chamando Bruno
Chamando Carla
Ainda tem? false                « o dedo chegou ao fim

Esse mesmo código funciona com qualquer coleção: troque a lista por um HashSet ou um TreeSet e nada mais muda. É por isso que o iterador existe: um jeito único de percorrer coleções que guardam os dados de formas muito diferentes (um array, nós encadeados, uma árvore…). Conjuntos não têm get(i), mas todos têm iterator().

Um iterador só anda para a frente e só serve uma vez. Para percorrer de novo, peça outro com alunos.iterator().

O for-each é um iterador disfarçado

Quando você escreve um for-each numa coleção, o compilador o transforma no while com iterador acima. Estes dois trechos são equivalentes:

for (String aluno : alunos) {            Iterator<String> it = alunos.iterator();
    System.out.println(aluno);           while (it.hasNext()) {
}                                            String aluno = it.next();
                                             System.out.println(aluno);
                                         }

Qualquer classe que tenha o método iterator() (ou seja, que implemente a interface Iterable) pode ser usada num for-each. Guarde esse detalhe: ele explica o erro da próxima seção.

Pediu um next() a mais: NoSuchElementException

Este código tem um erro de propósito.

        List<String> alunos = new ArrayList<>(List.of("Ana", "Bruno"));
        Iterator<String> it = alunos.iterator();
        System.out.println(it.next());
        System.out.println(it.next());
        System.out.println(it.next());

$ java Main
Ana
Bruno
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1053)
	at Main.main(Main.java:11)

O que quer dizer: "não há tal elemento": o terceiro next() passou do fim. (ArrayList$Itr é o nome da classe do iterador da ArrayList: Itr é uma classe interna dela.)

Como consertar: sempre pergunte hasNext() antes de cada next().

O problema: remover dentro de um for-each

A Ana quer tirar da lista as notas abaixo de 5. O jeito que parece óbvio:

Este código tem um erro de propósito.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> notas = new ArrayList<>(List.of(8, 3, 9, 4, 7));
        for (Integer n : notas) {
            if (n < 5) {
                notas.remove(n);
            }
        }
        System.out.println(notas);
    }
}

$ javac Main.java
$ java Main
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1096)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1050)
	at Main.main(Main.java:7)

ConcurrentModificationException quer dizer "exceção de modificação concorrente": a lista foi modificada ao mesmo tempo em que era percorrida. Leia a pilha de baixo para cima:

  1. Main.main(Main.java:7): a linha 7 é a do for. O erro não aconteceu no remove (linha 9), mas na volta seguinte do laço.
  2. ArrayList$Itr.next: o for-each chamou o next() do iterador escondido.
  3. checkForComodification: "verificar se houve modificação". O iterador percebeu que a lista mudou sem ele saber, e parou.

Por que o iterador reclama? Lembre do dedo na lista de chamada. Se alguém risca um nome pelas costas da Ana, os nomes de baixo sobem uma linha e o dedo dela fica apontando para o lugar errado: ela pularia alguém sem perceber. Para evitar esse bug silencioso, a ArrayList conta quantas vezes foi modificada, e o iterador confere essa contagem a cada next(). Se mudou por fora, ele lança a exceção (o nome técnico desse comportamento é fail-fast, "falhar rápido").

Repare: notas.remove(n) aqui remove pelo valor, porque n é um Integer (e não um int); veja a pegadinha do remove. O problema não está no remove, e sim em quem remove: a lista, e não o iterador.

Pior que a exceção: quando ela não acontece

Com outros dados, o mesmo código pode terminar sem erro, e errado. Com a lista [8, 9, 3, 4]:

$ java Main
[8, 9, 4]                « o 4 deveria ter saído!

O 3 era o penúltimo. Ao removê-lo, a lista ficou com 3 elementos, e o for-each, que já tinha passado por 3, achou que tinha terminado: nem chegou a chamar o next() que faria a verificação. O 4 nunca foi examinado. Por isso a regra é absoluta: nunca altere uma coleção dentro de um for-each sobre ela, nem quando "funciona".

Solução 1: remover pelo próprio iterador

Se é o dedo que risca o nome, ele sabe o que aconteceu e se ajusta. Para isso, escreva o laço com o iterador explícito e chame it.remove():

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> notas = new ArrayList<>(List.of(8, 3, 9, 4, 7));
        Iterator<Integer> it = notas.iterator();
        while (it.hasNext()) {
            int n = it.next();
            if (n < 5) {
                it.remove();
            }
        }
        System.out.println(notas);
    }
}

$ javac Main.java
$ java Main
[8, 9, 7]
int n = it.next();
Lê o próximo. Aqui guardamos num int (o Java desembrulha o Integer).
it.remove();
Remove o último elemento que o next() devolveu. Não recebe argumento: o iterador já sabe qual é.
Regras do it.remove()

Ele só pode ser chamado depois de um next(), e uma vez por next(). Chamar antes de qualquer next(), ou duas vezes seguidas, dá IllegalStateException (veja Quando dá errado).

Missão: o programa quer tirar da turma quem tem nome começando com "B", mas quebra com ConcurrentModificationException. Reescreva o laço com um Iterator e it.remove(). A saída deve ser [Ana, Carla].

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> alunos = new ArrayList<>(List.of("Ana", "Bruno", "Beatriz", "Carla"));
        for (String a : alunos) {
            if (a.startsWith("B")) {
                alunos.remove(a);
            }
        }
        System.out.println(alunos);
    }
}

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> alunos = new ArrayList<>(List.of("Ana", "Bruno", "Beatriz", "Carla"));
        Iterator<String> it = alunos.iterator();
        while (it.hasNext()) {
            String a = it.next();
            if (a.startsWith("B")) {
                it.remove();
            }
        }
        System.out.println(alunos);
    }
}

Solução 2: removeIf

Desde o Java 8, toda coleção tem removeIf ("remover se"): você diz a condição, e a coleção remove todos os elementos que a satisfazem, do jeito seguro. Na prática, é a forma mais usada hoje:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> notas = new ArrayList<>(List.of(8, 3, 9, 4, 7));
        boolean mudou = notas.removeIf(n -> n < 5);
        System.out.println(mudou + " " + notas);
    }
}

$ javac Main.java
$ java Main
true [8, 9, 7]           « true = alguma coisa foi removida
n -> n < 5
Uma lambda: uma pequena função que recebe cada elemento (n) e responde true ("remova") ou false ("mantenha"). Lê-se "dado n, n menor que 5".
boolean mudou
removeIf devolve true se removeu pelo menos um.

Uma linha só, impossível de errar o índice e, por dentro, mais rápido que remover um por um numa ArrayList. Use o iterador explícito quando, além de remover, você precisa fazer outras coisas no mesmo laço (mostrar quem saiu, contar, etc.).

Solução 3: laço com índice, de trás para a frente

Em listas, dá para usar um for com índice. Mas atenção à direção. Para a frente, ele erra sem avisar:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> notas = new ArrayList<>(List.of(8, 3, 4, 9));
        for (int i = 0; i < notas.size(); i++) {
            if (notas.get(i) < 5) {
                notas.remove(i);
            }
        }
        System.out.println("para a frente: " + notas);

        List<Integer> notas2 = new ArrayList<>(List.of(8, 3, 4, 9));
        for (int i = notas2.size() - 1; i >= 0; i--) {
            if (notas2.get(i) < 5) {
                notas2.remove(i);
            }
        }
        System.out.println("de trás para a frente: " + notas2);
    }
}

$ javac Main.java
$ java Main
para a frente: [8, 4, 9]              « o 4 escapou
de trás para a frente: [8, 9]         « certo

Para a frente: com i = 1, o 3 sai e o 4 sobe para a posição 1. Aí o i++ pula para 2, e o 4 nunca é examinado. De trás para a frente, os elementos que se movem são os que já foram examinados, então ninguém escapa. (Aqui notas.remove(i) é por posição, porque i é int.)

Qual usar?

FormaQuando usar
colecao.removeIf(x -> condição)O padrão: só remover quem satisfaz uma condição. Funciona em listas, conjuntos e nas visões de mapas.
Iterator + it.remove()Remover e fazer outras coisas no mesmo laço (mostrar, contar, decidir com várias regras).
for com índice, de trás para a frenteListas, quando você precisa da posição. Nunca para a frente.
Criar uma coleção nova só com quem ficaQuando a original não pode mudar (por exemplo, com streams: filter).
for-each + colecao.removeNunca.

O mesmo problema em mapas

Mapas também são percorridos por iteradores (das visões keySet, values e entrySet), e o problema se repete. A Ana quer tirar do estoque os produtos zerados:

Este código tem um erro de propósito.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> estoque = new HashMap<>();
        estoque.put("maçã", 12);
        estoque.put("uva", 0);
        estoque.put("banana", 30);
        estoque.put("kiwi", 0);
        for (String produto : estoque.keySet()) {
            if (estoque.get(produto) == 0) {
                estoque.remove(produto);
            }
        }
        System.out.println(estoque);
    }
}

$ javac Main.java
$ java Main
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1606)
	at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1629)
	at Main.main(Main.java:11)

O erro é o mesmo, agora vindo do iterador de chaves do HashMap (KeyIterator). A solução mais curta é o removeIf numa das visões. Remover da visão remove do mapa:

        estoque.values().removeIf(qtd -> qtd == 0);                  // pelo valor
        estoque.keySet().removeIf(produto -> produto.startsWith("k")); // pela chave
        estoque.entrySet().removeIf(par -> par.getValue() == 0);      // pelos dois

Com a primeira linha, num TreeMap (para a saída sair em ordem):

$ java Main
{banana=30, maçã=12}

Quando dá errado

ConcurrentModificationException 
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1096)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1050)
	at Main.main(Main.java:7)

O que quer dizer: a coleção foi alterada (com add ou remove dela mesma) enquanto um iterador, quase sempre o de um for-each, a percorria. A linha apontada é a do for, não a do remove.

Como consertar: removeIf, it.remove() ou laço de trás para a frente. Para acrescentar durante o percurso, junte os novos numa lista separada e faça addAll depois do laço.

Apesar do nome "concorrente", isso não tem nada a ver com threads: acontece com um programa de uma linha de execução só.

IllegalStateException: remove() antes do next()

Este código tem um erro de propósito.

        List<String> alunos = new ArrayList<>(List.of("Ana", "Bruno"));
        Iterator<String> it = alunos.iterator();
        it.remove();

$ java Main
Exception in thread "main" java.lang.IllegalStateException
	at java.base/java.util.ArrayList$Itr.remove(ArrayList.java:1063)
	at Main.main(Main.java:9)

O que quer dizer: "estado ilegal": o iterador ainda não leu ninguém, então não sabe o que remover. O mesmo acontece se você chamar it.remove() duas vezes depois do mesmo next().

Como consertar: um it.remove() por it.next(), sempre depois dele.

Não deu erro, mas sobrou um elemento que devia ter saído

O que aconteceu: ou você removeu dentro de um for-each e o elemento removido era o penúltimo, ou usou um for com índice para a frente. Nos dois casos, um elemento foi pulado.

Como consertar: troque por removeIf.

Referência

CódigoO que faz
Iterator<T> it = colecao.iterator();Cria um iterador, antes do primeiro elemento
it.hasNext()Tem próximo? (não avança)
it.next()Avança e devolve; passou do fim: NoSuchElementException
it.remove()Remove o último devolvido por next(); fora de hora: IllegalStateException
colecao.removeIf(x -> cond)Remove todos que satisfazem cond; devolve true se removeu
mapa.values().removeIf(…), keySet(), entrySet()Remove pares do mapa pelo valor, pela chave ou pelos dois
list.listIterator()Iterador de lista: também anda para trás (hasPrevious/previous) e troca (set)
Iterable<T>Interface de quem tem iterator(): pode ir num for-each

Exercícios

1. Tem mais?

Complete a condição do laço:

while (it.) { String s = it.next(); … }

2. Remover com segurança

Complete para remover da lista nomes todos os nomes vazios:

nomes.;

3. Em que linha a ConcurrentModificationException de um for-each é apontada?

4. O que it.remove() remove?

5. Num for (int i = 0; i < l.size(); i++) que remove com l.remove(i), o que pode acontecer?

Missão final: tire do estoque os produtos com quantidade 0, usando removeIf numa das visões do mapa (values() ou entrySet()). A saída deve ser {banana=30, maçã=12}.

import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> estoque = new TreeMap<>();
        estoque.put("maçã", 12);
        estoque.put("uva", 0);
        estoque.put("banana", 30);
        estoque.put("kiwi", 0);

        // remova os zerados

        System.out.println(estoque);
    }
}

import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> estoque = new TreeMap<>();
        estoque.put("maçã", 12);
        estoque.put("uva", 0);
        estoque.put("banana", 30);
        estoque.put("kiwi", 0);

        estoque.values().removeIf(qtd -> qtd == 0);

        System.out.println(estoque);
    }
}

Resumo

  • Um Iterator percorre qualquer coleção: hasNext() pergunta, next() avança e devolve, remove() tira o último lido.
  • O for-each usa um iterador escondido.
  • Alterar a coleção dentro do for-each dá ConcurrentModificationException, ou, pior, pula elementos sem avisar.
  • Para remover enquanto percorre: removeIf(condição) (o padrão), it.remove(), ou for com índice de trás para a frente.
  • Em mapas: values().removeIf, keySet().removeIf, entrySet().removeIf.
  • next() além do fim: NoSuchElementException; remove() fora de hora: IllegalStateException.

Próxima aula: A Classe Collections, a caixa de ferramentas com sort, shuffle, max e companhia.