Usuń elementy z kolekcji podczas iteracji

215

AFAIK, istnieją dwa podejścia:

  1. Powtórz kopię kolekcji
  2. Użyj iteratora rzeczywistej kolekcji

Na przykład,

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

i

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

Czy są jakieś powody, aby preferować jedno podejście nad drugim (np. Preferowanie pierwszego podejścia z prostej przyczyny czytelności)?

użytkownik1329572
źródło
1
Ciekawe, dlaczego tworzysz kopię głupca, a nie tylko zapętlasz głupca w pierwszym przykładzie?
Haz
@Haz, więc muszę zapętlić tylko raz.
user1329572
15
Uwaga: wolę „za” zamiast „również” za pomocą iteratorów, aby ograniczyć zakres zmiennej: for (Iterator <Foo> itr = fooList.iterator (); itr.hasNext ();) {}
Puce
Nie wiedziałem, że whilemają inne zasady określania zakresu niżfor
Alexander Mills
W bardziej złożonej sytuacji możesz mieć przypadek, w którym fooListjest zmienną instancji, i wywołujesz metodę podczas pętli, która kończy się wywołaniem innej metody w tej samej klasie, która to robi fooList.remove(obj). Widziałem, jak to się dzieje. W takim przypadku kopiowanie listy jest najbezpieczniejsze.
Dave Griffiths,

Odpowiedzi:

418

Pozwól mi podać kilka przykładów z kilkoma alternatywami, aby uniknąć ConcurrentModificationException .

Załóżmy, że mamy następujący zbiór książek

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

Zbieraj i usuwaj

Pierwsza technika polega na zebraniu wszystkich obiektów, które chcemy usunąć (np. Za pomocą rozszerzonej pętli for), a po zakończeniu iteracji usuwamy wszystkie znalezione obiekty.

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

Zakłada się, że operacja, którą chcesz wykonać, to „usuń”.

Jeśli chcesz „dodać”, to podejście również by działało, ale zakładam, że iterowałbyś inną kolekcję, aby określić, które elementy chcesz dodać do drugiej kolekcji, a następnie wydać addAllmetodę na końcu.

Korzystanie z ListIterator

Jeśli pracujesz z listami, inna technika polega na użyciu narzędzia, ListIteratorktóre obsługuje usuwanie i dodawanie elementów podczas samej iteracji.

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

Ponownie użyłem metody „usuń” w powyższym przykładzie, co wydaje się sugerować twoje pytanie, ale możesz również użyć jej addmetody, aby dodać nowe elementy podczas iteracji.

Używanie JDK> = 8

Osoby pracujące z wersją Java 8 lub wyższą mogą skorzystać z kilku innych technik, aby z niej skorzystać.

Możesz użyć nowej removeIfmetody w Collectionklasie podstawowej:

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

Lub użyj nowego interfejsu API strumienia:

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

W tym ostatnim przypadku, aby odfiltrować elementy z kolekcji, należy ponownie przypisać oryginalne odwołanie do przefiltrowanej kolekcji (tj. books = filtered) Lub użyć przefiltrowanej kolekcji do removeAllznalezionych elementów z oryginalnej kolekcji (tj books.removeAll(filtered).).

Użyj listy podrzędnej lub podzbioru

Istnieją również inne alternatywy. Jeśli lista jest posortowana, a chcesz usunąć kolejne elementy, możesz utworzyć listę podrzędną, a następnie ją wyczyścić:

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

Ponieważ lista podrzędna jest poparta oryginalną listą, byłby to skuteczny sposób na usunięcie tego podkolekcji elementów.

Coś podobnego można osiągnąć za pomocą posortowanych zestawów przy użyciu NavigableSet.subSetmetody lub dowolnej dostępnej tam metody krojenia.

Uwagi:

Wybór metody może zależeć od tego, co zamierzasz zrobić

  • Odbierz i removeAlTechnika technika działa z dowolną kolekcją (kolekcja, lista, zestaw itp.).
  • Ta ListIteratortechnika oczywiście działa tylko z listami, pod warunkiem, że ich ListIteratorimplementacja oferuje obsługę operacji dodawania i usuwania.
  • The IteratorPodejście będzie działać z każdym rodzajem kolekcji, ale obsługuje tylko operacje usunięcia.
  • Z ListIterator/Iterator podejściu oczywistą zaletą jest to, że nie trzeba niczego kopiować, ponieważ usuwamy je podczas iteracji. Jest to więc bardzo wydajne.
  • Przykład strumieni JDK 8 tak naprawdę niczego nie usunął, ale szukał pożądanych elementów, a następnie zastąpiliśmy oryginalne odwołanie do kolekcji nowym, i pozwoliliśmy, aby stary został wyrzucony. Tak więc powtarzamy tylko raz kolekcję i byłoby to skuteczne.
  • W kolekcji i removeAll podejścia wadą jest to, że musimy iterować dwa razy. Najpierw iterujemy w pętli foor w poszukiwaniu obiektu, który spełnia nasze kryteria usuwania, a gdy go znajdziemy, prosimy o usunięcie go z oryginalnej kolekcji, co oznaczałoby drugą pracę iteracji w celu wyszukania tego elementu w celu usunąć to.
  • Myślę, że warto wspomnieć, że metoda remove Iteratorinterfejsu jest oznaczona jako „opcjonalna” w Javadocs, co oznacza, że ​​mogą istnieć Iteratorimplementacje, które rzucają, UnsupportedOperationExceptionjeśli wywołamy metodę remove. Jako taki, powiedziałbym, że to podejście jest mniej bezpieczne niż inne, jeśli nie możemy zagwarantować iteratora wsparcia dla usuwania elementów.
Edwin Dalorzo
źródło
Brawo! to jest ostateczny przewodnik.
Magno C
To idealna odpowiedź! Dziękuję Ci.
Wilhelm,
7
W swoim akapicie o strumieniach JDK8, o których wspominasz removeAll(filtered). removeIf(b -> b.getIsbn().equals(other))
Skrótem
Jaka jest różnica między Iteratorem a ListIteratorem?
Alexander Mills,
Nie rozważałem usunięcia, ale to była odpowiedź na moje modlitwy. Dzięki!
Akabelle
15

W Javie 8 istnieje inne podejście. Kolekcja # removeIf

na przykład:

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

list.removeIf(i -> i > 2);
Santhosh
źródło
13

Czy są jakieś powody, by preferować jedno podejście od drugiego?

Pierwsze podejście będzie działać, ale ma oczywisty narzut związany z kopiowaniem listy.

Drugie podejście nie zadziała, ponieważ wiele kontenerów nie zezwala na modyfikację podczas iteracji. Obejmuje toArrayList .

Jeśli jedyną modyfikacją jest usunięcie bieżącego elementu, możesz sprawić, aby drugie podejście działało, używając itr.remove()(to znaczy użyj metody iteratora , a remove()nie kontenera ). To byłaby moja preferowana metoda dla iteratorów, które obsługują remove().

NPE
źródło
Ups, przepraszam ... sugeruje się, że użyłbym metody usuwania iteratora, a nie kontenera. A ile narzutu powoduje kopiowanie listy? Nie może to być wiele, a ponieważ jest to metoda, należy dość szybko zbierać śmieci. Zobacz edycję ..
użytkownik1329572
1
@ aix Myślę, że warto wspomnieć, że metoda usuwania Iteratorinterfejsu jest oznaczona jako opcjonalna w Javadocs, co oznacza, że ​​mogą istnieć implementacje Iteratora, które mogą rzucać UnsupportedOperationException. Jako taki powiedziałbym, że to podejście jest mniej bezpieczne niż pierwsze. W zależności od implementacji, które mają być zastosowane, pierwsze podejście może być bardziej odpowiednie.
Edwin Dalorzo
@EdwinDalorzo remove()na oryginalnej kolekcji może również wrzucić UnsupportedOperationException: docs.oracle.com/javase/7/docs/api/java/util/… . Interfejsy kontenerowe Java są niestety zdefiniowane jako wyjątkowo niewiarygodne (szczerze mówiąc, pokonanie punktu interfejsu). Jeśli nie znasz dokładnej implementacji, która będzie używana w środowisku uruchomieniowym, lepiej jest robić rzeczy w niezmienny sposób - np. Użyj interfejsu API strumieni Java 8+ do filtrowania elementów i zebrania ich w nowym kontenerze, a następnie całkowicie zastąp go starym.
Mateusz
5

