C++ Kurs

Standard-Container II

Die Themen:

Allgemeine Container-Eigenschaften und -Operationen

In diesem und dem nachfolgenden Kapitel werden wir uns erneut mit der C++ Standard Bibliothek befassen und uns weitere Container und Funktionen der Bibliothek sehen. Einige Container haben wir ja bereits in einem früheren Kapitel kennengelernt. Bevor wir auf die restlichen Container im Einzelnen eingehen, werden wir uns zunächst die allen Containern gemeinsamen Eigenschaften und Operationen ansehen.

AchtungDie in einem vorherigen Kapitel eingeführten speziellen Container stack, queue, priority_queue und bitset besitzen nicht alle hier aufgeführten Operationen.
HinweisWir werden uns nur die wichtigsten Eigenschaften und Memberfunktionen der Container ansehen. Wenn Sie weitergehende Informationen über die Standard-Bibliothek und den darin enthaltenen Elemente benötigen, so empfehle ich das Buch 'The C++ Standard Library, A Tutorial and Reference' von Nicolai M. Josuttis.

Gemeinsame Eigenschaften der Container

Folgende Eigenschaften gelten für alle weiteren Bibliotheks-Container:

1. Alle Bibliotheks-Container verwenden die sogenannte Werte-Semantik. D.h. die Container kopieren die in ihnen abzulegenden Elemente. Dies hat u.a. zur Folge, dass nachträgliche Änderungen an den Elementen sich nicht auf die im Container abgelegten Elemente auswirken.

PgmHeader// int-Stack definieren
stack<int> intStack;
// int Variable definieren und initialisieren
int var = 10;
// int Variable auf dem Stack ablegen
intStack.push(var);
// int-Variable erhöhen; auf dem Stack liegt weiterhin der Wert 10
var++;

2. Alle Elemente innerhalb eines Containers besitzen eine definierte Reihenfolge (Ordnung). So werden die Elemente im bekannten stack-Container in der Reihenfolge abgelegt, in der sie eingefügt wurden. Andere Container, wie z.B. ein set-Container, sortieren die Elemente nach einem (optional definierbaren) Sortierkriterium. So sortiert die bereits vorgestellte priority_queue ihre Elemente standardmäßig aufsteigend nach ihren Werten.

PgmHeader// using für Priority-Queue
using queueType = priority_queue<int>;
// Priority-Queue definieren
queueType myPrio;
// Werte ablegen
myPrio.push(10);
myPrio.push(5);
myPrio.push(20);
// Variable zum Auslesen definieren
queueType::value_type val;
// Werte der Priorität nach auslesen
while (!myPrio.empty())
{
   cout <<  myPrio.top() << ',';
   myPrio.pop();
}

3. Operationen auf die Container sind nicht 'sicher', d.h. die Anwendung muss selbst sicherstellen, dass die Parameter der Operationen innerhalb der erlaubten Grenzen liegen. So muss z.B. sichergestellt sein, dass beim Aufruf der Memberfunktion pop() der priority_queue diese nicht leer ist.

PgmHeader// using für Priority-Queue
using queueType = priority_queue<int>;
// Priority-Queue definieren
queueType myPrio;
// Die führt zu undefiniertem Verhalten!
myPrio.pop();

4. Wird ein Container entfernt, so entfernt er auch alle Elemente die sich in seinem Besitz befinden, d.h. beim Entfernen eines Containers mit Objekten wird auch der Destruktor der abgelegten Elemente aufgerufen.

PgmHeaderclass Any;
...
{
  // Container mit Objekten definieren
  stack<Any> objStack;
  // Container mit Objekten belegen
  ...
// Hier wird der Container zerstört und damit
// auch alle in ihm enthaltenen Objekte

}

5. Container können wiederum selbst Elemente von anderen Containern sein.

PgmHeader// 2-dimensionaler Vektor
vector<vector<int>> twoDimVect;

Gemeinsame Operationen aller Container

Definitionen

Jeder Container besitzt einen Standard-Konstruktor, der einen leeren Container erzeugt. Außer diesem Standard-Konstruktor enthalten die Container noch einen Kopierkonstruktor, um einen Container zu duplizieren. Außerdem ist es möglich, einen Container bei seiner Definition mit einer Teilmenge eines anderen Containers zu initialisieren. Die Teilmenge wird hierbei durch entsprechende Iteratoren bestimmt.

