Eliminar elementos de una colección en java mientras se itera sobre él

Question

Quiero ser capaz de eliminar varios elementos de un conjunto mientras estoy iterando sobre él. Inicialmente esperaba que los iteradores fueran lo suficientemente inteligentes como para que la siguiente solución ingenua funcione.

Set<SomeClass> set = new HashSet<SomeClass>(); 
fillSet(set); 
Iterator<SomeClass> it = set.iterator(); 
while (it.hasNext()) { 
    set.removeAll(setOfElementsToRemove(it.next())); 
} 

Pero esto arroja un ConcurrentModificationException.

Tenga en cuenta que iterator.remove() no funcionará tan lejos como puedo ver porque necesito eliminar varias cosas a la vez. Supongamos también que no es posible identificar qué elementos eliminar "sobre la marcha", pero es posible escribir el método setOfElementsToRemove(). En mi caso específico, tomaría mucha memoria y tiempo de procesamiento para determinar qué eliminar mientras se iteraba. Hacer copias tampoco es posible debido a restricciones de memoria.

setOfElementsToRemove() generará un conjunto de instancias SomeClass que deseo eliminar, y fillSet(set) llenará el conjunto con las entradas.

Después de buscar Desbordamiento de pila No pude encontrar una buena solución a este problema, pero unas pocas horas después me di cuenta de que lo siguiente haría el trabajo.

Set<SomeClass> set = new HashSet<SomeClass>(); 
Set<SomeClass> outputSet = new HashSet<SomeClass>(); 
fillSet(set); 
while (!set.isEmpty()) { 
    Iterator<SomeClass> it = set.iterator(); 
    SomeClass instance = it.next(); 
    outputSet.add(instance); 
    set.removeAll(setOfElementsToRemoveIncludingThePassedValue(instance)); 
} 

setOfElementsToRemoveIncludingThePassedValue() generará un conjunto de elementos para eliminar que incluye el valor pasado a ella. Necesitamos eliminar el valor pasado para que set se vacíe.

Mi pregunta es si alguien tiene una mejor manera de hacerlo o si hay operaciones de recopilación que admiten este tipo de eliminaciones.

Además, pensé en publicar mi solución porque parece que hay una necesidad y quería contribuir con el excelente recurso que es Stack Overflow.

Answer 1

Normalmente, cuando elimina un elemento de una colección mientras se repite la colección, obtendrá un Concurrent Modification Exception. Esto es parcialmente porque la interfaz Iterator tiene un método remove(). El uso de un iterador es la única forma segura de modificar una colección de elementos al atravesarlos.

El código sería algo como esto:

Set<SomeClass> set = new HashSet<SomeClass>(); 
fillSet(set); 
Iterator<SomeClass> setIterator = set.iterator(); 
while (setIterator.hasNext()) { 
    SomeClass currentElement = setIterator.next(); 
    if (setOfElementsToRemove(currentElement).size() > 0) { 
     setIterator.remove(); 
    } 
} 

De esta manera podrás eliminar de manera segura todos los elementos que generan una extracción del conjunto, desde su setOfElementsToRemove().

EDITAR

Basado en un comentario a otra respuesta, esto puede ser más lo que quiere:

Set<SomeClass> set = new HashSet<SomeClass>(); 
Set<SomeClass> removalSet = new HashSet<SomeClass>(); 
fillSet(set); 

for (SomeClass currentElement : set) { 
    removalSet.addAll(setOfElementsToRemove(currentElement); 
} 

set.removeAll(removalSet); 

Answer 2

Hay una respuesta simple a esto: use el método Iterator.remove().

Answer 3

¿Por qué no utiliza el iterator's remove method en los objetos que desea eliminar?

Los iteradores se introdujeron principalmente porque los enumeradores no podían manejar la eliminación al enumerar.

Answer 4

Debe llamar al método Iterator.remove.

También tenga en cuenta que en la mayoría de las colecciones java.util el método remove generará una excepción si el contenido de la colección ha cambiado. Por lo tanto, si el código es de subprocesos múltiples, tenga mucho cuidado o use colecciones concurrentes.

Answer 5

Cualquier solución que consiste en extraer del conjunto que está iterando mientras estás iterarlo, pero no a través del iterador, no funcionará en absoluto. Excepto posiblemente uno: puede usar un Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(sizing params)). El truco es que ahora su iterador es solo débilmente consistente, lo que significa que cada vez que elimina un elemento que aún no ha encontrado, no está definido si ese elemento aparecerá más tarde en su iteración o no. Si eso no es un problema, esto podría funcionar para usted.

Otra cosa que puede hacer es crear un conjunto toRemove sobre la marcha, luego set.removeAll(itemsToRemove); solo al final. O bien, copie el conjunto antes de comenzar, de modo que pueda repetir una copia mientras quita la otra.

EDIT: oops, veo que Peter Nix ya había sugerido la idea de toRemove (aunque con una innecesariamente hecha a mano removeAll).

Answer 6

En lugar de recorrer todos los elementos del conjunto para eliminar los que desee, puede usar colecciones de Google (no es algo que no pueda hacer por su cuenta) y aplicar un predicado a máscara el unos que no necesitas

