C++

Iteratoren: Der Klebstoff der STL

Verstehe Iterator-Kategorien, von Input-Iteratoren bis zu zusammenhängenden Iteratoren. Lerne Iterator-Arithmetik, die begin/end-Konvention und wie Iteratoren Container mit Algorithmen verbinden.

Die Iterator-Abstraktion

Iteratoren sind der Klebstoff zwischen STL-Containern und Algorithmen. Anstatt N Algorithmen für M Container zu schreiben (N*M Implementierungen), definiert die STL eine gemeinsame Iterator-Schnittstelle. Jeder Container stellt Iteratoren bereit, und jeder Algorithmus arbeitet mit Iterator-Bereichen — was N+M Implementierungen ergibt, die zusammenarbeiten.

Ein Iterator ist ein Objekt, das:
1. Auf ein Element in einer Sequenz zeigt
2. Dereferenziert werden kann (*it), um auf das Element zuzugreifen
3. Inkrementiert werden kann (++it), um zum nächsten Element zu gelangen
4. Verglichen werden kann (it != end), um das Ende der Sequenz zu erkennen

Verschiedene Iterator-Kategorien unterstützen unterschiedliche Operationsmengen und bilden eine Hierarchie vom schwächsten zum stärksten.

Iterator-Kategorien

Die C++-Iterator-Kategorien bilden eine Hierarchie (jede Ebene umfasst die Fähigkeiten aller darunter liegenden Ebenen):

| Kategorie | Operationen | Beispiel-Container |
|---|---|---|
| Input | Lesen, einmaliges Vorwärtsdurchlaufen (++, *, ==) | istream_iterator |
| Output | Schreiben, einmaliges Vorwärtsdurchlaufen (++, *=) | ostream_iterator, back_inserter |
| Forward | Lesen/Schreiben, mehrfaches Vorwärtsdurchlaufen | forward_list, unordered_set |
| Bidirectional | Forward + rückwärts (--) | list, set, map |
| Random Access | Bidirectional + Sprünge (+n, -n, [], <) | deque |
| Contiguous (C++17) | Random Access + Elemente sind im Speicher benachbart | vector, array, string |

Algorithmen deklarieren die minimale Kategorie, die sie erfordern. std::sort braucht Random-Access-Iteratoren, funktioniert also mit vector, aber nicht mit list (die eine eigene sort()-Memberfunktion bereitstellt).

Die begin/end-Konvention

Jeder STL-Container stellt begin() und end() bereit — einen halboffenen Bereich [begin, end), wobei end auf ein Element nach dem letzten zeigt. Die freien Funktionen std::begin() und std::end() funktionieren mit Containern, C-Arrays und jedem Typ, der .begin() und .end() als Member bietet.

begin_end.cpp
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};

    // Member functions
    auto first = vec.begin();   // points to 5
    auto last  = vec.end();     // points past 2

    // Free functions — preferred for generic code
    auto first2 = std::begin(vec);
    auto last2  = std::end(vec);

    // Works with C-arrays too
    int arr[] = {10, 20, 30};
    std::sort(std::begin(arr), std::end(arr));

    // const iterators — read-only access
    auto cit = vec.cbegin();     // const_iterator
    // *cit = 99;                // ERROR: cannot modify through const_iterator

    // Reverse iterators — iterate backward
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << ' ';  // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
    }
    std::cout << '\n';
}

Iterator-Hilfsfunktionen: next, prev, advance, distance

Der -Header stellt Hilfsfunktionen bereit, die mit allen Iterator-Kategorien funktionieren und automatisch die effizienteste Implementierung wählen.

