Supprimer des éléments de la collection tout en itérant

Question

De ce que je sache, il existe deux approches :

1. Parcourir une copie de la collection
2. Utiliser l'itérateur de la collection réelle

Par exemple,

List fooListCopy = new ArrayList(fooList);
for(Foo foo : fooListCopy){
    // modifier la liste fooList actuelle
}

et

Iterator itr = fooList.iterator();
while(itr.hasNext()){
    // modifier la liste fooList actuelle en utilisant itr.remove()
}

Y a-t-il des raisons de préférer une approche à l'autre (par exemple, préférer la première approche pour la simple raison de lisibilité) ?

Answer 1

Laissez-moi donner quelques exemples avec quelques alternatives pour éviter une ConcurrentModificationException.

Supposons que nous avons la collection suivante de livres

List books = new ArrayList();
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")));

Collecter et supprimer

La première technique consiste à collecter tous les objets que nous voulons supprimer (par exemple en utilisant une boucle améliorée) et après avoir terminé l'itération, nous supprimons tous les objets trouvés.

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

Ceci suppose que l'opération que vous voulez faire est "supprimer".

Si vous voulez "ajouter", cette approche fonctionnerait également, mais je suppose que vous itéreriez sur une collection différente pour déterminer quels éléments vous voulez ajouter à une seconde collection et ensuite utiliseriez la méthode addAll à la fin.

Utilisation de ListIterator

Si vous travaillez avec des listes, une autre technique consiste à utiliser un ListIterator qui prend en charge la suppression et l'ajout d'éléments pendant l'itération elle-même.

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

Encore une fois, j'ai utilisé la méthode "remove" dans l'exemple ci-dessus, ce qui semblait être ce que votre question impliquait, mais vous pouvez également utiliser sa méthode add pour ajouter de nouveaux éléments pendant l'itération.

Utilisation de JDK >= 8

Pour ceux travaillant avec Java 8 ou des versions supérieures, il existe quelques autres techniques que vous pourriez utiliser pour en tirer avantage.

Vous pourriez utiliser la nouvelle méthode removeIf dans la classe de base Collection:

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

Ou utilisez la nouvelle API de stream:

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

Dans ce dernier cas, pour filtrer les éléments d'une collection, vous réassignez la référence d'origine à la collection filtrée (c'est-à-dire books = filtered) ou utilisez la collection filtrée pour removeAll les éléments trouvés de la collection d'origine (c'est-à-dire books.removeAll(filtered)).

Utiliser une sous-liste ou un sous-ensemble

Il existe d'autres alternatives également. Si la liste est triée, et que vous souhaitez supprimer des éléments consécutifs, vous pouvez créer une sous-liste puis la vider:

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

Étant donné que la sous-liste est liée à la liste d'origine, il s'agit d'une façon efficace de supprimer cette sous-collection d'éléments.

Quelque chose de similaire pourrait être réalisé avec des ensembles triés en utilisant la méthode subSet de NavigableSet, ou l'une des méthodes de découpage offertes là-bas.

Considérations:

La méthode que vous utilisez pourrait dépendre de ce que vous avez l'intention de faire

• La technique de collecte et de removeAll fonctionne avec n'importe quelle Collection (Collection, List, Set, etc).
• La technique du ListIterator fonctionne évidemment uniquement avec les listes, à condition que leur implémentation de ListIterator donnée offre un support pour les opérations d'ajout et de suppression.
• L'approche de l'Iterator fonctionnerait avec n'importe quel type de collection, mais elle ne prend en charge que les opérations de suppression.
• Avec l'approche du ListIterator/Iterator, l'avantage évident est de ne pas avoir à copier quoi que ce soit puisque nous supprimons au fur et à mesure que nous itérons. Ainsi, c'est très efficace.
• L'exemple des flux JDK 8 ne supprime en réalité rien, mais recherche les éléments désirés, et ensuite nous remplaçons la référence de la collection d'origine par la nouvelle, laissant l'ancienne être ramassée par le ramasse-miettes. Ainsi, nous itérons une seule fois sur la collection et c'est efficace.
• Dans l'approche de collecte et de removeAll, l'inconvénient est que nous devons itérer deux fois. D'abord nous itérons dans la boucle for recherchant un objet qui correspond à notre critère de suppression, et une fois trouvé, nous demandons de le supprimer de la collection d'origine, ce qui impliquerait un deuxième travail d'itération pour rechercher cet élément afin de le supprimer.
• Je pense qu'il convient de mentionner que la méthode de suppression de l'interface Iterator est marquée comme "optionnelle" dans la Javadoc, ce qui signifie qu'il pourrait y avoir des implémentations d'Iterator qui lancent une UnsupportedOperationException si nous invoquons la méthode de suppression. En tant que tel, je dirais que cette approche est moins sûre que d'autres si nous ne pouvons pas garantir le support de l'itérateur pour la suppression des éléments.

Answer 2

Ancien favori (cela fonctionne toujours):

List list;

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

Avantages:

1. Il itère seulement sur la liste une fois
2. Aucun objet supplémentaire créé, ni autre complexité inutile
3. Aucun problème avec l'utilisation de l'index d'un élément supprimé, car... bon, réfléchissez-y!

Answer 3

En Java 8, il existe une autre approche. Collection#removeIf

par exemple:

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

list.removeIf(i -> i > 2);

Answer 4

Y a-t-il des raisons de préférer une approche à l'autre

La première approche fonctionnera, mais a le surcoût évident de copier la liste.

La deuxième approche ne fonctionnera pas car de nombreux conteneurs ne permettent pas la modification pendant l'itération. Cela inclut ArrayList.

Si la seule modification est de supprimer l'élément actuel, vous pouvez faire fonctionner la deuxième approche en utilisant itr.remove() (c'est-à-dire, utilisez la méthode remove() de l'itérateur, pas du conteneur). Ce serait ma méthode préférée pour les itérateurs qui supportent remove().

Answer 5

Seule la deuxième approche fonctionnera. Vous pouvez modifier la collection pendant l'itération en utilisant iterator.remove() seulement. Toutes les autres tentatives provoqueront une ConcurrentModificationException.