PgmHeader// Erzeugt einen leeren Container
stack<int> intStack;
// Dupliziert einen Container
stack<int> myStack(intStack)
// Erzeugt einen Container und legt die
// Elemente im Bereich [beg...end) in ihm ab

vector<int> iVect;
list<double> dList(iVect.begin(),iVect.end());

Bei der Anwendung der Klasse string haben wir ja schon einmal Bekanntschaft mit Iteratoren gemacht. Allgemein verweist ein Iterator auf eine Position innerhalb eines Containers, so wie ein Zeiger auf eine bestimmte Adresse verweist. Im obigen Beispiel wird der komplette Inhalt des int-Vektors iVect in die double-Liste dList übernommen. Wie dem Beispiel ebenfalls entnommen werden kann, muss der Ziel-Container nicht den gleichen Typ besitzen wie der Ausgangs-Container. Auch die Datentypen der im Container abzulegenden Elemente müssen nicht unbedingt übereinstimmen, es muss lediglich sichergestellt sein, dass für die Datentypen entsprechende Konvertierungen definiert sind.

Größenangaben

Um die Anzahl der Elemente in einen Container zu ermitteln, steht die Memberfunktion size() zur Verfügung. Soll nur getestet werden, ob der Container leer ist oder nicht, so kann hierfür die Memberfunktion empty() verwendet werden. Sie liefert true zurück, wenn der Container leer ist.

PgmHeader// int-Vektor definieren
vector<int> intVect;
...
// Anzahl der Elemente ausgeben
cout << intVect.size() << endl;
// Test ob Vektor Elemente enthält
if (intVect.empty())
  cout << "Keine Elemente im Vektor!\n";

Vergleiche

Container können mit den üblichen Vergleichsoperatoren, wie z.B. ==, != oder auch <, verglichen werden. Der Vergleich erfolgt hierbei lexikografisch (siehe unten). Die zu vergleichenden Container müssen denselben Typ besitzen. Zwei Container sind dann identisch, wenn ihre Elemente die gleichen Werte besitzen und auch die Reihenfolge der Elemente identisch ist.

PgmHeader// int-Vektor definieren
vector<int> intVect1, intVect2;
...
// Container-Inhalte vergleichen
if (intVect1 == intVect2)
  cout << "Container enthalten die gleichen Elemente!\n";
// Vergleich auf kleiner als
if (intVect1 < intVect2)
  cout << "intVect1 ist kleiner intVect2\n";

HinweisLexikografischer Vergleich bedeutet: die Container werden Element für Element verglichen bis eine der folgende Bedingungen eintritt:

  • Zwei Elemente (Werte) sind ungleich; in diesem Fall ist das Ergebnis des Vergleichs das Resultat aus dem Vergleich der beiden Elemente.
  • Einer der Container enthält kein weiteres Element mehr; in diesem Fall ist der Container, der kein Element mehr enthält, kleiner.
  • Beide Container enthalten keine weiteren Elemente mehr; in diesem Fall sind die beiden Container identisch.

Zuweisungen und Vertauschen

Einem Container kann ein anderer Container des gleichen Typs oder eine Initialisiererliste zugewiesen werden. Im ersten Fall werden die Elemente des Ausgangs-Containers in den Ziel-Container kopiert, d.h. beide Container enthalten danach den gleichen Inhalt. Die ursprünglichen Elemente des Ziel-Containers werden dabei (selbstverständlich) gelöscht. Zusätzlich kann mit der Memberfunktion swap(...) der Inhalt zweier Container vertauscht werden.

PgmHeader// int-Vektor definieren
vector<int> intVect1, intVect2;
...
// Container zuweisen
intVect1 = intVect2;
// Container-Inhalte vertauschen
swap(intVect1,intVect2);
// Container mit Werte aus Initialisiererliste belegen
intVect1 = {10,20,30};

Iteratoren

Der sequentielle Zugriff auf Elemente in einen Container erfolgt mittels Iteratoren, wenn hierfür nicht die for-range Schleife verwendet werden soll. Die Memberfunktionen begin() und end() des Containers liefern einen Iterator auf das erste bzw. das (letzte+1) Element im Container. Iteratoren werden später noch ausführlicher behandelt.

