Container

Container (Behälterklassen) sind Objekte, die andere Datentypen und Objekte speichern, zum Beispiel Listen und Felder. Zum Zugriff auf die einzelnen Elemente werden vom Container Methoden und Iteratoren zur Verfügung gestellt. Der Container kümmert sich um die Speicherverwaltung für die Elemente und hat deswegen Funktionen zum Einfügen und Löschen von Elementen. Der Container besitzt die Elemente. Das bedeutet, dass die Lebenszeit eines gespeicherten Objekts nicht die Lebenszeit der Liste übersteigt. Wenn der Inhalt danach benötigt wird, muss der Benutzer entweder Kopien davon erstellen oder selbst allokierte Pointer verwenden.

In sequenziellen Containern sind die Objekte linear angeordnet. In assoziativen Containern erfolgt der Zugriff mit Hilfe von Schlüsseln.

Sequenzielle Container

Name	Klassenname	Beschreibung	Verfügbar seit
Felder dynamischer Größe, Vector	std::vector	Einfügen und Löschen am Ende ist in ${\displaystyle {\mathcal {O}}(1)}$ und für anderen Elemente in ${\displaystyle {\mathcal {O}}(n)}$ möglich. Der Container unterstützt wahlfreien Zugriff (Random Access) in ${\displaystyle {\mathcal {O}}(1)}$.
Felder fester Größe	std::array	Die Größe muss bereits während des Kompiliervorgangs feststehen.	C++11
doppelt verkettete Listen	std::list	Einfügen und Löschen ist in ${\displaystyle {\mathcal {O}}(1)}$ möglich. Wahlfreier Zugriff ist nicht möglich.
einfach verkettete Listen	std::forward_list	Einfügen und Löschen ist in ${\displaystyle {\mathcal {O}}(1)}$ möglich. Wahlfreier Zugriff und Grössenabfrage sind nicht möglich.	C++11
Warteschlangen	std::queue	Der Container unterstützt keine Iteratoren.
Warteschlangen mit zwei Enden	std::deque	Der Datentyp verhält sich wie der Vector, kann jedoch Elemente am Anfang und Ende in ${\displaystyle {\mathcal {O}}(1)}$ einfügen.
Warteschlangen mit Prioritäten	std::priority_queue	Die Struktur garantiert wie der Heap, dass immer das Element mit der höchsten Priorität am Beginn steht.
Stapel	std::stack	Der Container unterstützt keine Iteratoren.

Iteratoren

Iteratoren (von lateinisch iterare: wiederholen) sind intelligente Zeiger, mit deren Hilfe über die Elemente eines Containers iteriert sowie auf einzelne Elemente des Containers zugegriffen werden kann. Die Iteratoren bilden ein zentrales Konzept für die Container. Bezogen auf ihre Aufgabe sind die Iteratoren reine Zugriffsobjekte. Sie entkoppeln Algorithmen von den Containern, so dass Algorithmen unabhängig von Containertypen formuliert werden können. Das nachfolgende Diagramm zeigt das Verhältnis des Iterators zu den Containern und Algorithmen:

Bei den Iteratoren gibt es folgende Kategorien:

• Eingabe-Iteratoren: lesender Zugriff für einen einzelnen Durchlauf
• Ausgabe-Iteratoren: schreibender Zugriff für einen einzelnen Durchlauf
• Forward-Iteratoren: sequenzieller Zugriff mit relativem Bezug auf Iteratoren, in eine Richtung
• Bidirektionale Iteratoren: wie Forward-Iteratoren jedoch in beide Richtungen
• Iteratoren mit wahlfreiem Zugriff: wahlfreier Zugriff, auch mit Index-Operator ([])

Dabei stellt nicht jeder Container alle Iteratoren zur Verfügung. Der list-Container lässt z. B. keinen wahlfreien, sondern nur sequenziellen Zugriff zu. Die Ein- und Ausgabe-Iteratoren sind dagegen sehr allgemein und werden grundsätzlich bereitgestellt.

Algorithmen

Algorithmen sind Funktionen mit bestimmten Manipulationsvorschriften, die auf einen Container angewendet werden. Dabei sind sie unabhängig von der speziellen Implementierung der Container. Sie können nur über Iteratoren auf die Elemente in den Containern zugreifen. Sie enthalten u. a. die Standard-Algorithmen der Informatik, wie z. B. Sortieralgorithmen oder Verfahren zur Erzeugung von Zufallszahlen. Die meistbenutzten sind:

• std::for_each: wendet eine Operation auf alle Elemente eines Datensatzes an
• std::transform: transformiert einen Datensatz mit einer Funktion in einen anderen
• std::copy: kopiert den Datensatz in einen anderen
• std::sort: sortiert den Datensatz
• std::find: sucht nach einem bestimmten Element in einem Datensatz
• std::search: sucht nach einer Elementreihe in einem Datensatz

Diese und weitere Algorithmen befinden sich im Header <algorithm>.

Funktionsobjekte

Bei Funktionsobjekten oder Funktoren handelt es sich um Objekte, die als Funktion aufgerufen werden können. Hierbei wird der Funktionsoperator „operator()“ überladen. Bei den Funktionsobjekten gibt es folgende Kategorien:

• Generatoren ohne Funktionsparameter „f()“
• Unäre Funktionen mit einem Funktionsparameter „f(x)“
• Binäre Funktionen mit zwei Funktionsparametern „f(x,y)“

Grundsätzlich benötigen die Algorithmen der C++-Standardbibliothek keine Funktionsobjekte mit mehr als zwei Parametern.

Zeichenketten

Die Zeichenketten-Bibliothek definiert ein Klassen-Template std::basic_string zur Darstellung von Zeichenketten (engl.: "strings") variabler Länge. Die Methoden des Klassen-Templates bieten Manipulationen und Operationen, wie z. B. das Einfügen, Löschen, Ersetzen und Suchen in Zeichenketten. Von diesem Klassen-Template gibt es zwei Typdefinitionen:

• std::string ist eine Instanziierung von std::basic_string, parametrisiert mit char. char kann ein Zeichen des Basiszeichensatzes speichern.
• std::wstring ist eine Instanziierung von std::basic_string, parametrisiert mit wchar_t (wide character). wchar_t kann alle Elemente des größten unterstützten Zeichensatzes speichern.