Container Klassen

Überblick/Einführung

Container sind Klassen zur Aufnahme von Objekten beliebigen Typs mit Funktionen zum Einfügen, Löschen und Verwalten dieser Objekte. Verschiedene Container unterscheiden sich in der Art und Weise, wie die Objekte zueinander arrangiert sind, ob die Elemente sortiert sind, und wie der Zugriff auf die einzelnen Elemente erfolgt. In den Container-Bibliotheken sind häufig gebrauchte Datenstrukturen als Template-Klassen implementiert, die beliebige Datentypen in sich aufnehmen können.

Man unterscheidet folgende grundsätzliche Typen:

In Tabelle Tabelle 5.1 finden Sie eine Übersicht der zur Verfügung gestellten Container. Im Praktikum verwenden wir nur die Containertypen vector, list, array und map und Iteratoren um auf die Container zuzugreifen, auf die wir in den weiteren Abschnitten näher eingehen.

Die Benutzung der Container gestaltet sich durch die gemeinsamen Funktionen sehr einfach. Die wichtigsten Funktionen sind:

Der Zugriff auf die gespeicherten Daten erfolgt meist über Iteratoren. Der Iterator ist ein Zeiger innerhalb der Container und kann mit ++ und -- vor- und rückwärts bewegt werden. Die Funktion begin() liefert einen Iterator auf das erste Element der Liste. Das Ende der Liste kann durch die Funktion end() abgefragt werden. Mehr dazu im entsprechenden Abschnitt Iteratoren

Container

Beschreibung

Sequentielle Container

array Statische, lineare Speicherung
Schnelle Iteration
vector Lineare, benachbarte Speicherung
schnelles Einfügen nur am Ende
deque Lineare, benachbarte Speicherung
schnelles Einfügen an Außenstellen
forward_list Einseitig verkettete Liste
schnelles Einfügen an beliebigen Stellen
list Beidseitig verkettete Liste
schnelles Einfügen an beliebigen Stellen

Assoziative Container

multiset Datenmenge, schneller assoziativer Zugriff
Duplikate zulässig
set Wie multiset, jedoch keine Duplikate zulässig
multimap Menge von Schlüssel/Wert-Paaren
schneller Zugriff über Schlüssel
Duplikate für Schlüssel zulässig
map Wie multimap, jedoch keine Duplikate für Schlüssel zulässig

Ungeordnete assoziative Container

unordered_multiset Datenmenge, schneller assoziativer Zugriff
Duplikate zulässig
unordered_set Wie unordered_multiset, jedoch keine Duplikate zulässig
unordered_multimap Menge von Schlüssel/Wert-Paaren
schneller Zugriff über Schlüssel
Duplikate für Schlüssel zulässig
unordered_map Wie unordered_multimap, jedoch keine Duplikation für Schlüssel zulässig

Adapter

stack first-in-last-out (FILO) Datenstruktur (Stapel)
queue first-in-first-out (FIFO) Datenstruktur (Warteschlange)
priority_queue Queue, die Elemente mit Priorität speichert und so die Reihenfolge des Zugriffs bestimmt
Tabelle 5.1: Containerklassen in der Übersicht

std::vector

Die Größe eines vector kann sich während der Ausführung des Programmes bei Bedarf ändern. Dazu kann z.B. mit push_back(Element) ein Element hinten angehängt werden oder mit pop_back() das letzte Element abgerufen und aus dem Vektor entfernt werden. Definiert ist der Vektor im Header <vector>.

Wie oben schon beschrieben handelt es sich hierbei um einen sequenziellen Container, dessen Größe sich nach Bedarf anpassen lässt:

vector<int> feld;

oder um eine Anfangsgröße des Vektors festzulegen, die später noch änderbar ist:

vector<int> feld(5);

Auch ein Initialwert kann bei der Definition direkt mitgegeben werden, z.B. 3 float-Elemente mit dem Wert -1:

vector<float> feld(3, -1.0);

Für den Zugriff auf Elemente stehen einige Methoden in Tabelle 5.2 zur Verfügung. Für eine vollständige Übersicht sei auch hier wieder auf die empfohlene Literatur verwiesen.

Funktionen

Funktionalität