Tylko drugie podejście będzie działać. Możesz modyfikować kolekcję podczas iteracji, używając iterator.remove()tylko. Wszystkie inne próby spowodują ConcurrentModificationException.

AlexR
źródło
2
Pierwsza próba polega na powtórzeniu kopii, co oznacza, że ​​może zmodyfikować oryginał.
Colin D
3

Ulubiony Old Timer (nadal działa):

List<String> list;

for(int i = list.size() - 1; i >= 0; --i) 
{
        if(list.get(i).contains("bad"))
        {
                list.remove(i);
        }
}
Shebla Tsama
źródło
1

Nie możesz zrobić drugiego, ponieważ nawet jeśli użyjesz remove()metody na Iteratorze , otrzymasz wyjątek .

Osobiście wolę pierwszy dla wszystkich Collectioninstancji, pomimo dodatkowego podsłuchu tworzenia nowego Collection, uważam, że jest mniej podatny na błędy podczas edycji przez innych programistów. W niektórych implementacjach Collection remove()obsługiwany jest Iterator , w innych nie. Możesz przeczytać więcej w dokumentacji dla Iteratora .

Trzecią alternatywą jest utworzenie nowego Collection, powtórzenie w stosunku do oryginału i dodanie wszystkich członków pierwszego Collectiondo drugiego Collection, których nie można usunąć. W zależności od wielkości Collectioni liczby usunięć może to znacznie zaoszczędzić na pamięci w porównaniu z pierwszym podejściem.

Jon
źródło
0

Wybrałbym drugi, ponieważ nie musisz robić kopii pamięci, a Iterator działa szybciej. Więc oszczędzasz pamięć i czas.

Calin Andrei
źródło
Iterator działa szybciej ”. Coś na poparcie tego roszczenia? Ponadto ślad pamięci związany z tworzeniem kopii listy jest bardzo trywialny, zwłaszcza, że ​​będzie się ona mieścić w metodzie i niemal natychmiast zbierze śmieci.
user1329572
1
W pierwszym podejściu wadą jest to, że musimy powtórzyć dwa razy. Iterujemy w pętli foor w poszukiwaniu elementu, a gdy go znajdziemy, prosimy o usunięcie go z oryginalnej listy, co oznaczałoby drugą pracę iteracji w celu wyszukania tego danego elementu. Potwierdzałoby to twierdzenie, że przynajmniej w tym przypadku podejście iteracyjne powinno być szybsze. Musimy wziąć pod uwagę, że tworzona jest tylko przestrzeń strukturalna kolekcji, obiekty w kolekcjach nie są kopiowane. Obie kolekcje zachowałyby odniesienia do tych samych obiektów. Kiedy dzieje się GC, nie możemy powiedzieć !!!
Edwin Dalorzo
-2

dlaczego nie to

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

A jeśli jest to mapa, a nie lista, możesz użyć zestawu kluczy ()

Drake Clarris
źródło
4
To podejście ma wiele poważnych wad. Po pierwsze, za każdym razem, gdy usuwasz element, indeksy są reorganizowane. Dlatego jeśli usuniesz element 0, element 1 stanie się nowym elementem 0. Jeśli masz zamiar to zrobić, przynajmniej zrób to wstecz, aby uniknąć tego problemu. Po drugie, nie wszystkie implementacje List oferują bezpośredni dostęp do elementów (podobnie jak ArrayList). Na LinkedList byłoby to niezwykle nieefektywne, ponieważ za każdym razem, gdy wydajesz get(i), musisz odwiedzać wszystkie węzły, aż do niego dotrzesz i.
Edwin Dalorzo
Nigdy nie zastanawiałem się nad tym, ponieważ zwykle po prostu użyłem go do usunięcia jednego elementu, którego szukałem. Dobrze wiedzieć.
Drake Clarris
4
Jestem spóźniony na imprezę, ale na pewno w kodzie blokowym if po Foo.remove(i);powrocie i--;?
Bertie Wheen
ponieważ jest zepsuty
Jack