C++ Iteratoren [C++ Reference]

- C++ Iteratoren

C++ Iteratoren

Iteratoren werden zum Zugriff auf die Elemente einer Folge verwendet, und können auf gleiche Weise wie Zeiger benutzt werden.
Zum Beispiel kann man einen Iterator verwenden um durch die Elemente eines Vektors zu gehen.

Der folgende Code erzeugt und benutzt einen Iterator mit einem Vektor:

    vector<int> the_vector;
    vector<int>::iterator the_iterator;
 
    for( int i=0; i < 10; i++ ) the_vector.push_back(i);
    int total = 0;
    the_iterator = the_vector.begin();
    while( the_iterator != the_vector.end() ) {
      total += *the_iterator;
      ++the_iterator;
    }
 
    cout << "Total=" << total << endl;

Man beachte das auf die Elemente des Containers durch Dereferenzierung des Iterators zugegriffen werden kann.

HINWEIS: Man sollte den Pre-Increment-Operator (++iter) dem Post-Increment-Operator (iter++)
vorziehen, wenn man den alten Wert nicht verwenden möchte.
Post-Increment ist im Allgemeine wie folgt implementiert:

  Iter operator++(int)
  {
    Iter tmp(*this); // store the old value in a temporary object
    ++*this;         // call pre-increment
    return tmp;      // return the old value
  }

Offensichtlich ist das weniger effizient als Pre-Increment.

Iterator-Kategorien

Nicht jede Art von Iteratoren hat exakt die gleichen Fähigkeiten. Lesen und Schreiben benötigt unterschiedliche Fähigkeiten.
Willkürlicher Zugriff ist für einen vector effizient und geeignet, für eine list hingegen aufwendig.
Aus diesem Grund werden Iteratoren nach ihren Fähigkeiten in fünf Kategorien eingeteilt:

Iterator-Kategorie	Beschreibung	Anbieter
input_iterator	Liest Werte mit Vorwärtsbewegung. Sie können inkrementiert, verglichen und dereferenziert werden.	istream
output_iterator	Schreibt Werte mit Vorwärtsbewegung. Sie können inkrementiert, verglichen und dereferenziert werden.	ostream, inserter
forward_iterator	Liest oder schreibt Werte mit Vorwärtsbewegung. Sie kombinieren die Funktionen der Input- und Output-Iteratoren mit der Fähigkeit den Wert des Iterators zu speichern.
bidirectional_iterator	Liest und schreibt Werte mit Vorwärts- und Rückwärtsbewegung. Sie sind wie Vorwärts-Iteratoren, aber man kann sie in- und dekrementieren	list, map, multimap, set, multiset
random_access_iterator	Liest und Schreibt Werte in willkürlicher Reihenfolge. Sie sind die leistungsfähigsten Iteratoren und kombinieren die Funktionen der Bidirektionalen-Iteratoren mit der Fähigkeit Zeiger-Arithmetik und Zeiger-Vergleiche durchzuführen.	array, deque, string, vector

Jeder der STL Container ist mit einer Iterator-Kategorie verknüpft, und jeder der STL Algorithmen verwendet bestimmte Kategorien von Iteratoren.

Zum Beispiel sind Vektoren mit Random-Access-Iteratoren verknüpft, was bedeutet, dass sie Algorithmen verwenden können, die willkürlichen Zugriff ermöglichen. Da Random-Access-Iteratoren alle charakteristischen Eigenschaften der anderen Iteratoren umfassen, könne Vektoren auch Algorithmen verwenden, die für andere Iteratoren entwickelt wurden.

    vector<int> the_vector(10);
 
    // generate_n requires output_iterator
    generate_n(the_vector.begin(), 5, rand);
 
    // fill requires forward_iterator
    fill(the_vector.begin()+5, the_vector.end(), 100);
 
    // random_shuffle requires random_access_iterator
    random_shuffle(the_vector.begin(), the_vector.end());
 
    // copy requires input_iterator
    copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));
 
    // reverse_copy requires bidirectional_iterator
    reverse_copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));

Iterator-Hilfsfunktionen

Die <iterator> Header-Datei definiert zwei Hilfsfunktionen.

  void advance( input_iterator& pos, Dist n );

advance() setzt den Iterator pos um n Schritte vorwärts (oder rückwärts).
Für Bidirektionale- und Random-Access-Iteratoren kann n negativ sein, um rückwärts zu schreiten.
Für Random-Access-Iteratoren benötigt advance() eine konstante Laufzeit (einfache Ausführung von pos+=n).
Für alle anderen Iteratoren hat advance() lineare Komplexität (Ausführung von ++pos n mal).

  typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );

distance() gibt den Abstand zwischen zwei Iteratoren zurück.
Für Random-Access-Iteratoren benötigt distance() eine konstante Laufzeit (es wird einfach pos2 - pos1 zurückgegeben).
Für alle anderen Iteratoren hat distance() lineare Komplexität (pos1 wird erhöht bis pos2 erreicht ist, und die Anzahl der Erhöhungen wird zurückgegeben).

Ungültige Iteratoren

Iteratoren zu existierenden Elementen in einem Container können ungültig werden wenn der Container gewechselt wird. Das macht es problematisch den Conatainer während dem Iterieren zu wechseln. Die Container bieten in dieser Hinsicht verschiedene Garantien:
- vectors: Einfügen/Entfernen von Elementen kann alle Iteratoren ungültig machen.
- list/map: Entfernen macht nur Iteratoren zum entfernten Element ungültig und keine Anderen.