Warum ist der Vergleich mit "end()" Iterator legal?

Question

Nach C++ Standard (3.7.3.2/4) mit (nicht nur Dereferenzierung, sondern auch Kopieren, Casting, was auch immer) ein ungültiger Zeiger ist undefiniertes Verhalten (im Zweifel siehe auch this question). Nun ist die typische Code ein STL containter sieht wie folgt zu verfahren:

std::vector<int> toTraverse; 
//populate the vector 
for(std::vector<int>::iterator it = toTraverse.begin(); it != toTraverse.end(); ++it) { 
    //process(*it); 
} 

std::vector::end() ist ein Iterator auf das Element hypothetic über das letzte Element des containter. Da es kein Element gibt, ist die Verwendung eines Zeigers durch diesen Iterator ein undefiniertes Verhalten.

Wie funktioniert das != end() dann? Ich meine, um den Vergleich durchzuführen, muss ein Iterator konstruiert werden, der eine ungültige Adresse umhüllt, und dann muss diese ungültige Adresse in einem Vergleich verwendet werden, der wiederum ein undefiniertes Verhalten ist. Ist solch ein Vergleich legal und warum?

Answer 1

Sie haben Recht, dass ein ungültiger Zeiger nicht verwendet werden kann, aber Sie irren sich, dass ein Zeiger auf ein Element nach dem letzten Element in einem Array ein ungültiger Zeiger ist - er ist gültig.

Der C-Standard, Abschnitt 6.5.6.8, so dass sie gut definiert und gültig ist:

... Wenn der Ausdruck P zeigt auf das letzte Element eines Array-Objekt, der Ausdruck (P) +1 Punkte einer hinter dem letzte Element des Array-Objekt ...

kann aber nicht dereferenziert werden:

... wenn das Ergebnis Punkte ein hinter dem letzte Element des Array-Objekt, es darf nicht als Operand eines unären Operator * verwendet werden, die ausgewertet wird ...

Answer 2

Huh? Es gibt keine Regel, die besagt, dass Iteratoren nur mit einem Zeiger implementiert werden müssen.

Es könnte ein boolesches Flag enthalten sein, das gesetzt wird, wenn die Inkrementierungsoperation sieht, dass es beispielsweise das Ende der gültigen Daten übergibt.

Answer 3

Die einzige Voraussetzung für end() ist, dass ++(--end()) == end(). Der end() könnte einfach ein spezieller Zustand sein, in dem sich der Iterator befindet. Es gibt keinen Grund, dass der Iterator end() einem Zeiger irgendeiner Art entsprechen muss.

Außerdem, selbst wenn es ein Zeiger wäre, erfordert der Vergleich von zwei Zeigern sowieso keine Art von Dereferenzierung. Berücksichtigen Sie Folgendes:

char[5] a = {'a', 'b', 'c', 'd', 'e'}; 
char* end = a+5; 
for (char* it = a; it != a+5; ++it); 

Dieser Code funktioniert einwandfrei, und es spiegelt Ihren Vektorcode.

Answer 4

Die Implementierung eines end() Iterators einer Standardbibliotheks-Container ist, nun, Implementierung-definiert, so dass die Implementierung Tricks spielen kann, weiß es die Plattform zu unterstützen.
Wenn Sie eigene Iteratoren implementiert haben, können Sie tun, was Sie wollen - solange es standardkonform ist. Beispielsweise könnte Ihr Iterator beim Speichern eines Zeigers einen Zeiger NULL speichern, um einen Enditerator anzuzeigen. Oder es könnte eine boolesche Flagge oder Ähnliches enthalten.

Answer 5

Außer dem, was bereits gesagt wurde (Iteratoren müssen nicht Zeiger), würde ich die Regel, die Sie

zitieren weisen darauf hin,

Nach C++ Standard (3.7.3.2/4) (nicht nur dereferencing, aber auch das Kopieren, Gießen, was sonst) ein ungültiger Zeiger

würde ohnehin nicht undefiniert Verhalten ist zu end() Iterator anzuwenden. Grundsätzlich, wenn Sie ein Array haben, sind alle Zeiger auf seine Elemente, plus ein Zeiger über das Ende, plus ein Zeiger vor dem Start des Arrays, gültig. Das bedeutet:

int arr[5]; 
int *p=0; 
p==arr+4; // OK 
p==arr+5; // past-the-end, but OK 
p==arr-1; // also OK 
p==arr+123456; // not OK, according to your rule 

Answer 6

Einfach. Iteratoren sind nicht (unbedingt) Zeiger.

