Suppression d'éléments d'une collection en java pendant l'itération sur celle-ci

Question

Je veux être en mesure de supprimer plusieurs éléments d'un ensemble pendant que j'effectue une itération sur celui-ci. Au départ, j'espérais que les itérateurs étaient suffisamment intelligents pour que la solution naïve ci-dessous fonctionne.

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

Mais cela jette un ConcurrentModificationException .

Notez que iterator.remove() ne fonctionnera pas, pour autant que je sache, car je dois supprimer plusieurs éléments à la fois. Supposons également qu'il n'est pas possible d'identifier les éléments à supprimer "à la volée", mais il est possible d'écrire la méthode setOfElementsToRemove() . Dans mon cas spécifique, cela prendrait beaucoup de mémoire et de temps de traitement pour déterminer ce qu'il faut supprimer pendant l'itération. Faire des copies n'est pas non plus possible en raison des contraintes de mémoire.

setOfElementsToRemove() va générer un ensemble d'instances de SomeClass que je veux supprimer, et fillSet(set) remplira le plateau d'entrées.

Après avoir cherché sur Stack Overflow, je n'ai pas trouvé de bonne solution à ce problème, mais quelques heures de pause plus tard, j'ai réalisé que la solution suivante ferait l'affaire.

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() générera un ensemble d'éléments à supprimer qui inclut la valeur qui lui est passée. Nous devons supprimer la valeur passée, donc set se videra.

Ma question est de savoir si quelqu'un a une meilleure façon de procéder ou s'il existe des opérations de collecte qui permettent ce type d'enlèvement.

J'ai également pensé que je posterais ma solution car il semble y avoir un besoin et je voulais contribuer à l'excellente ressource qu'est Stack Overflow.

Answer 1

Normalement, lorsque vous supprimez un élément d'une collection tout en bouclant sur la collection, vous obtenez un message Exception de modification simultanée . C'est en partie pourquoi le Itérateur possède une méthode remove(). L'utilisation d'un itérateur est le seul moyen sûr de modifier une collection d'éléments tout en la parcourant.

Le code ressemblerait à ceci :

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 cette façon, vous supprimez en toute sécurité tous les éléments qui génèrent un ensemble de suppression à partir de votre setOfElementsToRemove().

EDITAR

D'après un commentaire sur une autre réponse, c'est peut-être plus ce que vous voulez :

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

Au lieu d'itérer à travers tous les éléments de l'ensemble pour retirer ceux que vous voulez, vous pouvez en fait utiliser Google Collections (ce qui n'est pas impossible à faire soi-même) et appliquer un prédicat à masque ceux dont vous n'avez pas besoin.

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 3

Toute solution qui implique la suppression de l'ensemble que vous itérez pendant que vous l'itérez, mais pas via l'itérateur, ne fonctionnera absolument pas. Sauf peut-être une : vous pourriez utiliser un Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(_sizing params_)) . Le problème est que maintenant votre itérateur est seulement faiblement cohérent Cela signifie que chaque fois que vous supprimez un élément que vous n'avez pas encore rencontré, il n'est pas défini si cet élément apparaîtra plus tard dans votre itération ou non. Si ce n'est pas un problème, cela peut fonctionner pour vous.

Une autre chose que vous pouvez faire est de construire un toRemove au fur et à mesure, puis set.removeAll(itemsToRemove); seulement à la fin. Ou bien, copiez l'ensemble avant de commencer, afin de pouvoir itérer une copie tout en supprimant l'autre.

EDIT : oops, je vois que Peter Nix avait déjà suggéré le toRemove l'idée (bien qu'elle soit inutilement roulée à la main). removeAll ).

Answer 4

Vous pouvez essayer la méthode java.util.concurrent.CopyOnWriteArraySet qui vous donne un itérateur qui est un instantané de l'ensemble au moment de la création de l'itérateur. Toute modification apportée à l'ensemble (par exemple en appelant removeAll) ne sera pas visible dans l'itérateur, mais sera visible si vous regardez l'ensemble lui-même (et removeAll ne lancera pas l'appel).

Answer 5

Il existe une réponse simple à cette question : utilisez la méthode Iterator.remove().