Remover elementos da coleção enquanto itera

215

AFAIK, existem duas abordagens:

  1. Iterar uma cópia da coleção
  2. Use o iterador da coleção real

Por exemplo,

List<Foo> fooListCopy = new ArrayList<Foo>(fooList);
for(Foo foo : fooListCopy){
    // modify actual fooList
}

e

Iterator<Foo> itr = fooList.iterator();
while(itr.hasNext()){
    // modify actual fooList using itr.remove()
}

Existem razões para preferir uma abordagem à outra (por exemplo, preferindo a primeira abordagem pelo simples motivo de legibilidade)?

user1329572
fonte
1
Apenas curioso, por que você cria uma cópia do tolo em vez de apenas repetir o tolo no primeiro exemplo?
Haz
@ Haz, então eu só tenho que fazer um loop uma vez.
User1329572
15
Nota: prefira 'for' over 'while' também com iteradores para limitar o escopo da variável: for (Iterador <Foo> itr = fooList.iterator (); itr.hasNext ();) {}
Puce
Eu não sabia que whiletinha regras de escopo diferentes do quefor
Alexander Mills
Em uma situação mais complexa, você pode ter um caso em que fooListé uma variável de instância e chamar um método durante o loop que acaba chamando outro método na mesma classe que o faz fooList.remove(obj). Já vi isso acontecer. Nesse caso, copiar a lista é mais seguro.
Dave Griffiths

Respostas:

416

Deixe-me dar alguns exemplos com algumas alternativas para evitar a ConcurrentModificationException.

Suponha que tenhamos a seguinte coleção de livros

List<Book> books = new ArrayList<Book>();
books.add(new Book(new ISBN("0-201-63361-2")));
books.add(new Book(new ISBN("0-201-63361-3")));
books.add(new Book(new ISBN("0-201-63361-4")));

Coletar e remover

A primeira técnica consiste em coletar todos os objetos que queremos excluir (por exemplo, usando um loop for aprimorado) e depois de concluir a iteração, removemos todos os objetos encontrados.

ISBN isbn = new ISBN("0-201-63361-2");
List<Book> found = new ArrayList<Book>();
for(Book book : books){
    if(book.getIsbn().equals(isbn)){
        found.add(book);
    }
}
books.removeAll(found);

Isso supõe que a operação que você deseja executar seja "excluir".

Se você deseja "adicionar", essa abordagem também funcionaria, mas eu presumiria que você iteraria sobre uma coleção diferente para determinar quais elementos você deseja adicionar a uma segunda coleção e, em seguida, emitiria um addAllmétodo no final.

Usando ListIterator

Se você estiver trabalhando com listas, outra técnica consiste em usar um ListIteratorque tenha suporte para remoção e adição de itens durante a própria iteração.

ListIterator<Book> iter = books.listIterator();
while(iter.hasNext()){
    if(iter.next().getIsbn().equals(isbn)){
        iter.remove();
    }
}

Novamente, usei o método "remove" no exemplo acima, que é o que sua pergunta parecia implicar, mas você também pode usar o addmétodo para adicionar novos elementos durante a iteração.

Usando JDK> = 8

Para aqueles que trabalham com o Java 8 ou versões superiores, existem algumas outras técnicas que você pode usar para tirar proveito disso.

Você pode usar o novo removeIfmétodo na Collectionclasse base:

ISBN other = new ISBN("0-201-63361-2");
books.removeIf(b -> b.getIsbn().equals(other));

Ou use a nova API de fluxo:

ISBN other = new ISBN("0-201-63361-2");
List<Book> filtered = books.stream()
                           .filter(b -> b.getIsbn().equals(other))
                           .collect(Collectors.toList());

Neste último caso, para filtrar elementos de uma coleção, você reatribui a referência original à coleção filtrada (ou seja books = filtered) ou usou a coleção filtrada aos removeAllelementos encontrados da coleção original (ou seja books.removeAll(filtered)).

Usar sublista ou subconjunto

Existem outras alternativas também. Se a lista estiver classificada e você desejar remover elementos consecutivos, poderá criar uma sub-lista e desmarcá-la:

