Dodawanie elementów do kolekcji podczas iteracji

Czy można dodawać elementy do kolekcji podczas iteracji po niej?

Dokładniej, chciałbym iterować po kolekcji, a jeśli element spełnia określony warunek, chcę dodać inne elementy do kolekcji i upewnić się, że te dodane elementy są również iterowane. (Zdaję sobie sprawę, że może to prowadzić do nieskończonej pętli, ale jestem prawie pewien, że tak się nie stanie w moim przypadku).

Plik Java Tutorial z Sun sugeruje, nie jest to możliwe: „Należy pamiętać, że Iterator.removejest tylko . Bezpieczny sposób zmodyfikować kolekcji podczas iteracji; zachowanie jest nieokreślony, jeżeli zbiór bazowy jest modyfikowany w jakikolwiek inny sposób, podczas gdy iteracja jest w toku”

Więc jeśli nie mogę zrobić tego, co chcę zrobić za pomocą iteratorów, co sugerujesz, abym zrobił?

Co powiesz na zbudowanie kolejki z elementami, nad którymi chcesz iterować; kiedy chcesz dodać elementy, umieść je w kolejce na końcu kolejki i usuwaj elementy, aż kolejka będzie pusta. Tak zwykle działa wyszukiwanie wszerz.

Są tu dwa problemy:

Pierwszą kwestią jest dodanie do Collectionpo Iteratorzwróceniu an . Jak wspomniano, nie ma zdefiniowanego zachowania, gdy element bazowy Collectionjest modyfikowany, jak wspomniano w dokumentacji Iterator.remove:

... Zachowanie iteratora jest nieokreślone, jeśli bazowa kolekcja zostanie zmodyfikowana, podczas gdy iteracja jest w toku w inny sposób niż wywołanie tej metody.

Druga kwestia polega na tym, że nawet jeśli Iteratormożna było uzyskać a, a następnie powrócić do tego samego elementu, w którym się Iteratorznajdował, nie ma gwarancji co do kolejności iteracji, jak zaznaczono w Collection.iteratordokumentacji metody:

... Nie ma żadnych gwarancji co do kolejności zwracania elementów (chyba że ta kolekcja jest instancją jakiejś klasy, która daje gwarancję).

Na przykład, powiedzmy, że mamy listę [1, 2, 3, 4] .

Powiedzmy, że 5został dodany, gdy Iteratorbył w 3, i jakoś otrzymujemy, Iteratorktóry może wznowić iterację od 4. Jednak nie ma gwarancji, która 5nastąpi później 4. Kolejność iteracji może być taka [5, 1, 2, 3, 4]- wtedy iterator nadal będzie pomijał element5 .

Ponieważ nie ma gwarancji zachowania, nie można zakładać, że coś wydarzy się w określony sposób.

Jedną z alternatyw może być oddzielne, Collectiondo którego można dodawać nowo utworzone elementy, a następnie iterowanie po tych elementach:

Collection<String> list = Arrays.asList(new String[]{"Hello", "World!"});
Collection<String> additionalList = new ArrayList<String>();

for (String s : list) {
    // Found a need to add a new element to iterate over,
    // so add it to another list that will be iterated later:
    additionalList.add(s);
}

for (String s : additionalList) {
    // Iterate over the elements that needs to be iterated over:
    System.out.println(s);
}

Edytować

Opierając się na odpowiedzi Avi , możliwe jest umieszczanie w kolejce elementów, które chcemy iterować, do kolejki i usuwanie elementów, gdy kolejka zawiera elementy. Pozwoli to na „iterację” po nowych elementach oprócz elementów oryginalnych.

Spójrzmy, jak by to działało.

Koncepcyjnie, jeśli w kolejce mamy następujące elementy:

[1, 2, 3, 4]

A kiedy usuniemy 1, zdecydujemy się dodać 42, kolejka będzie wyglądać następująco:

[2, 3, 4, 42]

Ponieważ kolejka jest strukturą danych FIFO (pierwsze weszło , pierwsze wyszło), ta kolejność jest typowa. (Jak zauważono w dokumentacji Queueinterfejsu, nie jest to konieczne a Queue. Weźmy przykładPriorityQueue którym porządkuje elementy według ich naturalnego porządku, więc nie jest to FIFO).

