Allgemeine Container-Eigenschaften und -Operationen
Objekte und Container
vector
deque
list
In dieser und der nachfolgenden Lektion werden wir uns erneut mit der Standard C++ Bibliothek befassen. Sie erhalten einen Überblick über weitere Container und Funktionen, die in der Bibliothek enthalten sind. Einige Container haben Sie ja bereits in einer früheren Lektion kennen gelernt. Bevor wir auf die restlichen Container im Einzelnen eingehen, werden wir uns zunächst die allen Containern gemeinsamen Eigenschaften und Operationen ansehen.
|
|
|
|
Folgende Eigenschaften gelten für alle weiteren STL Container:
1. Alle STL Container verwenden die so genannte Werte-Semantik. D.h. die Container kopieren intern die einzufügenden Elemente anstatt nur eine Referenz darauf abzuspeichern. Dies hat u.a. zur Folge, dass nachträgliche Änderungen an den abgelegten Elementen sich nicht auf den Inhalt des Containers auswirken.
 // 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 Container 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 einer einem (optional definierbarem) Sortierkriterium. So sortiert im Beispiel die bereits vorgestellte priority_queue ihre Elemente standardmäßig aufsteigend nach ihren Werten.
// typedef für Priority-Queue typedef priority_queue<int> queueType; // 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 auch noch Elemente enthält.
// typedef für Priority-Queue typedef priority_queue<int> queueType; // 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 der Destruktor der abgelegten Elemente aufgerufen.
class 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.
// 2-dimensionaler Vektor
vector<vector<int> > twoDimVect;
|
Definitionen
Jeder Container besitzt einen Standard-Konstruktor, der einen leeren Container (ohne Elemente) erzeugt. Außer diesem Standard-Konstruktor enthalten die Container noch einen Kopier-Konstruktor, um einen Container zu duplizieren. Außerdem ist es noch möglich, einen Container bei seiner Definition mit einer Teilmenge eines anderen Containers zu initialisieren. Die Teilmenge wird hierbei durch entsprechende Iteratoren bestimmt.
// 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 Sie ja schon einmal Bekanntschaft mit Iteratoren gemacht (siehe hier). Ein Iterator verweist auf eine Position innerhalb eines Container, so wie ein Zeiger auf eine bestimmte Adresse verweist. Im obigen Beispiel wird der komplette Inhalt des int-Vektors iVect in die neu definierte double-Liste dList übernommen. Wie Sie dem Beispiel entnehmen können, muss der Ziel-Container nicht den gleichen Typ besitzen wie der Ausgangs-Container. Auch die Datentypen der Container-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. Wollen Sie nur testen, 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.
// 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 auch mit den üblichen Vergleichsoperatoren, wie z.B.
==, != oder auch <, verglichen
werden. Der Vergleich erfolgt hierbei lexikografisch (siehe unten). Die
zu vergleichenden Container müssen den selben Typ besitzen. Zwei
Container sind dann identisch, wenn ihre Elemente die gleichen Werte
besitzen und auch die Reihenfolge der Elemente identisch ist. D.h.
Container können durchaus verschiedene Objekte enthalten und sind
trotzdem gleich, wenn die Objekte den gleichen Wert (Inhalt) besitzen.
// 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"; |
|
|
Zuweisungen und Vertauschen
Sie können Container einander zuweisen. In diesem 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 können Sie noch mit der Memberfunktion swap(...) den Inhalt zweier Container vertauschen.
// int-Vektor definieren vector<int> intVect1, intVect2; ... // Container zuweisen intVect2 = intVect2; // Container-Inhalte vertauschen swap(intVect1,intVect2); |
Iteratoren
Der sequentielle Zugriff auf Elemente in einen Container kann über Iteratoren erfolgen. Hierbei liefern die Memberfunktionen begin() und end() des Containers einen Iterator auf das erste bzw. das letzte+1 Element im Container. Beachten Sie bitte, dass end() einen Iterator liefert der hinter das letzte Element verweist. Iteratoren werden in der nächsten Lektion noch ausführlicher behandelt.
// 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; |
So, damit genug mit den Gemeinsamkeiten der Container. Sehen wir uns im nächsten Abschnitt an, welche Bedingungen Objekte bzw. deren Klassen erfüllen müssen, damit sie in einem Container abgelegt werden können.
Container, wie auch die in den nächsten Lektionen 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 'Wert' wie das Original besitzen. Dieses Verhalten wird durch die Implementierung eines entsprechenden Kopier-Konstruktors erreicht.
class Any
{
... // Private Eigenschaften
public:
// Kopierkonstruktor
Any(const Any& src);
...
};
|
2. Die Objekte müssen zuweisbar sein. Hierzu überlädt eine Klasse den Zuweisungsoperator entsprechend.
class Any
{
... // Private Eigenschaften
public:
// Überladener Zuweisungsoperator
|
3. Die Objekte müssen auch wieder entfernt werden können. Container entfernen ihre Elemente durch den Aufruf des Destruktors.
class Any
{
... // Private Eigenschaften
public:
// Destruktor
~Any()
|
Alle diese Operationen werden implizit durch den Compiler für jede Klasse generiert. Sie müssen diese Operationen also nur für nicht-triviale Klassen (solche die z.B. dynamische Daten oder andere Objekte enthalten) selbst implementieren.
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.
class Any
{
... // Private Eigenschaften
public:
// Standard-ctro
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. Beachten Sie bitte, dass Sie den
Operator durch eine const-Memberfunktion implementieren müssen,
wenn Sie keine 'normale' Funktion für den Vergleichsoperator verwenden.
class 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 sein!
class Any
{
... // Private Eigenschaften
public:
// Implementierung des < Operators
bool operator < (const Any& rhs) const
|
Sie müssen aber nur die Operatoren == und <
implementieren, die restlichen Vergleichsoperatoren wie z.B. <=
oder != werden intern aus diesen Operatoren gebildet
werden. So ist z.B. x >= y das selbe wie y < x.
Damit genug der Vorworte, sehen wir uns nun den ersten neuen Container an.
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.
In einem Vektor können Sie Daten eines beliebige Datentyps ablegen, aber alle Daten innerhalb eines Vektors müssen den gleichen Datentyp besitzen. Diese Eigenschaft gilt übrigens für alle Container.
Wenn Sie einen Vektor einsetzen, müssen Sie die Header-Datei vector einbinden. Der Datentyp eines Vektors ist std::vector<DTYP>.
|
|
Ein Vektor kann auf die fünf nachfolgend dargestellten Arten definiert werden.
#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 10 definieren 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)); |
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. Und die letzte Vektordefinition erzeugt einen Vektor, der mit dem Elementen aus dem Bereich [begin..end) initialisiert wird. Für begin und end können sowohl Iteratoren wie auch Adressen von Feldelementen angegeben werden.
Diese Definitionen gelten generell für alle nachfolgenden Container und werden deshalb nicht mehr explizit aufgeführt,
Die Anzahl der in einem Vektor abgelegten Elemente können Sie über die Memberfunktion size() ermitteln. Eine zweite Kenngröße eines Vektors ist die Maximalgröße, bis zu der der Vektor erweitert werden kann, ohne dass hierfür neuer Speicherplatz angefordert werden muss. Diese Größe erhalten Sie durch den Aufruf der Memberfunktion capacity(). 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 Sie im Voraus schon wissen, wie viele Elemente im Vektor abgelegt werden, so können Sie mit der Memberfunktion reserve(n) die Größe des Vektors von vornherein festlegen. Sie können auch einen bereits mit Elementen belegten Vektor auf diese Weise 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 Sie rufen reserve(10) auf, so ändert dies an der Vektorgröße nichts.
// 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; |
4,4 |
Der Zugriff auf die einzelnen Elemente eines Vektors kann, wie bei
Feldern üblich, indiziert erfolgen. Auch hier hat das erste Element im
Vektor den Index 0. Eine Überprüfung des Index auf Zulässigkeit findet
hierbei nicht statt. Alternativ kann über die Memberfunktion at(...)
sowohl lesend wie auch schreibend auf die Elemente zugegriffen werden.
Die Memberfunktion at(..) führt jedoch eine Bereichsüberprüfung
durch. Wird auf ein nicht vorhandenes Element zugegriffen (Index<0
oder Index>=size()), so löst die Memberfunktion eine
out_of_range Exception aus. Für den Zugriff auf das erste bzw.
letzte Element im Vektor gibt es zusätzlich noch die gesonderten
Memberfunktionen front() bzw. back().
// 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(); |
Die Klasse vector, wie übrigens auch allen anderen Container-Klassen, enthält eine typedef-Anweisung für den Datentyp der Elemente, die im Vektor abgelegt sind. Die typedef-Anweisung stellt den Datentyp der Elemente unter dem Bezeichner value_type zur Verfügung. Wenn Sie diesen Bezeichner in Ihrer Anwendung verwenden um Variablen/Objekte zu definieren die im Vektor verarbeitet werden sollen, so ist Ihre Anwendung vom tatsächlichen, aktuellen Datentyp der Vektorelemente weitgehend unabhängig. 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 entspricht (über den Bezeichner value_type) dem Datentyp der Vektorelemente, also int.
// Beliebige Klassendefinition class Any; // Typ des Vektors typedef vector<int> theVector; // Vektor definieren theVector myVect; // Variable definieren deren Datentyp mit mit dem Datentyp der // Vektor-Elemente übereinstimmt theVector::value_type var; // Element aus Vektor auslesen var = myVect[0]; |
Werden dann zu einem späteren Zeitpunkt anstelle von int-Werten Objekte vom Typ Any im Vektor abgelegt, so ändert sich damit auch der Datentyp der Variablen var. value_type entspricht dann dem Datentyp Any. Sie brauchen also außer an der Definition des Vektortyps nichts in Ihrem Programm ändern (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 Sie bitte der Dokumentation zur Ihrem Compiler entnehmen. So liefert z.B. der Bezeichner pointer einen Zeiger vom Datentyp der Vektorelemente.
Das Einfügen von Elementen in einen Vektor erfolgt über die Memberfunktion insert(....). insert(...) erhält als ersten Parameter immer 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(...).
// 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 diese dann zu entsprechend häufigen Aufrufen des Kopier-Konstruktors und des Zuweisungsoperators. Sollen häufig Elemente eingefügt werden, so sollte besser einer der anderen Container verwendet werden.
Um Elemente aus einem Vektor zu entfernen wird u.a. die Memberfunktion erase(...) verwendet. Auch erase(...) besitzt als ersten Parameter immer 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.
// 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 der Position des zu löschenden Elements werden entsprechend nach vorne geschoben.
Zuweisungen, Vergleichsoperationen und Iteratoren
Vektoren können, wie weiter oben unter Gemeinsame Operationen beschrieben, zugewiesen und verglichen werden.
|
Zusä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. |
Ein Deque (gesprochen Deck) gleicht im Prinzip einem Vektor. Auch hier werden die Elemente in dynamischen Feldern abgelegt und er 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.
Wenn Sie ein Deque einsetzen, müssen Sie die Header-Datei deque einbinden. Der Datentyp eines Deque ist std::deque<DTYP>.
Ein Deque wird prinzipiell auf die gleiche Art wie ein Vektor definiert (5 Konstruktore). Im Beispiel sind zwei der fünf Definition dargestellt.
#include <deque> using std::deque; // Leeren Deque definieren deque<int> deq; // int-Feld definieren/initialisieren int array[] = {1,2,3,4}; // Deque mit Feldinhalt initialisieren deque<int> intDeq(array, array+sizeof(array)/sizeof(int)); |
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.
// Feld definieren/initialisieren int array[] = {1,2,3,4}; // Deque mit Feldinhalt initialisieren deque<int> deq(array, array+sizeof(array)/sizeof(int)); // Kenndaten des Deque ausgeben cout << deq.size() << endl; |
Auch hier gibt es zum Vektor keinen Unterschied.
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().
// Deque definieren deque<int> deq; // Erstes Element einfügen deq.push_front(99); // Erstes Element entfernen deq.pop_front(); |
Auch hier gibt es keinen Unterschied zum Vektor.
Eine Liste ist ein sequentieller Container, der in der Regel durch eine doppelt-verkettete Liste realisiert ist.
Wenn Sie eine Liste einsetzen, müssen Sie die Header-Datei list einbinden. Der Datentyp einer Liste ist std::list<DTYP>.
Die Definition einer Liste erfolgt prinzipiell auf die gleiche Art und Weise wie die Definition eines Vektors (5 Konstruktore).
Die Anzahl der in einer Liste abgelegten Elemente können Sie auch hier über die Memberfunktion size() ermitteln. Die Memberfunktionen reserve(...) und capacity() sind für Listen nicht definiert.
#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; |
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 entsprechende bidirektionalen Iterator sequentiell ausgelesen werden. Die Betonung liegt hierbei auf sequentiell, d.h. Sie können zu einem Listen-Iterator auch keinen Wert hinzuaddieren. Lediglich die Operationen ++ und -- sind mit einem solchen Iterator möglich.
// 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; |
|
|
Keine Änderung gegenüber Vektor.
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 in der nachfolgenden Lektion über Algorithmen der Standard-Bibliothek verwiesen.
Für Zuweisungen und Vergleichsoperation gilt das Gleiche wie bei Deques. Im Gegensatz zum Vektor, der Random-Access Iteratoren definiert, definiert eine Liste aber 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.
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.
// Liste definieren und initialisieren int array1[] = {1,2,2,1,111,222}; list<int> lst1(array1, array1+sizeof(array1)/sizeof(int)); lst1.sort(); Listeninhalt: 1,1,2,2,111,222 |
Soll die Sortierung nicht aufsteigend erfolgen, so kann das Sortierkriterium auch frei definiert werden. Um das Sortierkriterium für einfache Datentypen zu definieren, muss dies über eine Funktion erfolgen die folgende Signatur besitzt:
| bool SFUNC(const DTYP lhs, const DTYP rhs); |
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.
// Template-Sortierfunktion template <typename T> bool Less (const T& lhs, const T& rhs) { return (rhs<lhs); } ... list<int> myList; ... // Werte fallend sortieren über Funktion myList.sort(Less<myList::value_type>); |
Im Beispiel oben sehen Sie eine solche Sortierfunktion, die als Template ausgeführt wurde. Durch die Definition der Funktion als Template können Sie mithilfe dieser Funktion auch Objektelemente sortieren. Beachten Sie, dass die Klasse für Container-Elemente stets den Operator < überladen sollte.
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 Sie die Memberfunktion bei der Übergabe an sort(...) voll qualifizieren müssen!
class Object
{
..
// Sortier-Memberfunktion
static bool SortMethod(const Object& lhs, const Object& rhs)
{
return (rhs<lhs);
}
..
};
...
list<Object> objList;
...
// Object sortieren
objList.sort(Object::SortMethod);
|
Außer Sortieren können Sie eine komplette Liste oder Teile einer Liste auch in eine andere Liste verschieben. 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, eingefügten Liste enthalten!
// Zwei Listen definieren/initialisieren int array1[] = {1,2,2,1,111,222}; int array2[] = {11,22,33}; list<int> lst1(array1, array1+sizeof(array1)/sizeof(int)); list<int> lst2(array2, array2+sizeof(array2)/sizeof(int)); // Iterator auf Beginn 1. Liste setzen list<int>::iterator iter = lst1.begin(); // Iterator auf 3. Position schieben advance(iter,2); // 2. Liste einfügen, ist danach leer! lst1.splice(iter,lst2); Listeninhalt: |
Wollen Sie eine sortierte Liste in eine andere sortierte Liste einfügen, so dass die daraus resultierende Liste ebenfalls 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).
int array1[] = {1,11,111};
int array2[] = {11,21,31};
// Zwei bereits sortierte Listen erstellen
list<int> lst1(array1, array1+sizeof(array1)/sizeof(int));
list<int> lst2(array2, array2+sizeof(array2)/sizeof(int));
// Listen sortiert zusammenfügen
lst1.merge(lst2);
Listeninhalt:
1,11,11,21,31,111
|
Und zu guter Letzt können Sie noch unmittelbar aufeinander folgende gleiche Elemente (Werte) mit der Memberfunktion unique() aus der Liste entfernen und mit der Memberfunktion reverse() die Reihenfolge der Elemente in der Liste umdrehen. 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). Wollen Sie alle gleichen Elemente entfernen, so können Sie vorher die Liste mittels sort() entsprechend sortieren.
int array1[] = {1,11,22,11,11,111};
list<int> lst1(array1, array1+sizeof(array1)/sizeof(int));
// 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 in der nächsten Lektion den assoziativen Container zuwenden.
Die
in einer vorherigen Lektion eingeführten speziellen Container
stack, queue, priority_queue und
bitset besitzen nicht alle hier aufgeführten Operationen.
Wir
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 Ihnen das Buch 'The
C++ Standard Library, A Tutorial and Reference' von Nicolai
M. Josuttis.