iterator_utils.cpp
#include <iterator>
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // std::next — returns iterator n positions forward (default 1)
    auto it = std::next(vec.begin(), 2);   // points to 30
    std::cout << *it << '\n';              // 30

    // std::prev — returns iterator n positions backward
    auto it2 = std::prev(vec.end());       // points to 50
    std::cout << *it2 << '\n';             // 50

    // std::advance — modifies iterator in place (no return)
    auto it3 = vec.begin();
    std::advance(it3, 3);                  // now points to 40
    std::cout << *it3 << '\n';             // 40

    // std::distance — number of increments from first to last
    auto d = std::distance(vec.begin(), vec.end());  // 5
    std::cout << "Distance: " << d << '\n';

    // These work with non-random-access iterators too
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = std::next(lst.begin(), 2);  // O(n) for list, O(1) for vector
    std::cout << *lit << '\n';             // 3

    auto ld = std::distance(lst.begin(), lst.end());  // O(n) for list
    std::cout << "List distance: " << ld << '\n';     // 5
}

Einfüge-Iteratoren und Stream-Iteratoren

Einfüge-Iteratoren ermöglichen es Algorithmen, in Container einzufügen, anstatt bestehende Elemente zu überschreiben. Stream-Iteratoren passen E/A-Streams an die Iterator-Schnittstelle an.

insert_stream_iterators.cpp
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;

    // back_inserter — calls push_back on each assignment
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (works with deque, list)
    // inserter — calls insert at a given position

    // ostream_iterator — write to an output stream
    std::copy(dst.begin(), dst.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';  // 1, 2, 3, 4, 5,

    // istream_iterator — read from an input stream
    std::istringstream iss("10 20 30 40");
    std::vector<int> from_stream(
        std::istream_iterator<int>(iss),
        std::istream_iterator<int>()   // end-of-stream sentinel
    );
    // from_stream: {10, 20, 30, 40}
}
Stolperfalle

Einen Iterator über end() hinaus zu inkrementieren oder vor begin() zu dekrementieren ist undefiniertes Verhalten. Dasselbe gilt für das Dereferenzieren von end() — es ist ein Sentinel, kein gültiges Element.

Ein häufiger Fehler ist it + 1 zu schreiben, ohne zu prüfen, ob it bereits am oder nahe am Ende ist:

auto it = vec.end();
++it;    // UB -- über das Ende hinaus
*it;     // UB -- end() dereferenzieren

Prüfe immer die Iterator-Gültigkeit vor Operationen. Verwende std::next und std::prev mit Abstandsprüfungen, oder verwende Range-basierte for-Schleifen, die Grenzen automatisch behandeln.

Best Practice

Beim Schreiben generischer Funktionen, die auf Sequenzen operieren:

1. Akzeptiere Iterator-Paare (oder Ranges in C++20) anstatt spezifischer Container
2. Verwende typename oder auto für den Iterator-Typ
3. Verwende std::distance anstatt Subtraktion (die Random Access erfordert)
4. Verwende std::next/std::prev anstatt +/--Arithmetik
5. In C++20, bevorzuge Concepts, um Iterator-Anforderungen einzuschränken:

template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }

Dies stellt sicher, dass dein Code mit der größten Bandbreite an Containern funktioniert.

Wichtigste Erkenntnisse
  • Iteratoren entkoppeln Container von Algorithmen — das Kerndesignprinzip der STL
  • Es gibt sechs Iterator-Kategorien: Input, Output, Forward, Bidirectional, Random Access, Contiguous
  • Verwende die freien Funktionen std::begin() / std::end() für generischen Code, der mit Containern und C-Arrays funktioniert
  • std::next, std::prev, std::advance, std::distance funktionieren mit allen Iterator-Kategorien
  • Einfüge-Iteratoren (back_inserter, front_inserter, inserter) ermöglichen Algorithmen, Container wachsen zu lassen
  • Niemals end() dereferenzieren oder darüber hinaus inkrementieren — beides ist undefiniertes Verhalten

Quiz — Teste dein Wissen

(15 XP)

1. Welche Iterator-Kategorie erfordert `std::sort`?

2. Was erzeugt `std::back_inserter(vec)`?

3. Was ist die Zeitkomplexität von `std::distance(first, last)` bei einer `std::list`?

Zurück
Container-Adapter & spezielle Container
Weiter
STL-Algorithmen: Die Kraft von <algorithm>