Poniżej znajduje się przykład użycia a LinkedList(czyli a Queue) w celu przejścia przez wszystkie elementy wraz z dodatkowymi elementami dodanymi podczas dekolekcji. Podobnie jak w powyższym przykładzie, element 42jest dodawany po usunięciu elementu 2:

Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);

while (!queue.isEmpty()) {
    Integer i = queue.remove();
    if (i == 2)
        queue.add(42);

    System.out.println(i);
}

Wynik jest następujący:

1
2
3
4
42

Zgodnie z oczekiwaniami pojawił się element, 42który został dodany po trafieniu 2.

Można też spojrzeć na niektóre z bardziej wyspecjalizowanych typów, jak ListIterator , NavigableSet i (jeśli jesteś zainteresowany w mapach) NavigableMap .

Właściwie jest to raczej łatwe. Pomyśl tylko o optymalnym sposobie. Wierzę, że optymalny sposób to:

for (int i=0; i<list.size(); i++) {
   Level obj = list.get(i);

   //Here execute yr code that may add / or may not add new element(s)
   //...

   i=list.indexOf(obj);
}

Poniższy przykład działa doskonale w najbardziej logicznym przypadku - kiedy nie musisz iterować dodanych nowych elementów przed elementem iteracji. O elementach dodanych po elemencie iteracji - tam też możesz nie chcieć ich iterować. W takim przypadku powinieneś po prostu dodać / lub rozszerzyć obiekt yr flagą, która oznaczy je, aby ich nie iterować.

Użyj ListIteratorw następujący sposób:

List<String> l = new ArrayList<>();
l.add("Foo");
ListIterator<String> iter = l.listIterator(l.size());
while(iter.hasPrevious()){
    String prev=iter.previous();
    if(true /*You condition here*/){
        iter.add("Bah");
        iter.add("Etc");
    }
}

Kluczem jest iteracja w odwrotnej kolejności - wtedy dodane elementy pojawiają się w następnej iteracji.

Wiem, że był dość stary. Ale pomyślałem, że może się to przydać komukolwiek innemu. Niedawno natknąłem się na podobny problem, w którym potrzebuję kolejki, którą można modyfikować podczas iteracji. Użyłem listIterator, aby zaimplementować to samo w tych samych wierszach, co zasugerował Avi -> Odpowiedź Avi . Sprawdź, czy to będzie odpowiadało Twoim potrzebom.

ModifyWhileIterateQueue.java

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ModifyWhileIterateQueue<T> {
        ListIterator<T> listIterator;
        int frontIndex;
        List<T> list;

        public ModifyWhileIterateQueue() {
                frontIndex = 0;
                list =  new ArrayList<T>();
                listIterator = list.listIterator();
        }

        public boolean hasUnservicedItems () {
                return frontIndex < list.size();  
        }

        public T deQueue() {
                if (frontIndex >= list.size()) {
                        return null;
                }
                return list.get(frontIndex++);
        }

        public void enQueue(T t) {
                listIterator.add(t); 
        }

        public List<T> getUnservicedItems() {
                return list.subList(frontIndex, list.size());
        }

        public List<T> getAllItems() {
                return list;
        }
}

ModifyWhileIterateQueueTest.java

    @Test
    public final void testModifyWhileIterate() {
            ModifyWhileIterateQueue<String> queue = new ModifyWhileIterateQueue<String>();
            queue.enQueue("one");
            queue.enQueue("two");
            queue.enQueue("three");

            for (int i=0; i< queue.getAllItems().size(); i++) {
                    if (i==1) {
                            queue.enQueue("four");
                    }
            }

            assertEquals(true, queue.hasUnservicedItems());
            assertEquals ("[one, two, three, four]", ""+ queue.getUnservicedItems());
            assertEquals ("[one, two, three, four]", ""+queue.getAllItems());
            assertEquals("one", queue.deQueue());

    }