size_type size()const Liefert die Anzahl der Elemente
void swap(vector& vec) Tauscht den Inhalt mit dem von vec
void push_back(const T& val) Fügt val am Ende des Vektors ein
void insert(iterator pos, const T& val) Fügt val an der Stelle pos innerhalb des Vektors ein
void pop_back() Löscht das letzte Element im Vektor
Tabelle 5.2: Einige Funktionen von vector (Anmerkung: T steht in der Tabelle für beliebige Datentypen)

Es ist möglich, einen Vektor direkt einem anderen zuzuweisen (= -Operator) und zwei Vektoren auf Gleichheit zu testen (== -Operator). Für Gleichheit müssen beiden Vektoren gleich groß sein und alle Elemente übereinstimmen.

Ein ausführbares und veränderbares Beispiel:

#include <vector>
#include <iostream>
{
    std::vector<int> v1 = {0, 1, 2};
    int i;
    
    std::cout << "Der ursprüngliche Vektor: ";
    for(auto i: v1){
        std::cout << i << ' '; //Ausgabe: 0 1 2
    }
    std::cout << std::endl;
    
    v1.pop_back();
    
    std::cout << "Das letzte Element wurde nun gelöscht: ";
    for(auto i: v1){
        std::cout << i << ' '; //Ausgabe 0 1 
    }
    std::cout << std::endl;
    
    v1.push_back(5);
    v1.insert(v1.begin(),6);
    
    std::cout << "Mit den beiden vorne und hinten angehängten Zahlen sieht unser Vektor jetzt so aus: ";
    for(auto i: v1){
        std::cout << i << ' '; //Ausgabe 6 0 1 5
    }
    std::cout << std::endl;
}

std::list

Eine Liste ist ein sequentieller Container, der für Einfügen und Löschen gut geeignet ist. Dafür ist die Iteration langsamer und eine Liste bietet keinen direkten Zugriff üer Index. Sie ist in <list> definiert.

Die Definition einer Liste erfolgt, z.B. für eine Liste mit string-Elementen, durch:

#include <list>
#include <string>

std::list<std::string> meineListe;

Eine Liste besitzt die gleichen Memberfunktionen zum Erweitern, Löschen und Abfragen der Größe wie ein Vektor. Um Elemente in die Liste einzufügen oder zu löschen stehen zusätzlich die Funktionen insert(pos,Element) und erase(pos) zur Verfügung (für eine kurze Übersicht einiger Funktionen, siehe Tabelle 5.3). Diese Funktionen existieren zwar auch für Vektoren, führen dort aber zur Verschiebungen des gesamten Vektors und machen alle Iteratoren ungültig, die sich auf Elemente hinter der Einfüge-/Löschposition beziehen. Sie sind also dort nur in Sonderfällen einsetzbar, bei der Liste aber sinnvoll.

Funktionen

Funktionalität

size_type size()const Liefert die aktuelle Anzahl der Elemente
void push_back(const T& val) Fügt val am Ende der Liste ein
void push_front(const T& val) Fügt val am Anfang der Liste ein
void pop_back() Löscht das letzte Element
void pop_front() Löscht das erste Element
void erase(iterator pos) Löscht das Element an der Position pos
iterator insert(iterator post, const T& value) Fügt ein Element an der Stelle pos ein
Tabelle 5.3: Einige Funktionen von list

Zum umgekehrten Durchlaufen der Liste kann man einen reverse-iterator mit den zugehörigen Funktionen rbegin() (letztes Element) und rend() (vor dem erstem Element) benutzen. Entsprechend gibt es auch die umgekehrten push-/pop-Funktionen: push_front(Element) und pop_front(). Mit der Funktion reverse() kann die Reihenfolge der Elemente in der Liste umgekehrt werden. Es ist möglich, eine Liste oder einen Vektor direkt einer anderen Liste zuzuweisen (= -Operator) und zwei Listen auf Gleichheit zu testen (== - Operator). Für Gleichheit müssen die beiden Listen gleich groß sein und alle Elemente (in der richtigen Reihenfolge) übereinstimmen.

Beispiel:

#include <list>
#include <iostream>

