Was bewirkt die Aktivierung des STL-Iterator-Debugging wirklich?

Question

Ich habe das Iterator-Debugging in einer Anwendung aktiviert, indem ich Folgendes definiert habe

_HAS_ITERATOR_DEBUGGING = 1

Ich hatte erwartet, dass dies wirklich nur Vektor Grenzen zu überprüfen, aber ich habe das Gefühl, es ist viel mehr als das tun. Welche Prüfungen, etc. werden tatsächlich durchgeführt?

Dinkumware STL, nebenbei bemerkt.

Answer 1

Es gibt eine Reihe von Operationen mit Iteratoren, die zu undefiniertem Verhalten führen. Das Ziel dieses Triggers ist es, Laufzeitprüfungen zu aktivieren, um dies zu verhindern (unter Verwendung von Asserts).

Das Thema

Die offensichtliche Operation ist die Verwendung eines ungültigen Iterators, aber diese Ungültigkeit kann aus verschiedenen Gründen entstehen:

• Uninitialisierter Iterator
• Iterator zu einem Element, das gelöscht wurde
• Iterator zu einem Element, dessen physische Position sich geändert hat (Neuzuweisung für ein vector )
• Iterator außerhalb von [begin, end)

In der Norm ist für jeden Container genau festgelegt, welche Operation welchen Iterator ungültig macht.

Es gibt auch einen weniger offensichtlichen Grund, den die meisten Leute vergessen: das Mischen von Iteratoren zu verschiedenen Containern:

std::vector<Animal> cats, dogs;

for_each(cats.begin(), dogs.end(), /**/); // obvious bug

Dies bezieht sich auf ein allgemeineres Problem: die Gültigkeit der an die Algorithmen übergebenen Bereiche.

• [cats.begin(), dogs.end()) ist ungültig (es sei denn, das eine ist ein Alias für das andere)
• [cats.end(), cats.begin()) ist ungültig (es sei denn cats ist leer ??)

Die Lösung

Die Lösung besteht darin, den Iteratoren Informationen hinzuzufügen, so dass ihre Gültigkeit und die Gültigkeit der von ihnen definierten Bereiche während der Ausführung überprüft werden kann, um das Auftreten von undefiniertem Verhalten zu verhindern.

El _HAS_ITERATOR_DEBUGGING Symbol dient als Auslöser für diese Fähigkeit, weil es leider das Programm verlangsamt. In der Theorie ist es ganz einfach: jeder Iterator wird zu einem Observer des Containers, aus dem er stammt, und wird somit über die Änderung informiert.

In Dinkumware wird dies durch zwei Zusätze erreicht:

• Jeder Iterator trägt einen Zeiger auf den zugehörigen Container
• Jeder Container enthält eine verknüpfte Liste mit den von ihm erstellten Iteratoren

Und damit sind unsere Probleme auf elegante Weise gelöst:

• Ein nicht initialisierter Iterator hat keinen übergeordneten Container, die meisten Operationen (außer Zuweisung und Zerstörung) lösen eine Behauptung aus
• Ein Iterator zu einem gelöschten oder verschobenen Element wurde (dank der Liste) benachrichtigt und weiß von seiner Ungültigkeit
• Beim Inkrementieren und Dekrementieren eines Iterators kann geprüft werden, ob er innerhalb der Grenzen bleibt
• Die Prüfung, ob 2 Iteratoren zum selben Container gehören, ist so einfach wie der Vergleich ihrer Elternzeiger
• Die Überprüfung der Gültigkeit eines Bereichs ist so einfach wie die Überprüfung, dass wir das Ende des Bereichs erreichen, bevor wir das Ende des Containers erreichen (lineare Operation für die Container, die nicht zufällig zugänglich sind, also die meisten)

Die Kosten

Der Preis ist hoch, aber hat Korrektheit einen Preis? Wir können die Kosten aufschlüsseln:

• zusätzliche Speicherzuteilung (die zusätzliche Liste der Iteratoren wird beibehalten): O(NbIterators)
• Meldeverfahren für mutierende Vorgänge: O(NbIterators) (Beachten Sie, dass push_back o insert nicht unbedingt alle Iteratoren ungültig machen, sondern erase tut)
• Überprüfung der Gültigkeit des Bereichs: O( min(last-first, container.end()-first) )

Die meisten Bibliotheksalgorithmen sind natürlich so implementiert, dass sie möglichst effizient sind, d. h. die Prüfung wird in der Regel einmalig zu Beginn des Algorithmus durchgeführt, dann wird eine ungeprüfte Version ausgeführt. Dennoch kann sich die Geschwindigkeit stark verringern, insbesondere bei handgeschriebenen Schleifen:

for (iterator_t it = vec.begin();
     it != vec.end();              // Oops
     ++it)
// body

Wir kennen die Hoppla Zeile ist geschmacklos, aber hier ist es noch schlimmer: Bei jedem Durchlauf der Schleife erstellen wir einen neuen Iterator und zerstören ihn dann, was bedeutet, dass wir einen Knoten für vec Die Liste der Iteratoren... Muss ich auf die Kosten für die Zuweisung/Deallokation von Speicher in einer engen Schleife hinweisen?

Natürlich, ein for_each würde ein solches Problem nicht auftreten, was ein weiteres überzeugendes Argument für die Verwendung von STL-Algorithmen anstelle von handcodierten Versionen ist.

Answer 2

Soweit ich das verstanden habe:

_HAS_ITERATOR_DEBUGGING zeigt zur Laufzeit ein Dialogfeld an, um eine inkorrekte Iteratorverwendung festzustellen, einschließlich:

1) Iteratoren, die in einem Container verwendet werden, nachdem ein Element gelöscht wurde

2) Iteratoren, die in Vektoren verwendet werden, nachdem eine .push() oder .insert() Funktion aufgerufen wurde

Answer 3

Selon http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

Der C++-Standard beschreibt, welche Mitgliedsfunktionen Iteratoren zu einem Container ungültig werden lassen. Zwei Beispiele sind:

• Das Löschen eines Elements aus einem Container führt dazu, dass Iteratoren zu diesem Element ungültig werden.
• Die Vergrößerung eines Vektors (Push oder Insert) führt dazu, dass Iteratoren in den Vektorcontainer ungültig werden.