books.subList(0,5).clear();

Como a sub-lista é apoiada pela lista original, essa seria uma maneira eficiente de remover essa sub-coleção de elementos.

Algo semelhante poderia ser alcançado com conjuntos classificados usando o NavigableSet.subSetmétodo, ou qualquer um dos métodos de corte oferecidos lá.

Considerações:

Que método usado pode depender do que você pretende fazer

  • A coleta e a removeAltécnica funcionam com qualquer coleção (coleção, lista, conjunto etc.).
  • A ListIteratortécnica, obviamente, só funciona com listas, desde que os seus dados ListIteratorofertas de implementação apoio para acções adicionar e remover.
  • A Iteratorabordagem funcionaria com qualquer tipo de coleção, mas suporta apenas operações de remoção.
  • Com a abordagem ListIterator/ Iterator, a vantagem óbvia é não ter que copiar nada, pois removemos à medida que iteramos. Então, isso é muito eficiente.
  • O exemplo de fluxos do JDK 8 na verdade não removeu nada, mas procurou os elementos desejados e, em seguida, substituímos a referência de coleção original pelo novo e deixamos o antigo ser coletado como lixo. Portanto, iteramos apenas uma vez sobre a coleção e isso seria eficiente.
  • Na coleta e removeAllabordagem, a desvantagem é que precisamos iterar duas vezes. Primeiro, iteramos no loop foor procurando um objeto que atenda aos nossos critérios de remoção e, uma vez encontrado, pedimos para removê-lo da coleção original, o que implicaria um segundo trabalho de iteração para procurar esse item para remova.
  • Eu acho que vale a pena mencionar que o método remove da Iteratorinterface está marcado como "opcional" nos Javadocs, o que significa que pode haver Iteratorimplementações que serão lançadas UnsupportedOperationExceptionse invocarmos o método remove. Como tal, eu diria que essa abordagem é menos segura do que outras, se não podemos garantir o suporte do iterador para a remoção de elementos.
Edwin Dalorzo
fonte
Bravo! este é o guia definitivo.
Magno C
Esta é uma resposta perfeita! Obrigado.
21718 Wilhelm
7
No seu parágrafo sobre o JDK8 Streams, você menciona removeAll(filtered). Um atalho para isso seriaremoveIf(b -> b.getIsbn().equals(other))
ifloop 27/03
Qual é a diferença entre Iterator e ListIterator?
Alexander Mills
Não considerei remover, mas foi a resposta para minhas orações. Obrigado!
Akabelle 16/10/19
15

No Java 8, há outra abordagem. Coleção # removeIf

por exemplo:

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

list.removeIf(i -> i > 2);
Santhosh
fonte
13

Existem razões para preferir uma abordagem à outra

A primeira abordagem funcionará, mas possui a sobrecarga óbvia de copiar a lista.

A segunda abordagem não funcionará porque muitos contêineres não permitem modificações durante a iteração. Isso incluiArrayList .

Se a única modificação é remover o elemento atual, você pode fazer o segundo trabalho de abordagem usando itr.remove()(ou seja, usar o iterador 's remove()método, não o recipiente ' s). Esse seria o meu método preferido para iteradores compatíveis remove().

NPE
fonte
Opa, desculpe ... está implícito que eu usaria o método de remoção do iterador, não o contêiner. E quanto custa a cópia da lista cria? Não pode ser muito e, como o escopo é de um método, ele deve ser coletado rapidamente. Veja edit ..
user1329572
1
@aix Acho que vale a pena mencionar que o método remove da Iteratorinterface está marcado como opcional nos Javadocs, o que significa que pode haver implementações do Iterator que possam ser lançadas UnsupportedOperationException. Como tal, eu diria que essa abordagem é menos segura que a primeira. Dependendo das implementações que se pretende usar, a primeira abordagem pode ser mais adequada.
Edwin Dalorzo #
O @ EdwinDalorzo remove()na própria coleção original também pode lançar UnsupportedOperationException: docs.oracle.com/javase/7/docs/api/java/util/… . Infelizmente, as interfaces de contêiner Java são definidas como extremamente não confiáveis ​​(derrotando honestamente o ponto da interface). Se você não souber a implementação exata que será usada no tempo de execução, é melhor fazer as coisas de maneira imutável - por exemplo, use a API Java 8+ Streams para filtrar os elementos e coletá-los em um novo contêiner. substituir completamente o antigo por ele.
Matthew Leia
5