PgmHeader// int-Vektor definieren
vector<int> intVect;
...
// Iterator definieren
vector<int>::iterator iter;
// Kompletten Container ausgeben
for (iter=intVect.begin(); iter != intVect.end(); ++iter)
  cout << *iter << endl;
// Einfacher geht's in diesem Fall aber so
for (auto element: intVect)
  cout << element << endl;

Beenden wir damit die Gemeinsamkeiten von Containern und sehen uns im nächsten Abschnitt an, welche Bedingungen Objekte bzw. deren Klassen erfüllen müssen, damit diese in einem Container abgelegt werden können.

Objekte und Container

Container, wie auch die später behandelten Iteratoren und Algorithmen, stellen an Objekte bzw. deren Klassen besondere Anforderungen.

1. Die Objekte eines Containers müssen kopierbar sein und die erzeugte Kopie muss den gleichen Inhalt wie das Original besitzen. Dieses Verhalten wird durch die Implementierung eines entsprechenden Kopierkonstruktors bzw. Move-Konstruktors sichergestellt.

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Kopierkonstruktor
  Any(const Any& src);
  // Move-Konstruktor
  Any(Any&& srr);
  ...
};

2. Die Objekte müssen zuweisbar sein. Hierzu überlädt eine Klasse den Zuweisungsoperator bzw. Move-Operator entsprechend.

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Überladener Zuweisungsoperator
  Any& operator = (const Any& rhs);
  // Move-Operator
  Any& operator = (Any&& rhs);
  ...
};

3. Die Objekte müssen auch wieder entfernt werden können. Ein Container entfernt die in ihm abgelegten Elemente durch den Aufruf des Destruktors.

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Destruktor
  ~Any();
  ...
};

Alle diese Operationen werden implizit durch den Compiler für jede Klasse generiert. Für nicht-triviale Klassen, solche die z.B. dynamische Daten oder andere Objekte enthalten, müssen diese Operatoren explizit definiert werden.

Zusätzlich erfordern manche Container und Algorithmen noch folgende Eigenschaften:

4. Einige Container erfordern die Definition des Standard-Konstruktors (parameterloser Konstruktor). Dies ist insbesondere immer dann der Fall, wenn ein Container die Reservierung von Speicher für eine bestimmte Anzahl von Elementen erlaubt.

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Standard-ctor
  Any();
  ...
};

5. Einige Container verlangen die Implementierung des Operators ==. Dieser Operator wird immer dann benötigt, wenn z.B. ein Container nach einem bestimmten Element durchsucht werden kann. Dabei ist zu beachten, dass der Operator durch eine const-Memberfunktion implementiert wird wenn keine 'normale' Funktion für den Vergleichsoperator verwendet wird.

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Implementierung des == Operators
  bool operator == (const Any& rhs) const;
  ...
};

6. Können Container auf größer/kleiner verglichen werden oder sind die Elemente innerhalb eines Containers sortiert, so muss zusätzlich zum == Operator noch der < Operator definiert werden. Auch hier gilt: die Memberfunktion muss eine const-Memberfunktion oder normale Funktion sein!

PgmHeaderclass Any
{
  ... // Private Eigenschaften
 public:
  // Implementierung des < Operators
  bool operator < (const Any& rhs) const;
  ...
};

Es müssen aber nur die Operatoren == und < implementiert werden, die restlichen Vergleichsoperatoren wie z.B. <= oder != werden intern aus diesen Operatoren gebildet werden. So ist z.B. x >= y dasselbe wie y < x.

Damit genug der Vorworte, sehen wir uns nun den ersten neuen Container an.

vector

Ein Vektor ist vom Prinzip her zunächst einmal ein Feld, dessen Größe sich dynamisch an die Anzahl der in ihm abgelegten Elemente anpasst.

vector

In einem Vektor können Daten eines beliebige Datentyps ablegt werden, aber alle Daten innerhalb eines Vektors müssen den gleichen Datentyp besitzen oder in diesen konvertierbar sein. Diese Eigenschaft gilt übrigens für alle Container.

Wenn ein Vektor verwendet wird, muss die Header-Datei vector eingebunden werden. Der Datentyp eines Vektors ist std::vector<DTYP>.

HinweisIn den Beispielen wird der Einfachheit wegen bei den Containern deren Namensraum std nicht mehr angegeben.

Definition eines Vektors

