Das ist in etwa vergleichbar mit dem Absägen des Astes, auf dem man sitzt.
Als Beispiel nehme ich eine List<int>numbs mit Zufallszahlen, und alle Vielfachen von 3 sollen entfernt werden.
Wie es nicht geht
Die erste Variante des Fehlers würde foreach verwenden:
foreach(int n in numbs) if(n % 3 == 0) numbs.Remove(n);
| Fehler |
| "Auflistungen können während der Enumeration nicht verändert werden" |
Die Exception ist uns übrigens sehr nützlich, denn falls der Enumerator mit einer variablen Auflistung umgehen könnte, würde er dasselbe tückische Fehlverhalten produzieren, wie die folgende Variante des Fehlers, die Vorwärts-for-Schleife:
for(int i = 0; i < numbs.Count; i++) if(numbs[i] % 3 == 0) numbs.RemoveAt(i);
[FONT]i: 0 1 2 3 4 5 6 7 n: 8 6 3 5 8 1 2 9[/FONT]Erster Treffer bei i == 1. Danach sehen die Daten so aus:
[FONT]i: 0 1 2 3 4 5 6 7 n: 8 3 5 8 1 2 9[/FONT]Anschließend wird i auf 2 gesetzt. Durch die Entfernung des vorigen Treffers sind aber die folgenden Elemente nach vorn gerückt, und nun liegt eine 3 auf Position 1, wird aber nicht mehr geprüft, denn Zähler i steht schon auf 2.
Das tückische daran ist, dass die übersprungene Prüfung nur dann falsche Daten erzeugt, wenn zwei Treffer aufeinander folgen.
Wie es geht
Aus obiger Betrachtung ergibt sich direkt die "naive" Lösung, nämlich die Liste eben rückwärts zu durchlaufen:
for(int i = numbs.Count; i-- > 0; ) if(numbs[i] % 3 == 0) numbs.RemoveAt(i);
Aufwandsklasse der naiven Lösung
In üblichen arraybasierten Auflistungen (zB List<T>) werden beim Löschen eines Elementes intern alle Folge-Elemente um einen Platz nach vorne kopiert. Das heißt, bei jeder Löschung wird im Durchschnitt intern die halbe Liste durchlaufen. Eine Verdopplung der Element-Anzahl würde sowohl eine doppelte Treffer-Zahl mitbringen, als auch bei jedem Treffer doppelt so viele zu verrückende Elemente. Daraus ergibt sich eine quadratische Proportionalität zw. Anzahl der Elemente und dem Aufwand der Operation, also eine Aufwandsklasse von O(n^2).
Codestellen mit quadratischem Aufwand sollte man möglichst vermeiden, daher stelle ich im folgenden 3 Verbesserungen vor, die die unerwünschten Elemente in nur einem Durchgang entfernen (linearer Aufwand: O(n)).
Die Verbesserungen sind aber nicht bei allen Auflistungen anwendbar (Beispiele folgen), sodaß manchmal zur naiven Lösung keine Alternative besteht.
Verbesserung#1: Liste umkopieren, dabei Treffer auslassen
var list2 = new List<int>();
foreach(int n in numbs) if(n % 3 != 0) list2.Add(n);
- der Speicher der Ursprungs-Liste nicht freigegeben wird
- andernorts evtl. noch mit der veralteten Liste gearbeitet wird (Redundanz-Problem)
Verbesserung#2: Liste in sich selbst umkopieren
for(int i = 0; i < numbs.Count; i++) {
if(numbs[i] % 3 == 0) {
/*Die Treffer werden nicht entfernt, sondern ab dem ersten Treffer werden die folgenden
* Elemente nach vorn kopiert - Treffer werden dadurch überschrieben */
int i2 = i;
for(i++; i < numbs.Count; i++) {
if(numbs[i] % 3 != 0) numbs[i2++] = numbs[i];
}
//erst ganz zuletzt werden die überzähligen Stellen vom Ende her entfernt
numbs.RemoveRange(i2, i - i2);
}
}
Verbesserung#3: die dafür vorgesehene Methode nutzen
Der gesamte bisherige Code ist nicht praxis-relevant, und muß gewissermaßen als PseudoCode angesehen werden, denn die Auflistung List<T> bringt bereits eine Methode .RemoveAll(Predicate<T> match) mit, die genau das ausführt, was als Verbesserung#2 ausprogrammiert ist. Man muß nur einen Delegaten angeben, der bestimmt, ob ein Element zu entfernen ist, und List<T>.RemoveAll() entfernt alle diese Elemente, in nur einem Durchgang:
numbs.RemoveAll(delegate(int n) { return n % 3 == 0; });
//oder
numbs.RemoveAll(n => n % 3 == 0);
Spezielle Auflistungen
ControlCollection
Hier sind obige Verbesserungen nicht anwendbar. Da der Indexer readonly ist, kann dem i-ten Element kein anderes Control zugewiesen werden. Und natürlich kann man auch nicht eine ControlCollection durch eine andere austauschen, wie in Verbesserung#1 gezeigt. Wir müssen also auf die einfachste Lösung, das Rückwärts-Laufen, zurückgreifen.
ControlCollection ctrls = grpMultiControls.Controls;
for(int i = ctrls.Count; i-- > 0; ) if(ctrls[i] is Label) ctrls.RemoveAt(i);Im Gegenteil - man kann sogar auf Kosten der Schleifen-Performance die Lesbarkeit etwas verbessern:
foreach(int c in grpMultiControls.Controls.OfType<Label>().ToArray()) c.Dispose();TreenodeCollection und ListviewItemCollection
Möglicherweise sind dieses die Auflistungen, aus denen am häufigsten unerwünschte Elemente gelöscht werden sollen. Wie die ControlCollection sind auch diese eng an eine andere Klasse gekoppelt, und weder als ganzes austauschbar, noch lassen sich Elemente umkopieren. Als Algorithmus kommt also ebenfalls nur die Rückwärts-Schleife in Frage.
Da die drei letztgenannten Auflistungen direkt auf dem Bildschirm angezeigt werden, ist hier bei Mehrfach-Operationen eine Optimierung der Anzeige dringend angeraten - nämlich das zeitweilige Aussetzen ihrer Aktualisierung.
Für die ControlCollection bedeutet das, eingangs ParentControl.SuspendLayout() aufzurufen, und nach Abschluß der Mehrfach-Operation ParentControl.ResumeLayout().
grpMultiControls.SuspendLayout();
grpMultiControls.Controls.OfType<Label>().ToList().ForEach(c => c.Dispose());
grpMultiControls.ResumeLayout();EDIT von herbivore: Wenn es um das Löschen doppelter Elemente geht, siehe doppelte Werte einer Liste löschen.