Iteratoren und Datenstrukturen

Ishildur

Hallo zusammen, ich bin im Rahmen meiner Bachelorarbeit noch immer mit diversen Datenstrukturen beschäftigt und bin diesbezüglich auf einige Grundsatzfragen im Zusammenhang mit Iteratoren gestossen. Naja, solange Iteratoren ausschliesslich lesend auf eine Datenstruktur zugreifen, ist alles noch sehr einfach. Was aber, wenn diese die entsprechende Datenstruktur in irgendeiner Weise manipulieren (Add,Insert,Remove). Ich denke, solange immer nur ein einziger Iterator gleichzeitig über die Datenstruktur iteriert, sollte auch dies ein nicht allzug grosses Problem werden. Was aber, wenn mehrere Iteratoren parallel (nicht zeitgleich, sondern verzahnt) über die Datenstruktur iterieren und diese verändern. Ich habe diesbezüglich gängige Implementationen betrachtet und dabei folgendes gefunden.

Java: In der Doku steht:

public void remove();
Removes from the underlying collection the last element returned by the iterator (optional operation). This method can be called only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

Klare Ansage, der Programmierer: Keinerlei Schutzmechanismen vorhanden...

C# Wirft in einem solchen Fall ADAIK sowas wie eine ConcurrentModificationException

Bei der STL habe ich komischerweise keinerlei Informationen gefunden.

Aufbauend auf den gesammelten Informationen habe ich mir mal folgende Gedanken gemacht:

Also die Lösung von Java => undefiniertes Verhalten, gefällt mir irgendwie nicht so gut, auch wenn es sicherlich die performanteste Lösung wäre. Ich habe mir also Gedanken darüber gemacht, wie man eine ConcurrentModificationException wie in C# umsetzen könnte:

Jeder Iterator kriegt einen Zeitstempel, wann er erzeugt wurde. Die Datenstruktur selbst hat ebenfalls einen Zeitstempel der letzten Modifikation. Nun vergleicht jeder Iterator bei jedem Zugriff seinen Zeitstempel mit demjenigen in der Datenstruktur und weis sofort, ob die Datenstruktur manipuliert wurde, nachdem der entsprechende Iterator erzeugt wurde. Dadurch wird natürlich der Iterationsprozess verlangsamt, weil bei jedem Zugriff zuerst noch der Zeitstempel verglichen wird. Naja, könnte man ja auch mit einem Assert anstatt mit einer Exception machen, dann fällt der Overhead im Release Mode weg.

Eine andere Lösung wäre vielleicht, dass die Datenstruktur über jeden herausgegebenen Iterator Buch führt und sämtliche Iteratoren ungültig macht (vielleicht mit einem Flag innderhalb der iteratoren), wenn die Datenstruktur verändert wurde. Dies würde allerdings voraussetzten, dass bspw. eine LinkedList intern gerade selbst wieder eine LinkedList zum Abspeichern aller herausgegebenen Iteratoren benötigen würde, was glaube ich sehr ineffizient wäre. Ausserdem müsste bei dieser Variante ebenfalls bei jedem Zugriff das Flag geprüft werden.

Eine weitere Frage stellt sich mir diesbezüglich auch im Zusammenhang mit Multithreading. Soll ich die Datenstruktur für Schreibzugriff "sperren" solange noch mindestens ein Iterator herumgeistert? Dann müssten aber die Iteratoren irgendwie einen Mechanismus haben, um der Datenstruktur mitzuteilen, dass sie fertig sind mit iterieren. Naja, könnte man sicherlich mit Rerefence Counting und einer "Release" Methode seitens des Iterators bewerkstelligen.

Naja, das sind nur so meine wirren Gedanken und mich interessiert eure Meinungen und Erfahrungen zu diesem Thema

Mfg Samuel

volkard

In der Beschreibung zu add remove und so sollte stehen, ob iteratoren ungültig werden.
http://www.cplusplus.com/reference/stl/vector/push_back/

SeppJ

Bei der STL habe ich komischerweise keinerlei Informationen gefunden.

Der Standard besagt, dass es in den beschriebenen Fällen zu undefiniertem Verhalten kommt. Das kann aber auch durchaus bedeuten, dass eine Debug-Implementierung der STL dann eine Exception werfen darf. STL-Implementierungen die auf Releasecode getrimmt sind, enthalten aber üblicherweise keinerlei Schutzmechanismen.

Nexus

Es ist noch zu erwähnen, dass Iteratoren in C++ noch mal etwas anders als die Enumeratoren in Java sind, da sie grundsätzlich unabhängig von den Datenstrukturen existieren und im Allgemeinen nichts über letztere wissen müssen. Das heisst zum Beispiel auch, du kannst in C++ über einen Iterator nicht ein Element aus einer Range entfernen.

Aber der Iterator kann die Range intern so umsortieren, dass zu löschende Elemente am Ende der Sequenz vorzufinden sind. Dann gibt man dem Aufrufer den Anfang vom Ende (;)) zurück und der kann somit dem Container den Auftrag geben, die gewählten Elemente tatsächlich zu entfernen. Dieses Beispiel betrifft std::remove() und std::remove_if() .

Sowas kann man natürlich automatisieren. Um ungefähr zu erläutern, was ich meine (auf www.cplusplus.com oder den STL-Artikeln dieses Forums kannst du dich genauer informieren):

template <typename ContainerType, typename Function>
void RemoveIf(ContainerType& Ctr, Function RemoveCondition)
{
	Ctr.erase(std::remove_if(Ctr.begin(), Ctr.end(), RemoveCondition), Ctr.end());
}

Also besteht dein Problem eher darin, den Container selbst nicht zu verändern, während Iteratoren auf dessen Elemente zeigen. Das gilt im Übrigen auch für Referenzen und Zeiger. Aber auch hier gilt es zu differenzieren: Die assoziativen STL-Container und std::list lassen Elemente gültig. Was du auch beachten solltest, sind mehrere Algorithmen, die gleichzeitig auf der selben Sequenz herumwüten (z.B. bei Multithreading), da sie sich gegenseitig in die Quere kommen.

So, das waren nun etwas viel Informationen auf einmal, ich hoffe, du kannst was daraus brauchen.