Ein Vektor kann auf die nachfolgend dargestellten Arten definiert werden.

PgmHeader#include <vector>
using std::vector;
// 1. Leeren Vektor definieren
vector<int> vect1;
// 2. Vektor duplizieren
vector<int> vect2(vect1);
// 3. Vektor mit 5 Elementen definieren
vector<int> vect3(5);
// 4. Vektor mit 5 int-Werten definieren und mit 10 initialisieren
vector<int> vect4(5,10);
// int-Feld definieren/initialisieren
int array[] {1,2,3,4};
// 5. Vektor mit Feldinhalt initialisieren
vector<int> intVect(array, array+sizeof(array)/sizeof(int));
// 6. Vektor definieren und mit Initialisierliste belegen
vector<int> vect5 {11,22,33,44};

Die zweite Definition dupliziert einen Vektor, wobei der zu duplizierende Vektor den gleichen Datentyp wie der Zielvektor besitzen muss. Bei der dritten Definition wird der Vektor mit n Elementen belegt, die über ihren Standard-Konstruktor initialisiert werden. Die vierte Vektor-Definition erzeugt einen Vektor mit n Kopien des Elements, das im zweiten Parameter angegeben wird. Im Beispiel enthält der Vektor 5 int-Elemente, welche alle den Wert 10 besitzen. Die 5. Vektordefinition erzeugt einen Vektor, der mit dem Elementen aus dem Bereich [begin..end) initialisiert wird. Für begin und end können sowohl Iteratoren als auch Adressen von Feldelementen angegeben werden. Und die letzte Definition erstellt einen Vektor, dessen Elemente mit den Elementen aus der Initialisiererliste belegt werden.

Diese Definitionen gelten übrigens ebenfalls generell für alle nachfolgenden Container und werden deshalb nicht mehr explizit aufgeführt.

Größenangaben

Die Anzahl der in einem Vektor abgelegten Elemente wird über die Memberfunktion size() ermittelt. Eine zweite Kennzahl eines Vektors ist die Maximalgröße bis zu der der Vektor erweitert werden kann, ohne dass hierfür neuer Speicherplatz angefordert werden muss. Diese Kennzahl kann durch den Aufruf der Memberfunktion capacity() ermittelt werden. Sie ist deshalb so interessant, da nach einer Anforderung von neuem Speicherplatz für einen Vektor alle Element-Referenzen und -Zeiger sowie Iteratoren ungültig werden. Wenn im Voraus schon bekannt ist, wie viele Elemente maximal im Vektor abgelegt werden, so kann mit der Memberfunktion reserve(n) die Größe des Vektors vordefiniert werden. Auf diese Weise ist es sogar möglich, für einen bereits bestehenden Vektor den Speicherbereich zu vergrößern. In diesem Fall werden die bisherigen Elemente mit übernommen. reserve(n) vergrößert aber nur einen Vektor, d.h. enthält  der Vektor z.B. Platz für 20 Elemente und es wird reserve(10) aufgerufen, so ändert dies nicht die Vektorgröße.

PgmHeader// Feld definieren/initialisieren
int array[] {1,2,3,4};
// Vektor mit Feldinhalt initialisieren
vector<int> intVect(array, array+sizeof(array)/sizeof(int));
// Kenndaten des Vektors ausgeben
cout << intVect.size() << ',' << intVect.capacity() << endl;
// Vektor vergrößern
intVect.reserve(20);
// Erneut Kenndaten ausgeben
cout << intVect.size() << ',' << intVect.capacity() << endl;
Programmausgabe4,4
4,20

Elementzugriff

Der Zugriff auf die einzelnen Elemente eines Vektors kann, wie bei Feldern, indiziert erfolgen. Auch hier hat das erste Element im Vektor den Index 0. Eine Überprüfung des Index auf Zulässigkeit findet hierbei jedoch nicht statt. Alternativ kann über die Memberfunktion at(...) ein Zugriff auf die Elemente erfolgen. Der Unterschied zum indizierten Zugriff besteht darin, das at(...) eine Bereichsüberprüfung durchführt. D.h. wird auf ein nicht vorhandenes Element zugegriffen (Index<0 oder Index>=size()), so löst die Memberfunktion eine out_of_range Ausnahme aus. Für den Zugriff auf das erste bzw. letzte Element im Vektor gibt es zusätzlich noch die speziellen Memberfunktionen front() bzw. back().

