Was passiert, wenn Sie einen Iterator erhöhen, der dem Enditerator eines STL-Containers entspricht?

70

Was ist, wenn ich einen Iterator um 2 inkrementiere, wenn er auf das letzte Element eines Vektors zeigt? In dieser Frage , wie der Iterator durch zwei Elemente an einen STL-Container angepasst werden kann, werden zwei verschiedene Ansätze angeboten:

  • Verwenden Sie entweder zweimal eine Form des arithmetischen Operators - + = 2 oder ++
  • oder benutze std :: advanced ()

Ich habe beide mit VC ++ 7 auf den Randfall getestet, wenn der Iterator auf das letzte Element des STL-Containers oder darüber hinaus zeigt:

vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();
advance( it, 2 );
bool isAtEnd = it == vec.end(); // true
it++; // or advance( it, 1 ); - doesn't matter
isAtEnd = it == vec.end(); //false
it = vec.begin();
advance( it, 3 );
isAtEnd = it == vec.end(); // false

Ich habe vielleicht mal einen Rat gesehen, beim Überqueren des Vektors und anderer Container mit vector :: end () zu vergleichen:

for( vector<int>::iterator it = vec.begin(); it != vec.end(); it++ ) {
    //manipulate the element through the iterator here
}

Wenn der Iterator über das letzte Element in der Schleife hinaus vorgerückt ist, wird der Vergleich in der for-Schleifenanweisung offensichtlich als falsch ausgewertet, und die Schleife wird glücklich in ein undefiniertes Verhalten übergehen.

Verstehe ich es richtig, dass ich diese Situation nicht erkennen kann, wenn ich jemals progress () oder irgendeine Art von Inkrementoperation für einen Iterator verwende und ihn über das Ende des Containers hinaus zeige? Wenn ja, was ist die beste Vorgehensweise, um solche Fortschritte nicht zu nutzen?

scharfer Zahn
quelle

Antworten:

65

Es folgt das Zitat aus dem Buch von Nicolai Josuttis:

Beachten Sie, dass progress () nicht prüft, ob es das Ende () einer Sequenz überschreitet (es kann nicht geprüft werden, da Iteratoren im Allgemeinen die Container, mit denen sie arbeiten, nicht kennen). Das Aufrufen dieser Funktion kann daher zu einem undefinierten Verhalten führen, da der Aufruf von Operator ++ für das Ende einer Sequenz nicht definiert ist

Mit anderen Worten, die Verantwortung für die Aufrechterhaltung des Iterators innerhalb des Bereichs liegt vollständig beim Anrufer.

Naveen
quelle
2
Wie prüfe ich, ob es nach der arithmetischen Operation im Bereich liegt?
Narek
1
@ Narek Du kannst nicht. Das Überprüfen nach einer Operation, die möglicherweise UB aufweist, ist in C ++ immer eine verlierende Strategie.
Sebastian Redl
14

Vielleicht sollten Sie so etwas haben:

template <typename Itr>
Itr safe_advance(Itr i, Itr end, size_t delta)
{
    while(i != end && delta--)
        i++;
    return i;
}

Sie können dies für überlasten , wenn iterator_category<Itr>ist random_access_iteratorso etwas wie die folgende zu tun:

return (delta > end - i)? end : i + delta;
Motti
quelle
7

Sie können die Funktion "Abstand" zwischen Ihrem Iterator (it) und dem Iterator bei vec.begin () verwenden und sie mit der Größe des Vektors vergleichen (erhalten durch size ()).

In diesem Fall würde Ihre for-Schleife folgendermaßen aussehen:

for (vector<int>::iterator it = vec.begin(); distance(vec.begin(), it) < vec.size(); ++it)
{
     // Possibly advance n times here.
}
Kostas
quelle
Beruht dies auf einer zusammenhängenden Speicherzuweisung oder funktioniert es auch für andere Container?
Scharfzahn
2
Es hat mehr damit zu tun, wie Operator ++ für jeden Iteratortyp implementiert ist. "distance" zählt, wie viele ++ oder - für einen Iterator ausgeführt werden müssten, um den anderen zu erreichen. Wenn ich Sie wäre, würde ich es an allen Arten von Containern versuchen, die ich erwarte, und sehen, welche Entfernung mir gibt.
Kostas
1
distance () funktioniert auf jedem Eingabe-, Vorwärts-, bidirektionalen oder Direktzugriffs-Iterator gemäß dem Standard (24.3.4)
jalf
2
Die Entfernung ist für Iteratoren mit wahlfreiem Zugriff optimiert: Die Komplexität ist O (1), da sie nicht ++ zählt, sondern eine Subtraktion durchführt
Konstantin Tenzin
2
@jalf " distance () funktioniert auf jedem Eingabe-Iterator ": Das wollen Sie wahrscheinlich nicht!
Neugieriger
3

Der Code, den Marijn vorschlägt, ist nur leicht falsch (wie neugieriger Kerl betonte).

Die korrekte Version der letzten Zeile lautet:

bool isPastEnd = it >= vec.end();
DukeBrymin
quelle
it > vec.end()kann als immer falsch angenommen werden. ++vec.end()ist undefiniertes Verhalten
Caleth
1

Sie können auch weitere Vergleiche in Ihrer for-Anweisung durchführen:

for( vector<int>::iterator it = vec.begin(); it != vec.end() && it+1 != vec.end(); it+=2 ) {
    //manipulate the element through the iterator here
}

Ich weiß nicht, wie sich dies gegen Kostas ' Vorschlag verhalten würde , aber es scheint, als wäre es für ein kleines Inkrement besser. Natürlich wäre es für ein großes Inkrement ziemlich nicht zu warten, da Sie für jedes einen Check benötigen, aber es ist eine andere Option.

Ich würde es definitiv vermeiden, wenn es überhaupt möglich ist. Wenn Sie wirklich um jeweils 2 Werte inkrementieren müssen, sollten Sie einen Vektor von std :: pair oder einen Vektor einer Struktur mit 2 Elementen verwenden.

Delfin
quelle
1

Ich schlage vor, dass Sie sich Boost.Range ansehen .
Die Verwendung ist möglicherweise sicherer.
Es wird auch in C ++ 0x sein.

the_drow
quelle
1

container.end() - das Element kurz nach dem Ende - ist der einzige definierte äußere Wert.

Ein überprüfter Iterator wird einen Fehler bei einem Zugriff außerhalb des Bereichs machen, aber das ist nicht besonders hilfreich (insbesondere, da das Standardverhalten darin besteht, das Programm zu beenden).

Ich denke, die beste Vorgehensweise ist "Mach das nicht" - überprüfe entweder jeden Wert des Iterators (vorzugsweise in etwas, das als Filter verpackt ist) und arbeite nur mit interessanten Einträgen oder verwende den Index explizit mit

for(int i = 0; i < vec.size(); i+=2) {...}
Steve Gilham
quelle
-2

Obwohl diese Frage ein halbes Jahr alt ist, kann es dennoch nützlich sein, die Verwendung von Vergleichsoperatoren> und <zu erwähnen, um zu überprüfen, ob Sie das Ende (oder den Anfang beim Zurücklaufen) des Containers überschritten haben. Zum Beispiel:

vector<int> vec;
vec.push_back( 1 );
vec.push_back( 2 );

vector<int>::iterator it = vec.begin();

it+=10; //equivalent to advance( it, 10 )
bool isPastEnd = it > vec.end(); //true
Marijn
quelle
Entschuldigung, das ist FALSCH. Wie bereits erläutert, darf ein gültiger Iterator nicht hinter dem One-Past-The-End-Iterator, dh end (), liegen.
Neugieriger
1
Dies funktioniert nur, weil die Implementierung von std :: vector :: iterator tatsächlich ein Rohzeiger ist. Bei einem anderen Container kann die Geschichte völlig anders sein, es kann sogar eine Ausnahme auslösen, wenn Sie versuchen, über das Ende hinauszugehen.
Sogartar