Wie hängen Iteratoren und Zeiger zusammen?

Question

Code mit Iteratoren ähnelt Code mit Zeigern. Iteratoren sind von irgendeinem obskuren Typ (wie std::vector<int>::iterator zum Beispiel).

Was ich nicht verstehe, ist, wie Iteratoren und Zeiger zueinander in Beziehung stehen - ist ein Iterator ein Wrapper um einen Zeiger mit überladenen Operationen, um zu benachbarten Elementen vorzudringen oder ist es etwas anderes?

Answer 1

Iteratoren sind eine Verallgemeinerung von Zeigern.

Ein Iterator (abhängig von den Varianten) haben zu implementieren * und ++

So ein Zeiger ist ein Iterator. Aber nicht unbedingt umgekehrt.

Wenn Sie über eine komplexe Struktur (ein Baum, ein Diagramm ...) iterieren möchten, ist der Iterator viel mehr als ein Zeiger und bezieht sich nicht auf eine tatsächliche Stelle im RAM.

Answer 2

Konzeptionell ja - aber sie müssen keine Zeiger sein. Ihre Interna und Fähigkeiten hängen von der Datenstruktur ab, die sie "umhüllen".

Deshalb gibt es verschiedene "classes" of iterators. Z.B. Unidirektional, Bidirektional, RandomAccess usw.

Einige sind zu mehreren Klassen fähig.

z. Wenn die interne Struktur eine Rot-Schwarz-Struktur oder eine Verknüpfte Liste ist, sind die Iteratoren möglicherweise Bidirektional, aber nicht RandomAccess. Wenn sie einen Vektor umschließen (als Array implementiert), haben Sie RandomAccess und Bidirektional.

Answer 3

Iteratoren sind Objekte, die bestimmte Operatoren überladen, so dass die Verwendung wie Zeiger aussehen würde. Das gehört zu den Fähigkeiten einer bestimmten Iterator-Kategorie. Random Access-Iteratoren sehen vollständig wie Zeiger aus, andere Arten von Iteratoren stellen keine Operationen bereit (z. B. list<X>::iterator, die bidirektional ist, hat keinen Operator += unter vielen anderen, die einen wahlfreien Zugriff erfordern würden).

In Bezug auf den „obskuren Namen“, ist es nicht völlig undenkbar ist, einen einfachen Zeiger für einen Iterator zu verwenden:

template <class T> 
class MyContainer 
{ 
    ... 
    typedef T* iterator; 
} 

MyContainer<int>::iterator it; //the type is really int* 

Answer 4

Ein Iterator ist nur ein Konzept, das die Schnittstelle für Iteratoren erforderlich bietet - das ist unterschiedliches für die verschiedenen Arten von Iteratoren und sind in Abschnitt 24.1 des C++ - Standards (Iterator-Anforderungen) angegeben. Wie Iteratoren implementiert werden, hängt davon ab, was sie iterieren - für Vektoren sind sie gewöhnlich ein Wrapper um einen einzelnen Zeiger auf ein Array (in Release-Builds sowieso), für komplexere Container haben sie eine kompliziertere Implementierung. Für offene Bereiche enthalten sie den Zustand des Algorithmus, der zur Erzeugung der Elemente verwendet wird.

Beachten Sie, dass ein Zeiger auf ein Element in einem Array die Anforderungen eines Direktzugriffs-Iterators erfüllt, so dass sie in gewissem Maße austauschbar sind.