PgmHeader// Indizierter Elementzugriff
var = myVect[5];
// Abgesicherter Elementzugriff kann out_of_range Exception auslösen
var = myVect.at(99);
myVect.at(0) = var;
// Erstes Element auslesen
var = myVect.front();
// Letztes Element auslesen
var = myVect.back();

Typdefinitionen

Die Klasse vector, wie auch allen anderen Container-Klassen, enthält eine typedef-Anweisung für den Datentyp der Elemente, die im Vektor abgelegt sind. Diese typedef-Anweisung stellt den Datentyp der Elemente unter dem Bezeichner value_type zur Verfügung. So wird im Beispiel zunächst ein int-Vektor definiert. Aus diesem Vektor wird dann ein Element ausgelesen und in der Variablen var abgelegt. Der Datentyp der Variable var wird über den Bezeichner value_type festgelegt, ist hier also ein int.

PgmHeader// Beliebige Klassendefinition
class Any;
// Typ des Vektors
using theVector = vector<int>;
// Vektor definieren
theVector myVect;
// Variable definieren deren Datentyp mit dem Datentyp der
// Vektor-Elemente übereinstimmt

theVector::value_type var;
// Element aus Vektor auslesen
// Alternativ könnte hier auch 'auto var = ...' stehen

var = myVect[0];

Sollten zu einem späteren Zeitpunkt anstelle von int-Werten Objekte vom Typ Any im Vektor abgelegt werden, so ändert sich damit auch der Datentyp der Variablen var. value_type entspricht dann dem Datentyp Any. Außer der Definition des Vektortyps sind dann keine weiteren Änderungen am Programm notwendig (wenn Any einen Standard-Konstruktor besitzt und der Zuweisungsoperator für Any definiert ist).

Außer value_type stehen noch weitere Typdefinitionen zur Verfügung, die der Dokumentation zum Compiler zu entnehmen sind. So liefert z.B. der Bezeichner pointer einen Zeiger vom Datentyp der Vektorelemente.

Einfügen und Entfernen von Elementen

Das Einfügen von Elementen in einen Vektor erfolgt über die Memberfunktion insert(....). insert(...) erhält als ersten Parameter einen Iterator, der die Position bestimmt, ab der die einzufügenden Elemente eingefügt werden. Diese Position muss innerhalb des Vektors liegen, ansonsten ist das Verhalten der Memberfunktion unbestimmt. Die Klasse vector definiert drei verschiedene insert(...) Memberfunktionen, je nach dem, ob ein einzelnes Element (1. insert-Anweisung), mehrere gleiche Elemente (2. insert-Anweisung) oder Elemente aus einem anderen Bereich eingefügt werden sollen (3. insert-Anweisung). Zum Anfügen eines einzelnen Elements an einen Vektor dient die Memberfunktion push_back(...).

PgmHeader// Vektor definieren
vector<int> myVect;
// Den Wert 10 an der 2. Position einfügen
myVect.insert(myVect.begin()+1,10);
// 10x den Wert 9 ab der 4. Position einfügen
myVect.insert(myVect.begin()+3,10,9);
// Feld definieren
int array[] {1,2,3,4};
// int-Feld ab der Position 10 einfügen
myVect.insert(myVect.begin()+10, array, array+sizeof(array)/sizeof(int));
// Element anfügen
myVect.push_back(99);

Die Memberfunktion insert(...) kann unter Umständen sehr viel Zeit in Anspruch nehmen, da alle Elemente hinter der Einfügeposition entsprechend verschoben werden müssen. Bei Objekten im Vektor führt dies dann zu entsprechend häufigen Aufrufen des Kopierkonstruktors und des Zuweisungsoperators. Werden häufig Elemente eingefügt, so sollte besser ein anderer Containertyp verwendet werden.

Um Elemente aus einem Vektor zu entfernen dient u.a. die Memberfunktion erase(...). Auch erase(...) besitzt als ersten Parameter wieder einen Iterator, der die Position angibt, ab der Elemente aus dem Vektor entfernt werden sollen (1. erase-Anweisung). Soll ein ganzer Bereich aus dem Vektor entfernt werden, so wird als zweiter Parameter ebenfalls ein Iterator angegeben, der das Bereichsende angibt. Das Element am Bereichsende wird dabei nicht entfernt, d.h. es werden die Elemente im Bereich [begin..end) gelöscht. Soll nur das letzte Element im Vektor gelöscht werden, so wird hierfür die Memberfunktion pop_back() eingesetzt. pop_back() entfernt aber nur das Element, liefert es also nicht zurück. Alle Elemente innerhalb eines Vektors können über die Memberfunktion clear() entfernt werden.

