Hinzufügen von Elementen zu einer Sammlung während der Iteration

Ist es möglich, einer Sammlung Elemente hinzuzufügen, während Sie darüber iterieren?

Insbesondere möchte ich eine Sammlung durchlaufen, und wenn ein Element eine bestimmte Bedingung erfüllt, möchte ich der Sammlung einige andere Elemente hinzufügen und sicherstellen, dass diese hinzugefügten Elemente auch wiederholt werden. (Ich weiß , dass dies könnte zu einer unterminating Schleife führen, aber ich bin mir ziemlich sicher , es wird nicht in meinem Fall.)

Das Java-Tutorial von Sun schlägt vor, dass dies nicht möglich ist: "Beachten Sie, dass dies Iterator.removeder einzig sichere Weg ist, eine Sammlung während der Iteration zu ändern. Das Verhalten ist nicht angegeben, wenn die zugrunde liegende Sammlung während der Iteration auf andere Weise geändert wird."

Also, wenn ich nicht mit Iteratoren machen kann, was ich will, was schlagen Sie mir vor?

Wie wäre es, eine Warteschlange mit den Elementen zu erstellen, über die Sie iterieren möchten? Wenn Sie Elemente hinzufügen möchten, stellen Sie sie am Ende der Warteschlange in die Warteschlange und entfernen Sie die Elemente so lange, bis die Warteschlange leer ist. So funktioniert normalerweise eine Breitensuche.

Hier gibt es zwei Probleme:

Das erste Problem ist das Hinzufügen zu einem, Collectionnachdem ein Iteratorzurückgegeben wurde. Wie bereits erwähnt, gibt es kein definiertes Verhalten, wenn der Basiswert Collectiongeändert wird, wie in der Dokumentation für Folgendes angegeben Iterator.remove:

... Das Verhalten eines Iterators ist nicht angegeben, wenn die zugrunde liegende Auflistung während der Iteration auf andere Weise als durch Aufrufen dieser Methode geändert wird.

Das zweite Problem ist, dass es keine Garantie für die Reihenfolge der Iteration gibt, selbst wenn eine erhalten werden Iteratorkönnte und dann zu demselben Element zurückkehrt, an Iteratordem sie sich befand, wie in der Collection.iteratorMethodendokumentation angegeben:

... Es gibt keine Garantien für die Reihenfolge, in der die Elemente zurückgegeben werden (es sei denn, diese Sammlung ist eine Instanz einer Klasse, die eine Garantie bietet).

Nehmen wir zum Beispiel an, wir haben die Liste [1, 2, 3, 4].

Nehmen wir an, es 5wurde hinzugefügt, als das Iteratorbei war 3, und irgendwie erhalten wir ein Iterator, von dem aus die Iteration fortgesetzt werden kann 4. Es gibt jedoch keine Garantie, 5die danach kommt 4. Die Iterationsreihenfolge kann sein [5, 1, 2, 3, 4]- dann wird der Iterator das Element immer noch verfehlen 5.

Da es keine Garantie für das Verhalten gibt, kann man nicht davon ausgehen, dass die Dinge auf eine bestimmte Weise geschehen werden.

Eine Alternative könnte darin bestehen, eine separate zu haben, Collectionzu der die neu erstellten Elemente hinzugefügt werden können, und diese Elemente dann zu durchlaufen:

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

Bearbeiten

Wenn Sie die Antwort von Avi näher erläutern , können Sie die Elemente, über die wir iterieren möchten, in eine Warteschlange stellen und die Elemente entfernen, während die Warteschlange Elemente enthält. Dies ermöglicht die "Iteration" über die neuen Elemente zusätzlich zu den ursprünglichen Elementen.

Schauen wir uns an, wie es funktionieren würde.

Konzeptionell, wenn wir die folgenden Elemente in der Warteschlange haben:

[1, 2, 3, 4]

Und wenn wir entfernen 1, entscheiden wir uns hinzuzufügen 42, die Warteschlange wird wie folgt sein:

[2, 3, 4, 42]

Da es sich bei der Warteschlange um eine FIFO -Datenstruktur (First-In, First-Out) handelt, ist diese Reihenfolge typisch. (Wie in der Dokumentation für die QueueSchnittstelle angegeben, ist dies keine Notwendigkeit von a Queue. Nehmen Sie den Fall, bei PriorityQueuedem die Elemente nach ihrer natürlichen Reihenfolge geordnet werden, das ist also kein FIFO.)

Das folgende Beispiel verwendet ein LinkedList(welches a ist Queue), um alle Elemente zusammen mit zusätzlichen Elementen, die während des Enthärtens hinzugefügt wurden, durchzugehen. Ähnlich wie im obigen Beispiel wird das Element 42hinzugefügt, wenn das Element 2entfernt wird:

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

Das Ergebnis ist folgendes:

1
2
3
4
42

Wie erhofft erschien das Element, 42das hinzugefügt wurde, als wir schlugen 2.

Möglicherweise möchten Sie auch einige der spezielleren Typen wie ListIterator , NavigableSet und (wenn Sie an Karten interessiert sind) NavigableMap betrachten .

Eigentlich ist es ziemlich einfach. Denken Sie nur an den optimalen Weg. Ich glaube, der optimale Weg ist:

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

Das folgende Beispiel funktioniert im logischsten Fall perfekt - wenn Sie die hinzugefügten neuen Elemente vor dem Iterationselement nicht iterieren müssen. Informationen zu den hinzugefügten Elementen nach dem Iterationselement - dort möchten Sie sie möglicherweise auch nicht iterieren. In diesem Fall sollten Sie Ihr Objekt einfach mit einem Flag hinzufügen / oder erweitern, das sie markiert, um sie nicht zu wiederholen.

