Von Containern und anderen flexiblen Konzepten

Als Einstieg in die C++-Standardbibliothek soll die Container-Library dienen. Diese Sammlung von Datenstrukturen bietet für fast jeden Anwendungsfall ein passendes Klassentemplate. Hier leuchten die Iteratoren nochmal hell auf. Sie ermöglichen die flexible Verbindung von Containern mit Algorithmen und bieten so eine hohe Wiederverwendung innerhalb der Bibliothek an. Wir fangen an mit std::list und std::vector, die mittels Iteratoren mit einem kleinen Algorithmus auf der Konsole ausgegeben werden können.

Video

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <vector>
#include <list>
 
template <typename IteratorT> void printValues(IteratorT const start, IteratorT const end)
{
    for (IteratorT i=start; i != end; ++i) {
        std::cerr << *i << std::endl;
    }
}
 
int main()
{
    std::vector<int> v;
    v.push_back(2);
    v.push_back(7);
    v.push_back(4);
 
    printValues(v.begin(), v.end());
     
    std::list<std::string> l;
    l.push_back("Eins");
    l.push_back("Zwo");
    l.push_back("Drei");
     
    printValues(l.begin(), l.end());
}

Erklärung

Nicht viel Quellcode und das ist auch beabsichtigt: wir wollen ja gerade die Bibliothek verwenden, statt alles zu Fuß zu schreiben. Die beiden Container, die hier vorgestellt sind, unterscheiden sich doch deutlich in ihrem internen Aufbau. std::vector ist im Prinzip ein Array auf Steroiden: es vergrößert und verkleinert sich automatisch bei Bedarf, kann wahlfrei zugegriffen werden und ist typsicher. Anhängen ans Ende ist amortisiert O(1), in der Mitte allerdings O(n). Dafür ist der wahlfreie Zugriff O(1). std::list hingegen ist eine zweifach verkettete Liste. Die Elemente liegen nicht im Speicher hintereinander, sondern werden durch Zeiger verkettet (davon sieht der Nutzer der Klasse allerdings nichts). Einfügen und Löschen sind O(1), dafür ist der wahlfreie Zugriff O(n) (und kann nicht über einen Index erfolgen, wie beim std::vector).

Beide Datenstrukturen bieten geeignete Iteratoren, die sich in die von C++ vorgegebenen Konzepte einfügen. Für std::vector steht ein Random Access Iterator zur Verfügung, std::list bietet einen Bidirectional Iterator. Beide lassen sich daher einfach mit unserem Algorithmus zur Ausgabe eines Datenbereiches verbinden. Die Funktion printValues verlangt zwei Iteratoren als Parameter: einen Start-Iterator und einen Ende-Iterator. Die Funktion hält sich dabei an das Design der Standardbibliothek: der Bereich ist immer [start, ende), d.h. der Ende-Iterator ist immer das erste Element, welches nicht mehr zum Bereich gehört. Jeder C++-Container stellt diese beiden Iteratoren zur Verfügung: die Funktion begin() liefert den Anfang eines Containers, end() liefert das Element hinter dem Ende des Containers.

Unsere Ausgabefunktion hat nun nur noch etwas ganz einfaches zu tun: sie zählt einen Iterator i solange hoch, wie er ungleich dem Ende-Iterator ist. Dieses Muster tritt in C++-Programmen sehr häufig auf, weswegen es auch gleich zu Anfang mal vorgestellt werden soll. Wenn wir uns die Anforderungen an den Iterator anschauen, so ist klar, dass die Funktion einen Input-Iterator verlangt (dier Vergleich machts. Ohne den würde es auch ein normaler Iterator tun. Da wir nicht mehrfach durch den Bereich laufen, brauchen wir die entsprechende Fähigkeit des Forward Iterator nicht. Es genügt also ein Input-Iterator.) Um an die Daten ranzukommen, die sie ausgeben muss, muss die Funktion den Iterator nur dereferenzieren. Ob der nun ursprünglich aus einem std::vector kommt oder eine std::list die Quelle war oder jemand einen völlig eigenen Iteratortyp geschrieben hat, ist hier unerheblich.