PgmHeader// Vektor definieren
vector<int> myVect;
...
// 2. Element entfernen
myVect.erase(myVect.begin()+1);
// Letzte 4 Elemente entfernen
myVect.erase(myVect.end()-4,myVect.end());
// Letztes Element entfernen
myVect.pop_back();
// Alle Elemente entfernen
myVect.clear();

Und auch für erase(...) gilt: die Operation kann sehr zeitintensiv sein, den alle Elemente ab dem letzten gelöschten Element müssen entsprechend nach vorne geschoben werden.

Zuweisungen, Vergleichsoperationen und Iteratoren

Vektoren können, wie weiter oben unter Gemeinsame Operationen beschrieben, zugewiesen und verglichen werden.

HinweisWir haben uns hier nur die wesentlichen Operationen auf einen Vektors angesehen. Wenn Sie mehr über Vektoren erfahren wollen, so schlagen Sie bitte in der Dokumentation zu Ihrem Compiler nach.

HinweisZusätzlich stellt die Standard-Bibliothek noch einen besonderen Vektor std::vector<bool> zur Verfügung. Dieser Vektor besitzt einige Einschränkungen und ist von der Verarbeitungsgeschwindigkeit etwas langsamer als der 'normale' Vektor, benötigt dafür aber weniger Speicherplatz.

deque

Ein Deque (gesprochen Deck) gleicht im Prinzip einem Vektor. Auch hier werden die Elemente in einem dynamischen Feld abgelegt. Ein Deque hat prinzipiell die gleiche Schnittstelle wie ein Vektor. Der wesentliche Unterschied zum Vektor besteht darin, dass ein Deque das schnelle(!) Einfügen von Elementen am Anfang und Ende ermöglicht, während dies bei einem Vektor nur am Ende möglich ist.

deque

Bei der Verwendung eines Deque ist die Header-Datei deque einzubinden. Der Datentyp eines Deque ist std::deque<DTYP>.

Definition eines Deque

Ein Deque wird prinzipiell auf die gleiche Art wie ein Vektor definiert. Im Beispiel sind zwei der fünf Definition dargestellt.

PgmHeader#include <deque>
using std::deque;
// Leeren Deque definieren
deque<int> deq;
// Deque mit initialisieren mit Initialisiererliste
deque<int> intDeq {1,2,3,4};

Größenangaben

Die Anzahl der in einem Deque abgelegten Elemente kann ebenfalls über die Memberfunktion size() ermittelt werden. Die Memberfunktionen reserve(...) und capacity() sind für Deques nicht definiert.

PgmHeader// Deque initialisieren
deque<int> deq {1,2,3,4};
// Kenndaten des Deque ausgeben
cout << deq.size() << endl;

Elementzugriffe und Typdefinitionen

Hier gibt es keinen Unterschied zum Vektor.

Einfügen und Entfernen von Elementen

Zusätzlich zu den beim Vektor aufgeführten Memberfunktionen erlaubt ein Deque auch das direkte Einfügen und Entfernen von Elementen am Anfang des Deque mit den Memberfunktionen push_front(...) bzw. pop_front().

PgmHeader// Deque definieren
deque<int> deq;
// Erstes Element einfügen
deq.push_front(99);
// Erstes Element entfernen
deq.pop_front();

Zuweisungen, Vergleichsoperationen und Iteratoren

Auch hier gibt es keinen Unterschied zum Vektor.

list

Eine Liste ist ein sequentieller Container, der in der Regel durch eine doppelt-verkettete Liste realisiert ist.

list

Wenn eine Liste verwendet wird, ist die Header-Datei list einzubinden. Der Datentyp einer Liste ist std::list<DTYP>.

Definition einer Liste

Die Definition einer Liste erfolgt prinzipiell auf die gleiche Art und Weise wie die Definition eines Vektors.

Größenangaben