{
    std::list<int> l1;
    
    l1.push_back(7);
    
    std::cout << "Die ursprüngliche Liste: ";
    for(int i: l1){
        std::cout << i << ' '; //Ausgabe: 7
    }
    std::cout << std::endl;
    
    l1.insert(l1.begin(), 3);
    std::cout << "Nachdem die 3 vorne angehängt wurde, sieht die Liste so aus: ";
    for(int i: l1){
        std::cout << i << ' '; //Ausgabe: 3 7
    }
    std::cout << std::endl;
    
    l1.insert(l1.end(), 8);
    std::cout << "Nachdem die 8 hinten angehängt wurde, sieht die Liste so aus: ";
    for(int i: l1){
        std::cout << i << ' '; //Ausgabe: 3 7 8
    }
    std::cout << std::endl;
    
    l1.push_front(6);
    std::cout << "Es gibt verschiedene Möglichkeiten, Zahlen vorne anzuhängen: ";
    for(int i: l1){
        std::cout << i << ' '; //Ausgabe: 6 3 7 8
    }
    std::cout << std::endl;
    
    l1.pop_front();
    
    std::cout << "Nach dem Enfernen sieht die Liste nun wieder so aus: ";
    for(int i: l1){
        std::cout << i << ' '; //Ausgabe: 3 7 8
    }
    std::cout << std::endl;
}

Statt ein einzelnes Element in die Liste einzufügen, kann man auch alle Elemente des Intervalls [first, last) einfügen. Der Funktionsaufruf ist dann:

void insert(iterator pos, const_iterator first, const_iterator last)

Der durch first und last bestimmte Teil einer Liste (oder eines Vektors bzw. Arrays) wird an der Position pos eingefügt.

Beispiel:

#include <list>
#include <iostream>
{
    std::list<std::string> list1, list2;
    
    list1.push_back("gelb");
    list1.push_back("blau");
    list1.push_back("rot");
    
    std::cout << "Der Inhalt von list1 sieht so aus: " << std::endl;
    for(const auto& i: list1){
        std::cout << i << ' '; //Ausgabe: gelb blau rot
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    list2.push_front("weiß");
    list2.push_front("lila");
    list2.push_front("schwarz");
    
    std::cout << "Der Inhalt von list2 sieht so aus: " << std::endl;
    for(const auto& i: list2){
        std::cout << i << ' '; //Ausgabe: schwarz lila weiß
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    auto start = (list2.begin())++;
    list1.insert(list1.begin(), start, list2.end());
    
    std::cout << "Die zusammengefügte Liste sieht nun so aus: " << std::endl;
    for(const auto& i: list1){
        std::cout << i << ' '; //Ausgabe: schwarz lila weiß gelb blau rot
    }
    std::cout << std::endl;
    std::cout << std::endl;
    
    list1.erase(list1.begin());
    std::cout << "Der Inhalt von List1 sieht so aus: " << std::endl;
    for(const auto& i: list1){
        std::cout << i << ' ';
    }
    std::cout << std::endl;
}

std::array

Das in der Container-Bibliothek implentierte array ist eine bessere Implementierung der Ihnen eventuell aus C bekannten Felder. Dementsprechend ist std::array den C-Arrays vorzuziehen. Definiert ist array im Header <array> und ist wie folgt deklariert:

template<class T, std::size_t N> 
class array;

Dabei ist T der Typ der Elemente und N die Größe. Die Größe von array muss zur Compile-Zeit vorliegen. Deswegen können können Elemente weder hinzugefügt, noch entfernt werden.

Deklariert wird ein Array z.B. so:

array<int, 42> feld; //ist ein Array namens feld, welches 42 int-Werte speichern kann.

Bei der Initialisierung können Werte gesetzt werden:

array<int, 3> feld = {1, 2, 3}; //ist ein Array, das bereits mit Werten initialisiert wurde.

Für ein array ist sichergestellt, dass alle Elemente hintereinander im Speicher liegen. Dementsprechend kann auf die einzelnen Elemente mit dem []-Operator zugegriffen werden, beginnend für das erste Element mit 0 (bei dem vorherigen Beispiel würde feld[2] den Wert 3 zurückliefern). Zugriffe auf ein Array außerhalb dieser Indizies ist ein Programmierfehler mit undefinierten Auswirkungen. Die Funktion at empfängt die gleichen Argumente wie der []-Operator bei den klassischen C-Arrays, überprüft aber den Wertebereich und wirft im Fehlerfall eine Exception. Auf die Elemente kann auch über Iteratoren zugegriffen werden und mithilfe von size_type size()const kann die Anzahl der Elemente ausgeben werden. Die Funktion void swap(array& ar) tauscht den Inhalt des Arrays mit dem von ar.

Beispiel:

#include <iostream>
#include <array>

{
    std::array<int, 4> arr = {0, 1, 2, 3};
    std::cout << "Inhalt von arr: ";
    for(auto it: arr){
        std::cout << it << " ";  //Ausgabe: 0 1 2 3 
    }
    std::cout << std::endl;
    
    std::array<int, 4> swaparray = {0, 0, 0, 0};
    std::cout << "Inhalt von swaparray: ";
    for(auto it : swaparray){
        std::cout << it << " ";  //Ausgabe: 0 0 0 0
    }
    std::cout << std::endl;
    swaparray.swap(arr);
    
    std::cout << "Der Inhalt von swaparray ist nun: ";
    for(auto it: swaparray){
        std::cout << it << " ";  //Ausgabe: 0 1 2 3 
    }
    std::cout << std::endl;
    
    std::cout << "Und der Inhalt von arr ist jetzt: ";
    for(auto it: arr){
        std::cout << it << " ";  //Ausgabe: 0 0 0 0
    }
    std::cout << std::endl;
}

std::map

Maps sind assoziative Container zur Speicherung von Schlüssel/Wert-Paaren. Sie ermöglichen schnellen Zugriff über den Schlüssel, können aber auch sequentiell durchlaufen werden. Zum schnelleren Zugriff kann man auch unsortierte Maps benutzen. In diesem Zusammenhang bedeutet unsortiert, dass die Schlüssel nicht sortiert abgespeichert werden. Zur einfacheren Darstellung benutzen wir im Praktikum sortierte Maps. Maps sind im Header <map> definiert.

Im Folgenden werden nur einige elementare Eigenschaften der Maps beschrieben. Für weitergehende Informationen sei wieder auf die Literatur verwiesen. Im einfachsten Fall erfolgt die Deklaration einer Map über

map<[Key], [Value]>;

also z.B.:

map<string, int> MapStringInt;

Diese Map enthält int-Zahlen, auf die über strings als Schlüssel zugegriffen wird.

map<long int, Studi> MapStudi;

definiert eine Map, die Studentendaten enthält, auf die über eine long int-Zahl (z.B. Matrikelnummer) zugegriffen wird.

Über den Subskript-Operator operator[] erfolgt der Zugriff mit dem Schlüssel. Wenn noch kein Objekt mit diesem Schlüssel existiert, wird ein leeres Elemtn über den Default-Kontrukstor erstellt (bei einem Pointer ist dies der nullptr) und zurückgegeben. Der Operator gibt eine Referenz auf das Objekt zurück. Auch für die Map gibt es die Alternative at, die, wenn kein Objekt gefunden wurde, eine Exception wirft. die Funktionen begin(), end(), empty() und size() sind analog zu den übrigen Containern auch für Maps definiert.

Maps unterstützen Iteratoren und den =-Operator. Die Dereferenzierung eines Iterators liefert jeweils ein pair-Objekt aus Schlüssel und Wert. Mit firstkann dann auf den Schlüssel und mit second auf den Wert zugegriffen werden. Man beachte, dass dies keine Memberfunktionen, sondern Datenelemente sind und daher ohne () geschrieben werden.

Eine sehr häufige Anwendung der Maps ist die Zuordnung zwischen externen Textschlüsseln auf interne Werte, wie im folgenden Beispiel die Zuordnung von Studierenden zu ihren Matrikelnummern: Beispiel:

#include <map>
#include <iostream>
#include <string>

{
    std::map<long, std::string> studi_map;
    
    studi_map[123123] = "Schmachtenberg";
    studi_map[123456] = "Ruediger";
    studi_map[123321] = "Ulrich";
    
    std::cout << "Die Studierenden mit ihren Matrikelnummern sind: " << std::endl;
    for(const auto& it: studi_map){
        std::cout << it.first << " ";
        std::cout << it.second << std::endl;
    }
}

Die Funktionen erase() und insert() funktionieren analog zu den Funktionen von Listen. Um einen Iterator auf ein bestimmtes Element zu erhalten, existiert die Memberfunktion

Iterator find(Key);

die einen entsprechenden Iterator liefert. Falls dieses Element nicht gefunden wurde, wird ein Iterator auf end() zurückgegeben.

Beispiel:

{
    std::map<std::string, int> numbers;
    
    numbers["eins"] = 1;
    numbers["zwei"] = 2;
    numbers["drei"] = 3;
    
    std::cout << "So sieht die map numbers aus: " << std::endl;
    for(const auto& it: numbers){
        std::cout << it.first << ": " << it.second << std::endl;
    }
    
    auto lookUp1 = numbers.find("eins");
    
    if(lookUp1 != numbers.end()){
        numbers.erase(lookUp1);
    }
    
    std::cout << std::endl;
    std::cout << "Nachdem wir die 1 gelöscht haben, sieht die map so aus: " << std::endl;
    for(const auto& it: numbers){
        std::cout << it.first << ": " << it.second << std::endl;
    }
}

Iteratoren

Iteratoren sind Objekte, die es gestatten, Elemente eines Containers (oder Streams) zu durchlaufen. Definiert sind sie im Header <iterator>. Ein Iterator hat zu jedem Zeitpunkt eine bestimmte Position innerhalb eines Containers, die er so lange beibehält, bis er durch einen neuen Befehlsaufruf versetzt wird. Die Standartbibliothek definiert fünf Kategorien von Iteratoren, die hierarchisch angeordnet sind:

Eine mögliche Durchlaufreihenfolge einer Liste wird an folgendem Bild verdeutlicht:

Iteratorbeispiel.png

            Bild 5.1: Durchlauf einer Liste

Die grundlegenden Operationen eines Iterators sind:

Es sind nur die zusätzlichen Operatoren definiert, die für die jeweilige Containerklasse effizient ausführbar sind (z.B. kein Random-Access-Zugriff für Listen).

Bei Random-Access-Iteratoren sind zusätzlich

definiert.

Iteratoren erhält man als Ergebnis einer entsprechenden Funktion (wie begin(), end() oder find()) oder explizit über eine Deklaration wie:

vector<int>::iterator it1;

Möchten Sie mittels eines Iterators innerhalb einer konstanten Instanzmethode auf einen Container zugreifen, muss auch der Iterator als konstant deklariert werden, etwa:

list<int>::const_iterator it2;

Die Konzepte Datentypableitung (auto) und Range-basierte for-Schleifen sind für Container-Zugriffe mittels Iteratoren ideal geeignet. In den folgenden Beispielen wird dies ersichtlich.

Beispiel (Berechnen einer Summe):

#include <iostream>
#include <vector>
using namespace std;

{
    vector<int> v (3,1); //v: 1 1 1
    v.push_back(7); //v: 1 1 1 7
    int sum = 0;
    cout << "Summe(";
    
    for(auto it: v){ //Elementtyp des Vektors ist int, auto wird durch int ersetzt
        cout << " " << it;
        sum += it;  //Ausgabe: 1 1 1 7
    }
    cout << " ) = " << sum << endl; //Ausgabe: 10
}

Soll der Container rückwärts durchlaufen werden, gibt es verschiedene Möglichkeiten. Die einfachste ist wohl der reverse_iterator. Er ist ebenfalls Teil der <iterator>-Bibliothek und kann beispielsweise so deklariert werden:

vector<int>::reverse_iterator revIt;

reverse_iterator erzeugt einen Iterator, der vom Ende eines Containers zu dem Anfang durch Inkrementierung wandert. Man erhält ihn auch als Ergebnis einer entsprechenden Funktion (rbegin()oder rend()).

Beispiel:

#include <iostream>
#include <iterator>
#include <vector>

{
    std::vector<int> v;
    for(int i = 0; i < 10; ++i){
        v.push_back(i);
    }
    
    std::vector<int>::iterator it;
    std::vector<int>::reverse_iterator revIt;
    
    std::cout << "v wird vorwärts durchlaufen: ";
    for(it = v.begin(); it < v.end(); it++){
        std::cout << *it << " ";  //Ausgabe: 0 1 2 3 4 5 6 7 8 9  
    }
    std::cout << std::endl;
    
    std::cout << "v wird rückwärts durchlaufen: ";
    for(revIt = v.rbegin(); revIt != v.rend(); revIt++){
        std::cout << *revIt << " ";  //Ausgabe: 9 8 7 6 5 4 3 2 1 0
    }
    std::cout << std::endl;
}

Übungsaufgaben zu diesem Kapitel finden Sie hier.