Verwenden Sie ListIteratorwie folgt:

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

Der Schlüssel ist, in umgekehrter Reihenfolge zu iterieren - dann werden die hinzugefügten Elemente bei der nächsten Iteration angezeigt.

Ich weiß, dass es ziemlich alt war. Aber ich dachte daran, dass es für andere von Nutzen ist. Kürzlich bin ich auf dieses ähnliche Problem gestoßen, bei dem ich eine Warteschlange benötige, die während der Iteration geändert werden kann. Ich habe listIterator verwendet, um das Gleiche in den gleichen Zeilen zu implementieren, wie von Avi vorgeschlagen -> Avis Antwort . Sehen Sie, ob dies für Ihre Bedürfnisse geeignet ist.

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

    }

Verwenden von Iteratoren ... nein, das glaube ich nicht. Sie müssen so etwas zusammen hacken:

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

Welche yeilds:
[foo, bar, baz, hinzugefügt-Artikel-1, hinzugefügt-Artikel-2]

Neben der Lösung, eine zusätzliche Liste zu verwenden und addAll aufzurufen, um die neuen Elemente nach der Iteration einzufügen (z. B. die Lösung von Benutzer Nat), können Sie auch gleichzeitige Sammlungen wie die CopyOnWriteArrayList verwenden .

Die Iteratormethode im "Snapshot" -Stil verwendet einen Verweis auf den Status des Arrays zum Zeitpunkt der Erstellung des Iterators. Dieses Array ändert sich während der Lebensdauer des Iterators nie, sodass Interferenzen nicht möglich sind und der Iterator garantiert keine ConcurrentModificationException auslöst.

Mit dieser speziellen Sammlung (normalerweise für den gleichzeitigen Zugriff verwendet) ist es möglich, die zugrunde liegende Liste zu bearbeiten, während Sie darüber iterieren. Der Iterator spiegelt die Änderungen jedoch nicht wider.

Ist das besser als die andere Lösung? Wahrscheinlich nicht, ich kenne den Overhead, der durch den Copy-On-Write-Ansatz entsteht, nicht.

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

Zum Beispiel haben wir zwei Listen:

  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

Ich ziehe es vor, Sammlungen funktional zu verarbeiten, anstatt sie an Ort und Stelle zu mutieren. Dies vermeidet diese Art von Problem insgesamt sowie Aliasing-Probleme und andere knifflige Fehlerquellen.

Also würde ich es wie folgt implementieren:

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

Meiner Meinung nach wäre es sicherer, eine neue Sammlung zu erstellen, die angegebene Sammlung zu durchlaufen, jedes Element in die neue Sammlung aufzunehmen und bei Bedarf zusätzliche Elemente in die neue Sammlung aufzunehmen, um schließlich die neue Sammlung zurückzugeben.

Bei einer Liste, List<Object>die Sie durchlaufen möchten, ist der einfache Weg:

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

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

   list.remove(0);
}

Sie durchlaufen also eine Liste, nehmen immer das erste Element und entfernen es dann. Auf diese Weise können Sie während der Iteration neue Elemente an die Liste anhängen.

Vergessen Sie Iteratoren, sie funktionieren nicht zum Hinzufügen, sondern nur zum Entfernen. Meine Antwort gilt nur für Listen. Bestrafen Sie mich also nicht dafür, dass ich das Problem für Sammlungen nicht gelöst habe. Halten Sie sich an die Grundlagen:

    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++;
        }
    }

Ich habe ListIterator müde gemacht, aber es hat meinem Fall nicht geholfen, bei dem Sie die Liste beim Hinzufügen verwenden müssen. Folgendes funktioniert bei mir:

Verwenden Sie 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);
}

Dies kann zu einer Ausnahme führen oder zu Endlosschleifen führen. Wie Sie bereits erwähnt haben

Ich bin mir ziemlich sicher, dass dies in meinem Fall nicht der Fall ist

Es liegt in Ihrer Verantwortung, Eckfälle in einem solchen Code zu überprüfen.

Das mache ich normalerweise mit Sammlungen wie Sets:

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

Dies schafft zusätzlichen Speicher (die Zeiger für Zwischensätze, aber es treten keine doppelten Elemente auf) und zusätzliche Schritte (erneutes Durchlaufen von Änderungen). Dies ist jedoch normalerweise keine große Sache und möglicherweise besser als die Arbeit mit einer ersten Sammlungskopie.

Obwohl wir während der Iteration keine Elemente zur gleichen Liste hinzufügen können, können wir die flatMap von Java 8 verwenden, um einem Stream neue Elemente hinzuzufügen. Dies kann unter einer Bedingung erfolgen. Danach kann der hinzugefügte Artikel bearbeitet werden.

Hier ist ein Java-Beispiel, das zeigt, wie Sie dem laufenden Stream ein Objekt hinzufügen, das von einer Bedingung abhängt, die dann mit einer Bedingung verarbeitet wird:

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

Die Ausgabe des Spielzeugbeispiels lautet:

[2, 3, 21, 4]

Im Allgemeinen ist es nicht sicher, obwohl es für einige Sammlungen sein kann. Die offensichtliche Alternative besteht darin, eine Art for-Schleife zu verwenden. Sie haben jedoch nicht angegeben, welche Sammlung Sie verwenden, sodass dies möglicherweise nicht möglich ist.