Apenas a segunda abordagem funcionará. Você pode modificar a coleção durante a iteração usando iterator.remove()apenas. Todas as outras tentativas causarão ConcurrentModificationException.

AlexR
fonte
2
A primeira tentativa itera uma cópia, o que significa que ele pode modificar o original.
Colin D
3

Favorito antigo do temporizador (ainda funciona):

List<String> list;

for(int i = list.size() - 1; i >= 0; --i) 
{
        if(list.get(i).contains("bad"))
        {
                list.remove(i);
        }
}
Shebla Tsama
fonte
1

Você não pode fazer o segundo, porque mesmo se você usar o remove()método no Iterator , receberá uma exceção .

Pessoalmente, eu preferiria o primeiro para todas as Collectioninstâncias, apesar do escutar adicional de criar o novo Collection, acho menos propenso a erros durante a edição por outros desenvolvedores. Em algumas implementações de coleção, o Iterator remove()é suportado; em outros, não. Você pode ler mais nos documentos do Iterator .

A terceira alternativa é criar uma nova Collectioniteração sobre o original e adicionar todos os membros do primeiro Collectionao segundo Collectionque não estão prontos para exclusão. Dependendo do tamanho Collectione do número de exclusões, isso pode economizar significativamente na memória, quando comparado à primeira abordagem.

Jon
fonte
0

Eu escolheria o segundo, pois você não precisa fazer uma cópia da memória e o Iterator funciona mais rápido. Então você economiza memória e tempo.

Calin Andrei
fonte
"O iterador funciona mais rápido ". Algo para apoiar esta reivindicação? Além disso, a pegada de memória de fazer uma cópia de uma lista é muito trivial, especialmente porque ela terá o escopo definido dentro de um método e o lixo será coletado quase imediatamente.
User1329572
1
Na primeira abordagem, a desvantagem é que precisamos iterar duas vezes. Nós iteramos no loop foor procurando por um elemento e, uma vez encontrado, pedimos para removê-lo da lista original, o que implicaria um segundo trabalho de iteração para procurar esse item. Isso apoiaria a alegação de que, pelo menos nesse caso, a abordagem do iterador deve ser mais rápida. Temos que considerar que apenas o espaço estrutural da coleção é aquele que está sendo criado, os objetos dentro das coleções não estão sendo copiados. Ambas as coleções manteriam referências aos mesmos objetos. Quando o GC acontece, não podemos dizer !!!
Edwin Dalorzo
-2

por que não isso?

for( int i = 0; i < Foo.size(); i++ )
{
   if( Foo.get(i).equals( some test ) )
   {
      Foo.remove(i);
   }
}

E se for um mapa, não uma lista, você pode usar keyset ()

Drake Clarris
fonte
4
Essa abordagem tem muitas grandes desvantagens. Primeiro, sempre que você remove um elemento, os índices são reorganizados. Portanto, se você remover o elemento 0, o elemento 1 se tornará o novo elemento 0. Se você for fazer isso, pelo menos faça-o ao contrário para evitar esse problema. Segundo, nem todas as implementações de Lista oferecem acesso direto aos elementos (como ArrayList). Em uma LinkedList, isso seria tremendamente ineficiente, pois toda vez que você emitir um, get(i)você precisará visitar todos os nós até chegar i.
Edwin Dalorzo 03/03/12
Nunca considerei isso, pois normalmente o usava para remover um único item que estava procurando. Bom saber.
Drake Clarris
4
Estou atrasado para a festa, mas certamente no código de bloco if depois que Foo.remove(i);você deve fazer i--;?
Bertie Wheen
becouse é grampeado
Jack