Vergleichen von Iteratoren aus verschiedenen Containern

Ist es legal, Iteratoren aus verschiedenen Containern zu vergleichen?

std::vector<int> foo;
std::vector<int> bar;

Macht den Ausdruck foo.begin() == bar.begin() zu falschem oder undefiniertem Verhalten führen?

(Ich schreibe einen benutzerdefinierten Iterator und bin bei der Implementierung auf diese Frage gestoßen operator==.)

Wenn Sie den C ++ 11-Standard (n3337) berücksichtigen:

§ 24.2.1 — [iterator.requirements.general#6]

Ein Iterator j heißt erreichbar von einem Iterator i genau dann, wenn es eine endliche Folge von Anwendungen des Ausdrucks gibt ++i das macht i == j. Ob j ist erreichbar von ibeziehen sie sich auf Elemente derselben Folge.

§ 24.2.5 — [forward.iterators#2]

Die Domäne von == für Vorwärts-Iteratoren ist die von Iteratoren über dieselbe zugrunde liegende Sequenz.

Angesichts dessen RandomAccessIterator muss alle Anforderungen erfüllen, die von gestellt werden ForwardIteratorist der Vergleich von Iteratoren aus verschiedenen Containern nicht definiert.

Das LWG-Ausgabe Nr. 446 spricht speziell über diese Frage, und der Vorschlag war, den folgenden Text zum Standard hinzuzufügen (danke an @Lightness Races in Orbit für die Aufmerksamkeit):

Das Ergebnis der direkten oder indirekten Auswertung einer beliebigen Vergleichsfunktion oder des binären Operators mit zwei Iteratorwerten als Argumente, die aus zwei verschiedenen Bereichen r1 und r2 (einschließlich ihrer Werte nach dem Ende) erhalten wurden. die keine Teilbereiche eines gemeinsamen Bereichs sind, ist undefiniert, sofern nicht ausdrücklich anders beschrieben.

Undefiniertes Verhalten soweit ich weiß. In VS 2010 mit

/*
* to disable iterator checking that complains that the iterators are incompatible (come from * different containers :-)
*/
#define _HAS_ITERATOR_DEBUGGING 0 

std::vector<int> vec1, vec2;

std::vector<int>::iterator it1 = vec1.begin();
std::vector<int>::iterator it2 = vec2.begin();

if (it1 == it2)
{
std::cout << "they are equal!!!"; 
}

Der Gleichheitstest gibt in diesem Fall true zurück :-), da die Container leer sind und das _Ptr-Mitglied der Iteratoren beide nullptr sind.

Wer weiß, vielleicht macht Ihre Implementierung die Dinge anders und der Test würde falsch zurückgeben :-).

BEARBEITEN:

Sehen Liste der aktiven Probleme der C++-Standardbibliothek “446. Gleichheit des Iterators zwischen verschiedenen Containern”. Vielleicht kann jemand in der Norm nachsehen, ob die Änderung übernommen wurde?

Wahrscheinlich nicht, da es auf der Liste der aktiven Probleme steht, also hat Charles Bailey, der dies auch beantwortet hat, recht, dass es sich um ein nicht näher bezeichnetes Verhalten handelt.

Ich denke also, dass sich das Verhalten (zumindest theoretisch) zwischen verschiedenen Implementierungen unterscheiden könnte, und dies ist nur ein Problem.

Die Tatsache, dass bei aktiviertem Iterator-Debugging in der STL-Implementierung, die mit VS-Checks geliefert wird, genau für diesen Fall (Iteratoren aus verschiedenen Containern) vorhanden sind, signalisiert mir zumindest noch einmal, dass solche Vergleiche nach Möglichkeit vermieden werden sollten.

Sie können Iteratoren aus verschiedenen Containern nicht direkt vergleichen. Ein Iterator ist ein Objekt, das die verwendet internen Zustand eines Containers, um ihn zu durchqueren; Es macht einfach keinen Sinn, das Innenleben eines Containers mit einem anderen zu vergleichen.

Wenn jedoch die resultierenden Iteratoren aus container.begin() sind vorhanden, es kann Sinnvoll ist es, Iteratoren anhand der Anzahl der durchlaufenen Objekte zu vergleichen begin() auf den aktuellen Iteratorwert. Dies geschieht mit std::distance:

int a = std::distance(containerA.begin(), iteratorA);
int b = std::distance(containerB.begin(), iteratorB);

if (a <comparison> b)
{ /* ... */ }

Ohne mehr Kontext ist es schwierig zu beurteilen, ob dies Ihr Problem lösen würde oder nicht. YMMV.

Nein. Wenn es legal wäre, würde dies bedeuten, dass Zeiger keine Iteratoren wären.

Ich glaube, dass es sich um nicht spezifiziertes Verhalten handelt (C++03). std::vector Iteratoren sind Iteratoren mit wahlfreiem Zugriff und das Verhalten von == ist in den Anforderungen für Forward-Iteratoren definiert.

== ist eine Äquivalenzrelation

Beachten Sie, dass dies eine Anforderung für einen Typ ist und daher (in diesem Fall) auf jedes gültige Paar (dereferenzierbar oder anderweitig) anwendbar sein muss. std::vector::iterators. Ich glaube, das bedeutet == muss dir ein geben true/false Antwort und kann UB nicht verursachen.

— Wenn a und b gleich sind, dann sind entweder a und b beide dereferenzierbar oder beide sind nicht dereferenzierbar.

Umgekehrt kann ein dereferenzierbarer Iterator nicht mit einem nicht dereferenzierbaren Iterator verglichen werden.

— Wenn a und b beide dereferenzierbar sind, dann a == b genau dann, wenn *a und *b dasselbe Objekt sind.

Beachten Sie die fehlende Anforderung, ob a == b für zwei Iteratoren, die nicht dereferenzierbar sind. So lange wie == ist transitiv (falls a.end() == b.end() und b.end() == c.end() dann a.end() == c.end()), reflexiv (a.end() == a.end()) und symmetrisch (ggf a.end() == b.end() dann b.end() == a.end()) egal ob einige, alle oder keine end() Iteratoren für verschiedene Container sind gleich.

Beachten Sie auch, dass dies im Gegensatz zu steht <. < ist definiert in Bezug auf b - awo a und b sind beide Iteratoren mit wahlfreiem Zugriff. Eine Voraussetzung für die Leistung b - a ist, dass es eine geben muss Distance Wert n so dass a + n == b welches benötigt a und b um Iteratoren in denselben Bereich zu sein.

ISO/IEC 14882:2003(E) 5.10.1

Die Operatoren == (gleich) und != (ungleich) haben dieselben semantischen Einschränkungen, Konvertierungen und Ergebnistypen wie die relationalen Operatoren, mit Ausnahme ihrer niedrigeren Priorität und ihres Wahrheitswertergebnisses. [ .. ] Zeiger auf Objekte oder Funktionen des gleichen Typs (nach Zeigerkonvertierungen) können auf Gleichheit verglichen werden. Zwei Zeiger desselben Typs sind genau dann gleich, wenn sie beide null sind, beide auf dieselbe Funktion zeigen oder beide dieselbe Adresse darstellen (3.9.2).

Simulationsergebnisse auf XCode (3.2.3):

#include <iostream>
#include <vector>

int main()
{
    std::vector <int> a,aa;
    std::vector <float> b;

    if( a.begin() == aa.begin() )
        std::cout << "\n a.begin() == aa.begin() \n" ;

    a.push_back(10) ;

    if( a.begin() != aa.begin() )
        std::cout << "\n After push back a.begin() != aa.begin() \n" ;

    // Error if( a.begin() == b.begin() )   

    return 0;
}

Ausgabe :

a.begin() == aa.begin()
Nach dem Zurückschieben a.begin() != aa.begin()

Ich bekomme die Anforderungen an Eingabe-Iteratoren nicht aus dem Standard 100%, aber von da an (Forward/Bidirektional/Random Access Iterators) gibt es keine Anforderungen an die Domäne von ==, also muss es sein falsch zurückgeben ergeben eine Äquivalenzrelation. Sie können jedoch keine < oder > oder Subtraktionen für Iteratoren aus verschiedenen Containern ausführen.

Bearbeiten: Es muss nicht falsch zurückgegeben werden, es muss zu einer Äquivalenzbeziehung führen, dies ermöglicht .begin() von zwei leeren Behältern gleich zu vergleichen (wie in einer anderen Antwort gezeigt). Wenn die Iteratoren dereferenzierbar sind, a == b => *a == *b muss halten. Es ist immer noch kein undefiniertes Verhalten.