Ich versuche, eine std::list zu durchlaufen, aber es gibt ein Problem - die während der Iteration durchgeführten Operationen können dazu führen, dass ein Element aus der Liste hinzugefügt oder entfernt wird. Hinzufügungen sind in diesem Fall kein Problem, aber ein Entfernen kann dazu führen, dass alle Iteratoren in der Liste ungültig werden, einschließlich des aktuellen oder des nächsten Elements in der Sequenz.
Der Punkt, an dem die Entscheidung getroffen wird, die Liste zu modifizieren, ist weit entfernt von der Iterationsschleife - der Debugger zeigt 40 Funktionsaufrufe in dem Aufrufstapel zwischen den beiden. Aus diesem Grund ist es nicht möglich, den Iterator basierend auf dem Entfernen zu ändern.
Das Einzige, was mir einfällt, ist, am Anfang eine Kopie der Liste zu erstellen und darüber zu iterieren und jedes Element zu testen, um sicherzustellen, dass es immer noch in der Hauptliste ist. Das ist ein O (n ^ 2) Vorschlag, den ich möglichst vermeiden möchte.
Sie haben drei Möglichkeiten:
Wenn die Iteratoren ungültig sind, beginnen Sie erneut von vorn (und überspringen Sie vielleicht n iterations? [mit continue ])
Bearbeiten:
Wie Pubby sagte, markiere entfernte Elemente als abgelaufen, und wenn du Elemente hinzufügst, benutze das skipping n iterations Zeug:)
Iteratoren erlauben keinen Zugriff per Index, daher ist es etwas schwieriger, eine elegante Lösung für Ihr Problem zu finden.
kann dazu führen, dass ein Iterator in der Liste ungültig wird
Keine.
Sehen Sie sich die Beschreibung von std::list::erase :
Iterator-Gültigkeit
Fazit zum Löschen: Nur das entfernte Element wird ungültig. Alle anderen bleiben gültig. Und in diesem Fall haben Sie die Möglichkeit, O (n) in den meisten Kontexten zu implementieren.
Hier sind einige weitere Optionen.
Anstatt ein Element zu entfernen, könnte "modifizierender" Code es in eine temporäre Liste verschieben mit splice Methode. Das Verbinden einzelner Elemente ist eine konstante Zeitoperation. Und es macht keine Iteratoren oder Referenzen ungültig (selbst für ein verschobenes Element).
Vor dem Verschieben eines Elements sollte "modifizierender" Code die Hauptkopie des Listen-Iterators (der zum "iterierenden" Code gehört) vorrücken.
"Iterating" Code sollte nur diese temporäre Liste nach jeder Iteration löschen.
Vorteile: Sie müssen den enthaltenen Elementen keine Flags hinzufügen.
Nachteile: einige Leistungseinbußen wegen der Notwendigkeit, temporäre Liste zu löschen; benötigte externe Schnittstelle, um den zu "iterierenden" Code gehörenden Iterator weiterzuentwickeln; Wenn ein Code zwischen "iterierenden" und "modifizierenden" Codes die nächsten / vorherigen Elemente relativ zum "entfernten" Element untersuchen muss, sieht er nur andere "entfernte" Elemente anstelle des Rests der Liste.
Wenn Sie das Flag "locked" für das Element setzen, auf das der Iterator gerade zeigt, kann "Modifying" -Code Spleiß nur für dieses einzelne Element verwenden und andere auf die übliche Weise entfernen.
"Iterating" -Code sollte nur die temporäre Liste nach jeder Iteration löschen.
Vorteile: praktisch keine Leistung.
Nachteile: müssen Listenelemente ändern. benötigte externe Schnittstelle, um den zu "iterierenden" Code gehörenden Iterator weiterzuentwickeln; Wenn ein Code zwischen "iterierenden" und "modifizierenden" Codes die nächsten / vorherigen Elemente relativ zum "entfernten" Element überprüfen muss, findet er nichts.
Wenn Sie das Flag "locked" für das Element setzen, auf das iterator gerade zeigt, kann der "modifizierende" Code das Flag "removed" für dieses einzelne Element setzen und andere auf die übliche Weise entfernen.
"Iterating" -Code sollte (nach jeder Iteration) einfach ein Element entfernen, das zum Entfernen markiert ist.
Vorteile: praktisch keine Leistungseinbußen; Wenn ein Code zwischen "iterierenden" und "modifizierenden" Codes die nächsten / vorherigen Elemente relativ zum "entfernten" Element überprüfen muss, funktioniert er wie erwartet.
Nachteile: müssen Listenelemente ändern.
Zwei mögliche Ansätze kommen in Betracht (zusätzlich zu einer Kopie der Liste):
1) Löschen Sie keine Sachen sofort aus der Liste. Erstellen Sie stattdessen einen weiteren Container mit Iteratoren, die gelöscht werden sollen, sobald Sie mit der vollständigen Iteration fertig sind. Dies ändert das Verhalten ("gelöschte" Elemente können immer noch bearbeitet werden), also weiß ich nicht, ob es Ihnen hilft.
2) Lassen Sie Ihre Liste entweder Zeiger oder ein Paar mit dem Item / Validity-Flag enthalten und löschen Sie einfach die Gültigkeit. Wenn Sie das erste Mal iteriert haben, führen Sie eine weitere Iteration durch, um die ausgefallenen Knoten zu bereinigen.