Auch die Anzahl der in einer Liste abgelegten Elemente kann über die Memberfunktion size() ermittelt werden. Die Memberfunktionen reserve(...) und capacity() sind für Listen nicht definiert.

PgmHeader#include <list>
using std::list;
// Feld definieren/initialisieren
int array[] {1,2,3,4};
// Liste mit Feldinhalt initialisieren
list<int> lst(array, array+sizeof(array)/sizeof(int));
// Kenndaten der Liste ausgeben
cout << lst.size() << endl;

Elementzugriffe

Für den direkten Zugriff auf die Elemente in einer Liste stehen nur die Memberfunktionen front() und back() zur Verfügung, um das erste bzw. letzte Element einer Liste auszulesen. Alle anderen Elemente müssen über einen entsprechenden bidirektionalen Iterator sequentiell ausgelesen werden. Die Betonung liegt hierbei auf sequentiell, d.h. es kann zu einem Listen-Iterator kein Wert addiert werden. Nur die Operationen ++ und -- sind mit einem solchen Iterator möglich.

PgmHeader// Liste definieren
list<int> lst;
...
// Erstes und letztes Element auslesen
var = lst.front();
var = lst.back();
// Das geht bei einem List-Iterator nicht!
list<int>::iterator iter = lst.begin()+10;

HinweisDa einige Memberfunktionen, insbesondere die Memberfunktionen zum Einfügen und Löschen von Elementen, die Position als Iterator erwarten, hier ein kleiner Vorgriff auf die Behandlung von Iteratoren: die Iterator-Memberfunktion advance(iter,n) verschiebt einen Iterator iter um n Positionen. D.h. die beiden nachfolgenden Programmsequenzen sind damit identisch:

// Iterator definieren
list<int>::iterator iter;
// Das geht bei einem Listen-Iterator nicht!
iter = iter+3;
// Aber so geht's, Iterator um 3 Positionen verschieben
++iter; ++iter; ++iter;
// Etwas eleganter, Iterator ebenfalls um 3 Positionen verschieben
advance(iter,3)

Typdefinitionen

Keine Änderung gegenüber Vektor.

Einfügen und Entfernen von Elementen

Zusätzlich zu den beim Deque aufgeführten Memberfunktionen erlaubt eine Liste auch das bedingte Entfernen von Elementen mit der Memberfunktion remove_if(...). Da uns im Augenblick noch Grundlagen fehlen um die remove_if(...) Memberfunktion zu verstehen, sei an dieser Stelle auf die Behandlung der Memberfunktion im nachfolgenden Kapitel über Algorithmen der Standard-Bibliothek verwiesen.

Zuweisungen, Vergleichsoperationen und Iteratoren

Für Zuweisungen und Vergleichsoperation gilt das Gleiche wie bei Deques. Im Gegensatz zum Vektor, der Random-Access Iteratoren definiert, definiert eine Liste nur bidirektionale Iteratoren. Der Unterschied zwischen diesen beiden Iterator-Typen liegt in den Operationen, die mit einem solchen Iterator erlaubt sind. Random-Iteratoren erlauben z.B. die Addition eines Wertes auf einen Iterator, um so direkt auf beliebige Elemente zugreifen zu können. Bidirektionale Iteratoren dagegen erlauben, wie auch bereits erwähnt, nur die Operationen ++ bzw. --, d.h. es ist nur möglich, auf das nächste bzw. vorherige Element in einem Zug zuzugreifen.

Weitere Listen-Memberfunktionen

Zum Sortieren von Listen enthält die list-Klasse die Memberfunktion sort(...). Defaultmäßig werden die Elemente einer Liste aufsteigend sortiert. Enthält die Liste Objekte, so führt dies zum Aufruf des Operators < der Objekt-Klasse.

PgmHeader// Liste definieren und initialisieren
list<int> lst1 {1,2,2,1,111,222};
lst1.sort();
Listeninhalt:
1,1,2,2,111,222

Soll die Sortierung nicht aufsteigend erfolgen, so muss das Sortierkriterium definiert werden. Die Definition des Sortierkriteriums für einfache Datentypen erfolgt mittels einer Funktion die folgende Signatur besitzt :

bool SFUNC(const DTYP val1, const DTYP val2);

SFUNC ist der Name der Sortierfunktion und DTYP der Datentyp der zu sortierenden Elemente. Der Name der Sortierfunktion wird dann der Memberfunktion sort(...) als Parameter übergeben.