package com.stackoverflow.q1675037; 

import java.util.HashSet; 
import java.util.Set; 

import org.junit.Assert; 
import org.junit.Test; 

import com.google.common.base.Predicate; 
import com.google.common.collect.Iterables; 
import com.google.common.collect.Sets; 


public class SetTest 
{ 
public void testFilter(final Set<String> original, final Set<String> toRemove, final Set<String> expected) 
{ 

    Iterable<String> mask = Iterables.filter(original, new Predicate<String>() 
    { 
     @Override 
     public boolean apply(String next) { 
     return !toRemove.contains(next); 
     } 
    }); 

    HashSet<String> filtered = Sets.newHashSet(mask); 

    Assert.assertEquals(original.size() - toRemove.size(), filtered.size()); 
    Assert.assertEquals(expected, filtered);   
} 


@Test 
public void testFilterNone() 
{ 
    Set<String> original = new HashSet<String>(){ 
     { 
      this.add("foo"); 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    Set<String> toRemove = new HashSet(); 

    Set<String> expected = new HashSet<String>(){ 
     { 
      this.add("foo");     
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    this.testFilter(original, toRemove, expected); 
} 

@Test 
public void testFilterAll() 
{ 
    Set<String> original = new HashSet<String>(){ 
     { 
      this.add("foo"); 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    Set<String> toRemove = new HashSet<String>(){ 
     { 
      this.add("foo"); 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    HashSet<String> expected = new HashSet<String>(); 
    this.testFilter(original, toRemove, expected); 
}  

@Test 
public void testFilterOne() 
{ 
    Set<String> original = new HashSet<String>(){ 
     { 
      this.add("foo"); 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    Set<String> toRemove = new HashSet<String>(){ 
     { 
      this.add("foo"); 
     } 
    }; 

    Set<String> expected = new HashSet<String>(){ 
     { 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    this.testFilter(original, toRemove, expected); 
}  


@Test 
public void testFilterSome() 
{ 
    Set<String> original = new HashSet<String>(){ 
     { 
      this.add("foo"); 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    Set<String> toRemove = new HashSet<String>(){ 
     { 
      this.add("bar"); 
      this.add("foobar"); 
     } 
    }; 

    Set<String> expected = new HashSet<String>(){ 
     { 
      this.add("foo"); 
     } 
    }; 

    this.testFilter(original, toRemove, expected); 
}  
} 

Answer 7

Si tiene suficiente memoria para una copia del conjunto, supongo que también tiene suficiente memoria para dos copias. Las reglas kafkianos que usted cita no parecen prohibir que :)

Mi sugerencia, entonces:

fillSet(set); 
fillSet(copy); 
for (Object item : copy) { 
    if (set.contains(item)) { // ignore if not 
    set.removeAll(setOfStuffToRemove()) 
    } 
} 

modo de copia se mantiene intacto y solo proporciona el material de bucle en, mientras conjunto sufre supresiones. Las cosas que se eliminaron del set mientras tanto serán ignoradas.

Answer 8

Puede probar el java.util.concurrent.CopyOnWriteArraySet que le proporciona un iterador que es una instantánea del conjunto en el momento de la creación del iterador. Cualquier cambio que realice en el conjunto (es decir, al llamar al removeAll()) no estará visible en el iterador, pero estará visible si mira el conjunto (y no se lanzará el removeAll()).

Answer 9

Es posible implementar un Set que permite que sus elementos se eliminen mientras se itera sobre él.

Creo que las implementaciones estándar (HashSet, TreeSet etc.) no lo permiten porque eso significa que pueden usar algoritmos más eficientes, pero no es difícil de hacer.

He aquí un ejemplo incompleto usando Google Colecciones:

import java.util.Iterator; 
import java.util.Map; 
import java.util.Set; 
import java.util.concurrent.ConcurrentHashMap; 

import com.google.common.base.Predicates; 
import com.google.common.collect.ForwardingSet; 
import com.google.common.collect.Iterators; 
import com.google.common.collect.Sets; 

public class ConcurrentlyModifiableSet<E> 
extends ForwardingSet<E> { 
/** Create a new, empty set */ 
public ConcurrentlyModifiableSet() { 
    Map<E, Boolean> map = new ConcurrentHashMap<E, Boolean>(); 
    delegate = Sets.newSetFromMap(map); 
} 

@Override 
public Iterator<E> iterator() { 
    return Iterators.filter(delegate.iterator(), Predicates.in(delegate)); 
} 

@Override 
protected Set<E> delegate() { 
    return this.delegate; 
} 

private Set<E> delegate; 
} 

Nota: El iterador no soporta la operación remove() (pero el ejemplo en la pregunta no lo requiere.)

Answer 10

Copiado del Java API:

La interfaz lista proporciona un iterador especial, llamado un ListIterator, que permite la inserción del elemento y reemplazo, y el acceso bidireccional, además de las operaciones normales de que el iterador interfaz proporciona. Se proporciona un método para obtener un iterador de lista que comienza en una posición específica en la lista.

Pensé que señalaría que el ListIterator, que es un tipo especial de Iterator, está diseñado para ser reemplazado.