Sie haben einige Ähnlichkeiten (d. H.Sie können sie dereferenzieren), aber das ist es auch schon.

Answer 7

Eine nach dem Ende ist kein ungültiger Wert (weder mit regulären Arrays oder Iteratoren). Sie können es nicht dereferenzieren, aber es kann für Vergleiche verwendet werden.

std::vector<X>::iterator it; 

Dies ist ein einzelner Iterator. Sie können nur einen gültigen Iterator zuweisen.

std::vector<X>::iterator it = vec.end(); 

Dies ist ein perfekt gültiger Iterator. Sie können es nicht dereferenzieren, aber Sie können es für Vergleiche verwenden und dekrementieren (vorausgesetzt, der Container hat eine ausreichende Größe).

Answer 8

antworte ich hier seit andere Antworten sind jetzt veraltet; sie waren jedoch nicht ganz richtig auf die Frage.

Zuerst hat C++ 14 die in der Frage genannten Regeln geändert. Die Indizierung durch einen ungültigen Zeigerwert oder die Übergabe eines ungültigen Zeigerwerts an eine Freigabe-Funktion sind noch nicht definiert, aber andere Operationen sind jetzt implementierungsdefiniert, siehe Documentation of "invalid pointer value" conversion in C++ implementations.

Zweitens zählt Wörter. Sie können die Definitionen nicht umgehen, während Sie die Regeln anwenden. Der entscheidende Punkt ist hier die Definition von "ungültig". Für Iteratoren ist dies in [iterator.requirements] definiert. In der Tat, selbst wenn es wahr ist, dass pointers are iterators, Bedeutungen von "ungültig" zu ihnen sind subtil anders. Regeln für Zeiger machen "ungültig" als "nicht indirekt durch ungültigen Wert", was ein Spezialfall von "nicht dereferenceable" für Iteratoren ist; "nicht referenzierbar" ist jedoch nicht, was für Iteratoren "ungültig" bedeutet. "Ungültig" ist explizit als "may be singular" definiert, während "Singular" -Wert als "keiner Sequenz zugeordnet" definiert ist (im selben Absatz der Definition von "dereferenzierbar"). In diesem Absatz wurden sogar explizit die "über die Endwerte" definiert.

Aus dem Text der Norm in [iterator.requirements], ist es klar, dass:

• past-the-End-Wert nicht (zumindest von der Standardbibliothek) sein dereferenceable angenommen, wie der Standard besagt.
• Dereferenzierbare Werte sind nicht singulär, da sie der Sequenz zugeordnet sind.
• Die Werte am Ende der Vergangenheit sind nicht singulär, da sie der Sequenz zugeordnet sind.
• Ein Iterator ist nicht ungültig, wenn er definitiv nicht singulär ist (durch Negation bei der Definition von "ungültiger Iterator"). Mit anderen Worten: Wenn ein Iterator einer Sequenz zugeordnet ist, ist er nicht ungültig.

Wert von end() ist ein past-the-Endwert, der mit einer Sequenz verknüpft ist, bevor sie ungültig gemacht wird. So ist es tatsächlich per Definition gültig. Auch mit Missverständnissen auf "ungültig" wörtlich, sind die Regeln der Zeiger hier nicht anwendbar.

Die Regeln für == Vergleich auf solche Werte sind in input iterator requirements, die von einer anderen Kategorie von Iteratoren (vorwärts, bidirektionale, usw.) geerbt wird. Genauer gesagt gültige Iteratoren are required to be comparable in the domain of the iterator auf diese Weise (==). Weitere Anforderungen für den Vorwärts-Iterator sind the domain is over the underlying sequence. Und Containeranforderungen spezifiziert die iterator und const_iterator Mitgliedstypen in any iterator category meets forward iterator requirements. Somit muss == über end() und Iterator über denselben Container klar definiert sein. Als Standard-Container erfüllen auch vector<int> die Anforderungen. Das ist die ganze Geschichte.

Drittens: Selbst wenn end() ist ein Zeigerwert (dies ist wahrscheinlich mit einem optimierten Umsetzung des Iterator vector Instanz geschehen), die Regeln in der Frage noch nicht anwendbar. Der Grund ist oben erwähnt (und in einigen anderen Antworten): "ungültig" betrifft * (indirekt durch), kein Vergleich. One-past-end value is explicitly allowed to be compared in specified ways by the standard. Beachten Sie auch, dass ISO C++ nicht ISO C ist, sie stimmen auch subtil (z. B. für < auf Zeigerwerte nicht im selben Array, nicht angegeben vs. undefiniert), obwohl sie hier ähnliche Regeln haben.