PgmHeader// Template-Sortierfunktion
template <typename T>
bool Less (const T& val1, const T& val2)
{
  return (val1<val2);
}
...
list<int> myList;
...
// Werte fallend sortieren über Funktion
myList.sort(Less<myList::value_type>);

Im Beispiel ist eine solche Sortierfunktion einmal als Template-Funktion implementiert. Durch die Definition der Funktion als Template können auch Objektelemente sortiert werden, wenn die Klasse der Container-Elemente den Operator < überladen hat.

Sind in der Liste Objekte abgelegt, so kann das Sortierkriterium auch über eine entsprechende Memberfunktion innerhalb der Klasse definiert werden. Nachfolgend ist wieder eine Beispiel für eine solche Sortier-Memberfunktion dargestellt. Beachten Sie bitte, dass die Sortier-Memberfunktion in der Regel static sein muss und die Memberfunktion bei der Übergabe an sort(...) voll zu qualifizieren ist.

PgmHeaderclass Object
{
  int toSort;   // Zu sortierendes Datum
  ..
public:
  // Sortier-Memberfunktion
  static bool SortMethod(const Object& obj1, const Object& obj2)
  {
    return (obj1.toSort < obj2.toSort);
  }
  ..
};
...
list<Object> objList;
...
// Object sortieren
objList.sort(Object::SortMethod);

Außer dass eine Liste sortiert werden kann, kann eine Liste, oder ein Teil davon, in eine andere Liste verschoben werden. Hierzu dienen die Memberfunktionen splice(pos, lst2), splice(pos, lst2, l2pos) bzw. splice(pos, lst2, l2beg, l2end). Im ersten Falle werden alle Elemente aus der Liste lst2 vor die Position pos verschoben. Die zweite Memberfunktion verschiebt alle Elemente aus der Liste lst2 ab der Position l2pos vor die Position pos während die dritte Memberfunktion nur die Elemente im Bereich [l2beg..l2end) aus der zweiten Liste verschiebt. Beachten Sie bitte, dass die Elemente verschoben werden, d.h. sie sind danach nicht mehr in der zweiten Liste enthalten!

PgmHeader// Zwei Listen definieren/initialisieren
list<int> lst1 {1,2,2,1,111,222};
list<int> lst2 {11,22,33};
// Iterator auf Beginn 1. Liste setzen
auto iter = lst1.begin();
// Iterator auf 3. Position schieben
advance(iter,2);
// 2. Liste einfügen, ist danach leer!
lst1.splice(iter,lst2);
Listeninhalt:
1,2,11,22,33,2,1,111,222

Soll eine sortierte Liste in eine andere sortierte Liste so eingefügt werden, so dass die daraus resultierende Liste ebenfalls wieder sortiert ist, so wird hierfür die Memberfunktion merge(lst2) verwendet. Beachten Sie, dass beide Listen sortiert sein müssen, ansonsten ist das Ergebnis undefiniert (wenigstens lt. C++ Standard).

PgmHeader// Zwei bereits sortierte Listen erstellen
list<int> lst1 {1,11,111};
list<int> lst2 {11,21,31};
// Listen sortiert zusammenfügen
lst1.merge(lst2);
Listeninhalt:
1,11,11,21,31,111

Und zu guter Letzt können noch unmittelbar aufeinander folgende gleiche Elemente (Werte) mit der Memberfunktion unique() aus der Liste entfernt werden. Außerdem kann mit der Memberfunktion reverse() die Reihenfolge der Elemente in der Liste umgedreht werden. Beachten müssen Sie bei der Memberfunktion unique(), dass nur aufeinander folgende gleiche Elemente entfernt werden (siehe dazu im Beispiel die Behandlung des Werts 11). Sollen alle doppelten Elemente entfernt werden, so ist die Liste vorher mittels sort() entsprechend zu sortieren.

PgmHeaderlist<int> lst1 {1,11,22,11,11,111};
// Gleiche Elemente entfernen
lst1.unique();
// Liste umdrehen
lst1.reverse();
Listeninhalt nach unique():
1,11,22,11,111
Listeninhalt nach reverse():
111,11,22,11,1

Damit sind die sequentiellen Container abgehandelt und wir können uns im nächsten Kapitel den assoziativen Container zuwenden.