Używanie iteratorów ... nie, nie sądzę. Będziesz musiał zhakować coś takiego:

    Collection< String > collection = new ArrayList< String >( Arrays.asList( "foo", "bar", "baz" ) );
    int i = 0;
    while ( i < collection.size() ) {

        String curItem = collection.toArray( new String[ collection.size() ] )[ i ];
        if ( curItem.equals( "foo" ) ) {
            collection.add( "added-item-1" );
        }
        if ( curItem.equals( "added-item-1" ) ) {
            collection.add( "added-item-2" );
        }

        i++;
    }

    System.out.println( collection );

Które yeilds:
[foo, bar, baz, added-item-1, added-item-2]

Oprócz rozwiązania polegającego na wykorzystaniu dodatkowej listy i wywołaniu addAll w celu wstawienia nowych elementów po iteracji (jak np. Rozwiązanie użytkownika Nat), można również użyć współbieżnych kolekcji, takich jak CopyOnWriteArrayList .

Metoda iteratora w stylu „migawki” używa odwołania do stanu tablicy w punkcie, w którym iterator został utworzony. Ta tablica nigdy nie zmienia się w okresie istnienia iteratora, więc zakłócenia są niemożliwe, a iterator gwarantuje, że nie zgłosi ConcurrentModificationException.

Dzięki tej specjalnej kolekcji (zwykle używanej do współbieżnego dostępu) można manipulować podstawową listą podczas iteracji po niej. Jednak iterator nie odzwierciedli zmian.

Czy to lepsze niż inne rozwiązanie? Prawdopodobnie nie, nie znam narzutu wprowadzonego przez podejście Copy-On-Write.

public static void main(String[] args)
{
    // This array list simulates source of your candidates for processing
    ArrayList<String> source = new ArrayList<String>();
    // This is the list where you actually keep all unprocessed candidates
    LinkedList<String> list = new LinkedList<String>();

    // Here we add few elements into our simulated source of candidates
    // just to have something to work with
    source.add("first element");
    source.add("second element");
    source.add("third element");
    source.add("fourth element");
    source.add("The Fifth Element"); // aka Milla Jovovich

    // Add first candidate for processing into our main list
    list.addLast(source.get(0));

    // This is just here so we don't have to have helper index variable
    // to go through source elements
    source.remove(0);

    // We will do this until there are no more candidates for processing
    while(!list.isEmpty())
    {
        // This is how we get next element for processing from our list
        // of candidates. Here our candidate is String, in your case it
        // will be whatever you work with.
        String element = list.pollFirst();
        // This is where we process the element, just print it out in this case
        System.out.println(element);

        // This is simulation of process of adding new candidates for processing
        // into our list during this iteration.
        if(source.size() > 0) // When simulated source of candidates dries out, we stop
        {
            // Here you will somehow get your new candidate for processing
            // In this case we just get it from our simulation source of candidates.
            String newCandidate = source.get(0);
            // This is the way to add new elements to your list of candidates for processing
            list.addLast(newCandidate);
            // In this example we add one candidate per while loop iteration and 
            // zero candidates when source list dries out. In real life you may happen
            // to add more than one candidate here:
            // list.addLast(newCandidate2);
            // list.addLast(newCandidate3);
            // etc.

            // This is here so we don't have to use helper index variable for iteration
            // through source.
            source.remove(0);
        }
    }
}

Na przykład mamy dwie listy:

  public static void main(String[] args) {
        ArrayList a = new ArrayList(Arrays.asList(new String[]{"a1", "a2", "a3","a4", "a5"}));
        ArrayList b = new ArrayList(Arrays.asList(new String[]{"b1", "b2", "b3","b4", "b5"}));
        merge(a, b);
        a.stream().map( x -> x + " ").forEach(System.out::print);
    }
   public static void merge(List a, List b){
        for (Iterator itb = b.iterator(); itb.hasNext(); ){
            for (ListIterator it = a.listIterator() ; it.hasNext() ; ){
                it.next();
                it.add(itb.next());

            }
        }

    }

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5

Wolę przetwarzać zbiory funkcjonalnie, zamiast modyfikować je w miejscu. Pozwala to całkowicie uniknąć tego rodzaju problemów, a także problemów z aliasami i innych trudnych źródeł błędów.

Więc zaimplementowałbym to tak:

List<Thing> expand(List<Thing> inputs) {
    List<Thing> expanded = new ArrayList<Thing>();

    for (Thing thing : inputs) {
        expanded.add(thing);
        if (needsSomeMoreThings(thing)) {
            addMoreThingsTo(expanded);
        }
    }

    return expanded;
}

IMHO bezpieczniejszym sposobem byłoby utworzenie nowej kolekcji, iteracja po danej kolekcji, dodanie każdego elementu w nowej kolekcji i dodanie dodatkowych elementów, jeśli to konieczne, również w nowej kolekcji, w końcu zwrócenie nowej kolekcji.

Biorąc pod uwagę listę, List<Object>którą chcesz iterować, najłatwiejszym sposobem jest:

while (!list.isEmpty()){
   Object obj = list.get(0);

   // do whatever you need to
   // possibly list.add(new Object obj1);

   list.remove(0);
}

Tak więc, iterujesz listę, zawsze biorąc pierwszy element, a następnie go usuwając. W ten sposób możesz dodawać nowe elementy do listy podczas iteracji.

Zapomnij o iteratorach, nie działają one na dodawanie, tylko na usuwanie. Moja odpowiedź dotyczy tylko list, więc nie karz mnie za nierozwiązanie problemu ze zbiorami. Trzymaj się podstaw:

    List<ZeObj> myList = new ArrayList<ZeObj>();
    // populate the list with whatever
            ........
    int noItems = myList.size();
    for (int i = 0; i < noItems; i++) {
        ZeObj currItem = myList.get(i);
        // when you want to add, simply add the new item at last and
        // increment the stop condition
        if (currItem.asksForMore()) {
            myList.add(new ZeObj());
            noItems++;
        }
    }

Zmęczyłem ListIterator, ale nie pomogło to w moim przypadku, w którym musisz korzystać z listy podczas dodawania do niej. Oto, co działa dla mnie:

Użyj LinkedList .

LinkedList<String> l = new LinkedList<String>();
l.addLast("A");

while(!l.isEmpty()){
    String str = l.removeFirst();
    if(/* Condition for adding new element*/)
        l.addLast("<New Element>");
    else
        System.out.println(str);
}

Może to stanowić wyjątek lub napotkać nieskończone pętle. Jednak, jak wspomniałeś

Jestem prawie pewien, że w moim przypadku tak nie będzie

sprawdzanie przypadków narożnych w takim kodzie jest Twoim obowiązkiem.

To jest to, co zwykle robię z kolekcjami takimi jak zestawy:

Set<T> adds = new HashSet<T>, dels = new HashSet<T>;
for ( T e: target )
  if ( <has to be removed> ) dels.add ( e );
  else if ( <has to be added> ) adds.add ( <new element> )

target.removeAll ( dels );
target.addAll ( adds );

Tworzy to dodatkową pamięć (wskaźniki dla zestawów pośrednich, ale nie zdarzają się zduplikowane elementy) i dodatkowe kroki (ponowne iterowanie zmian), jednak zwykle nie jest to wielka sprawa i może być lepsza niż praca z początkową kopią kolekcji.

Mimo że nie możemy dodawać elementów do tej samej listy podczas iteracji, możemy użyć flatMap Java 8, aby dodać nowe elementy do strumienia. Można to zrobić pod pewnymi warunkami. Następnie można przetworzyć dodaną pozycję.

Oto przykład w Javie, który pokazuje, jak dodać do bieżącego strumienia obiekt w zależności od warunku, który jest następnie przetwarzany z warunkiem:

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

intList = intList.stream().flatMap(i -> {
    if (i == 2) return Stream.of(i, i * 10); // condition for adding the extra items
    return Stream.of(i);
}).map(i -> i + 1)
        .collect(Collectors.toList());

System.out.println(intList);

Dane wyjściowe przykładu zabawki to:

[2, 3, 21, 4]

W ogóle , to nie jest bezpieczne, chociaż dla niektórych zbiorów może być. Oczywistą alternatywą jest użycie jakiejś pętli for. Ale nie powiedziałeś, jakiej kolekcji używasz, więc może to być możliwe lub nie.