Eliminar elementos de la colección mientras itera

215

AFAIK, hay dos enfoques:

  1. Iterar sobre una copia de la colección.
  2. Usa el iterador de la colección real

Por ejemplo,

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

y

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

¿Hay alguna razón para preferir un enfoque sobre el otro (por ejemplo, preferir el primer enfoque por la simple razón de la legibilidad)?

usuario1329572
fuente
1
Solo por curiosidad, ¿por qué creas una copia de tonto en lugar de simplemente pasar por tonto en el primer ejemplo?
Haz
@Haz, así que solo tengo que hacer un bucle una vez.
user1329572
15
Nota: prefiera 'for' over 'while' también con iteradores para limitar el alcance de la variable: for (Iterator <Foo> itr = fooList.iterator (); itr.hasNext ();) {}
Puce
No sabía que whiletenía reglas de alcance diferentes quefor
Alexander Mills
En una situación más compleja, es posible que tenga un caso donde fooListes una variable de instancia y llama a un método durante el ciclo que termina llamando a otro método en la misma clase que lo hace fooList.remove(obj). He visto que esto suceda. En cuyo caso, copiar la lista es lo más seguro.
Dave Griffiths

Respuestas:

418

Permítanme dar algunos ejemplos con algunas alternativas para evitar a ConcurrentModificationException.

Supongamos que tenemos la siguiente colección de libros.

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")));

Recoger y quitar

La primera técnica consiste en recopilar todos los objetos que queremos eliminar (por ejemplo, utilizando un bucle for mejorado) y después de terminar de iterar, eliminamos todos los 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);

Esto supone que la operación que desea hacer es "eliminar".

Si desea "agregar" este enfoque también funcionaría, pero supongo que iteraría sobre una colección diferente para determinar qué elementos desea agregar a una segunda colección y luego emitir un addAllmétodo al final.

Usando ListIterator

Si está trabajando con listas, otra técnica consiste en utilizar una ListIteratorque tenga soporte para eliminar y agregar elementos durante la iteración misma.

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

Nuevamente, usé el método "eliminar" en el ejemplo anterior, que es lo que su pregunta parecía implicar, pero también puede usar su addmétodo para agregar nuevos elementos durante la iteración.

Usando JDK> = 8

Para aquellos que trabajan con Java 8 o versiones superiores, hay un par de otras técnicas que podría utilizar para aprovecharlo.

Podría usar el nuevo removeIfmétodo en la Collectionclase base:

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

O use la nueva API de transmisión:

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

En este último caso, para filtrar elementos de una colección, reasigne la referencia original a la colección filtrada (es decir books = filtered) o utilice la colección filtrada a removeAlllos elementos encontrados de la colección original (es decir books.removeAll(filtered)).

Usar sublista o subconjunto

También hay otras alternativas. Si la lista está ordenada y desea eliminar elementos consecutivos, puede crear una sublista y luego borrarla:

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

Como la sublista está respaldada por la lista original, esta sería una forma eficiente de eliminar esta subcolección de elementos.

Algo similar podría lograrse con conjuntos ordenados utilizando el NavigableSet.subSetmétodo, o cualquiera de los métodos de corte que se ofrecen allí.

Consideraciones:

El método que utilice puede depender de lo que tenga intención de hacer.

  • La colección y la removeAltécnica funcionan con cualquier Colección (Colección, Lista, Conjunto, etc.).
  • La ListIteratortécnica obviamente solo funciona con listas, siempre que su ListIteratorimplementación dada ofrezca soporte para operaciones de agregar y quitar.
  • El Iteratorenfoque funcionaría con cualquier tipo de colección, pero solo admite operaciones de eliminación.
  • Con el enfoque ListIterator/ Iteratorla ventaja obvia es no tener que copiar nada, ya que eliminamos a medida que iteramos. Entonces, esto es muy eficiente.
  • El ejemplo de secuencias JDK 8 en realidad no eliminó nada, sino que buscó los elementos deseados, y luego reemplazamos la referencia de colección original con la nueva, y dejamos que se recolectara la basura. Entonces, iteramos solo una vez sobre la colección y eso sería eficiente.
  • En la recopilación y el removeAllenfoque, la desventaja es que tenemos que repetir dos veces. Primero iteramos en el bucle de búsqueda buscando un objeto que coincida con nuestros criterios de eliminación, y una vez que lo hemos encontrado, pedimos eliminarlo de la colección original, lo que implicaría un segundo trabajo de iteración para buscar este artículo para eliminarlo
  • Creo que vale la pena mencionar que el método remove de la Iteratorinterfaz está marcado como "opcional" en Javadocs, lo que significa que podría haber Iteratorimplementaciones que arrojen UnsupportedOperationExceptionsi invocamos el método remove. Como tal, diría que este enfoque es menos seguro que otros si no podemos garantizar el soporte del iterador para la eliminación de elementos.
Edwin Dalorzo
fuente
¡Bravo! Esta es la guía definitiva.
Magno C
Esta es una respuesta perfecta! Gracias.
Wilhelm
77
En su párrafo sobre las secuencias JDK8 que menciona removeAll(filtered). Un acceso directo para que seríaremoveIf(b -> b.getIsbn().equals(other))
ifloop
¿Cuál es la diferencia entre Iterator y ListIterator?
Alexander Mills
No he considerado eliminar si, pero fue la respuesta a mis oraciones. ¡Gracias!
Akabelle
15

