example - Eliminar elementos de una colección en Java mientras se itera sobre ella

set<> java example

Question

Quiero poder 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 una ConcurrentModificationException .

Tenga en cuenta que iterator.remove () no funcionará tanto como yo pueda 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 entradas.

Después de buscar Stack Overflow 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 que se le pasa. Necesitamos eliminar el valor pasado para que el set se vacíe.

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

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

Answer 1

¿Por qué no utilizas el método de eliminación del iterador en los objetos que deseas eliminar?

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

Answer 2

Copiado de la API de Java :

La interfaz List proporciona un iterador especial, llamado ListIterator, que permite la inserción y el reemplazo de elementos, y el acceso bidireccional además de las operaciones normales que proporciona la interfaz Iterator. 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 ListIterator, que es un tipo especial de iterador, está diseñado para ser reemplazado.

Answer 3

Cualquier solución que implique eliminar del conjunto que está iterando mientras la itera, pero no a través del iterador, no funcionará. Excepto posiblemente uno: podría usar Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>( sizing params )) . El inconveniente es que ahora su iterador solo es 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 para toRemove en su lugar, 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.

EDITAR: oops, veo que Peter Nix ya había sugerido la idea de toRemove (aunque con un removeAll innecesariamente enrollado a removeAll ).

Answer 4

Debería llamar al método Iterator.remove .

También tenga en cuenta que en la mayoría de las colecciones de java.util , el método de 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

En lugar de iterar a través de todos los elementos en el Conjunto para eliminar los que desea, puede usar Google Collections (no es algo que no puede hacer por su cuenta) y aplicar un Predicado para enmascarar los que no necesita .

package com..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 6

Es posible implementar un Set que permita eliminar sus elementos 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.

Aquí hay un ejemplo incompleto usando Google Collections:

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 admite la operación remove() (pero el ejemplo en la pregunta no lo requiere).

Answer 7

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

Answer 8

Normalmente, cuando elimina un elemento de una colección al pasar por encima de la colección, obtendrá una Excepción de Modificación Concurrente . Esto es parcialmente por qué la interfaz del 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 forma, eliminará de forma segura todos los elementos que generan un conjunto de eliminación de su setOfElementsToRemove ().

EDITAR

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

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 9

Puede probar 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 a removeAll() ) no será visible en el iterador, pero estará visible si mira el conjunto en sí (y removeAll() no arrojará).

Answer 10

Si tiene suficiente memoria para una copia del conjunto, supongo que también tiene suficiente memoria para dos copias. Las reglas de Kafka-esque que citas no parecen prohibir eso :)

Mi sugerencia, entonces:

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

para que la copia permanezca intacta y solo proporcione las cosas para reproducir, mientras que el ajuste sufre eliminaciones. Las cosas que se eliminaron del set mientras tanto serán ignoradas.