En Java 8, hay otro enfoque. Colección # removeIf

p.ej:

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

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

¿Hay alguna razón para preferir un enfoque sobre el otro?

El primer enfoque funcionará, pero tiene la sobrecarga obvia de copiar la lista.

El segundo enfoque no funcionará porque muchos contenedores no permiten modificaciones durante la iteración. Esto incluyeArrayList .

Si la única modificación es eliminar el elemento actual, puede hacer que el segundo enfoque de trabajo mediante el uso itr.remove()(es decir, utilizar el iterador 's remove()método, no el contenedor ' s). Este sería mi método preferido para iteradores compatibles remove().

NPE
fuente
Oops, lo siento ... está implícito que usaría el método remove del iterador, no el contenedor. ¿Y cuántos gastos generales genera la copia de la lista? No puede ser mucho y, dado que está enfocado a un método, debería recolectarse basura con bastante rapidez. Ver edición ..
user1329572
1
@aix Creo que vale la pena mencionar que el método de eliminación de la Iteratorinterfaz está marcado como opcional en Javadocs, lo que significa que podría haber implementaciones de Iterator que podrían arrojarse UnsupportedOperationException. Como tal, diría que este enfoque es menos seguro que el primero. Dependiendo de las implementaciones destinadas a ser utilizadas, el primer enfoque podría ser más adecuado.
Edwin Dalorzo
@EdwinDalorzo remove()en la colección original también puede lanzar UnsupportedOperationException: docs.oracle.com/javase/7/docs/api/java/util/… . Lamentablemente, las interfaces de contenedor Java se definen como extremadamente poco confiables (honestamente, derrotando el punto de la interfaz). Si no conoce la implementación exacta que se utilizará en tiempo de ejecución, es mejor hacer las cosas de una manera inmutable; por ejemplo, use la API Java 8+ Streams para filtrar los elementos y recopilarlos en un nuevo contenedor, luego Reemplace completamente el viejo con él.
Matthew leyó el
5

Solo el segundo enfoque funcionará. Puede modificar la colección durante la iteración usando iterator.remove()solo. Todos los demás intentos causarán ConcurrentModificationException.

AlexR
fuente
2
El primer intento itera en una copia, lo que significa que puede modificar el original.
Colin D
3

Antiguo temporizador favorito (todavía funciona):

List<String> list;

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

No puede hacer el segundo, porque incluso si usa el remove()método en Iterator , obtendrá una excepción .

Personalmente, preferiría el primero para todas las Collectioninstancias, a pesar de la escucha adicional de crear el nuevo Collection, encuentro que es menos propenso a errores durante la edición por otros desarrolladores. En algunas implementaciones de Collection, Iterator remove()es compatible, en otras no. Puedes leer más en los documentos de Iterator .

La tercera alternativa es crear una nueva Collection, iterar sobre la original y agregar todos los miembros de la primera Collectiona la segunda Collectionque no estén disponibles para su eliminación. Dependiendo del tamaño Collectiony la cantidad de eliminaciones, esto podría ahorrar significativamente en memoria, en comparación con el primer enfoque.

Jon
fuente
0

Elegiría el segundo ya que no tienes que hacer una copia de la memoria y el iterador funciona más rápido. Así ahorras memoria y tiempo.

Calin Andrei
fuente
" Iterator funciona más rápido ". ¿Algo para respaldar esta afirmación? Además, la huella de memoria de hacer una copia de una lista es muy trivial, especialmente porque se analizará dentro de un método y la basura se recolectará casi de inmediato.
user1329572
1
En el primer enfoque, la desventaja es que tenemos que repetir dos veces. Repetimos en el bucle de búsqueda buscando un elemento, y una vez que lo encontramos, pedimos eliminarlo de la lista original, lo que implicaría un segundo trabajo de iteración para buscar este elemento dado. Esto respaldaría la afirmación de que, al menos en este caso, el enfoque iterador debería ser más rápido. Tenemos que considerar que solo el espacio estructural de la colección es el que se está creando, los objetos dentro de las colecciones no se están copiando. Ambas colecciones mantendrían referencias a los mismos objetos. ¡Cuando sucede GC no podemos decirlo!
Edwin Dalorzo
-2

¿Por qué no esto?

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

Y si es un mapa, no una lista, puede usar keyset ()

Drake Clarris
fuente
44
Este enfoque tiene muchas desventajas importantes. Primero, cada vez que elimina un elemento, los índices se reorganizan. Por lo tanto, si elimina el elemento 0, el elemento 1 se convierte en el nuevo elemento 0. Si va a hacer esto, al menos hágalo hacia atrás para evitar este problema. En segundo lugar, no todas las implementaciones de List ofrecen acceso directo a los elementos (como lo hace ArrayList). En un LinkedList esto sería tremendamente ineficiente porque cada vez que emite unget(i) debe visitar todos los nodos hasta llegar i.
Edwin Dalorzo
Nunca lo consideré, ya que normalmente solo lo usé para eliminar un solo elemento que estaba buscando. Bueno saber.
Drake Clarris
44
Llego tarde a la fiesta, pero ¿seguramente en el código de bloque if Foo.remove(i);que debes hacer i--;?
Bertie Wheen
porque está molesto
Jack