1. Iteratoren:

schaffen eine einheitliche Basis zum Positionieren und Iterieren für unterschiedliche Container. Können damit als eine Abstraktion von Zeigern verstanden werden.

a). selbstdefinierte : eigene Variable vom Typ Iterator.

b). "eingebettete" Typen: Iteratoren, reverse_iteratoren:

vordefinierte Datentypen zur Darstellung von Iteratoren.

c). begin( ), end( ), rend( ), rbegin( ) :

Vordefinierte Methoden des Containers, der Iterator als Rückgabewert zurückliefern.

· Begin ( ): das erste Element

· rbegin( ) : das letzte Element (reverse begin)

· end ( ) : Zeiger auf das Element hinter dem letzten Element

· rend( ) : das Element vor dem ersten Element (reverse ende)

d). ++, -- - Inkrement (bzw. Dekrement) -Operatoren :

sind für die Iterator Typen (Bidirektionale It.) überladen und manipulieren Iterator-Variable

e). Iteratormanagement bei Vektoren und listen:

Increment / Decrement (++, --) Operatoren sind für alle Klassen definiert. Dazu kommt Indexoperator [] (in vector und deque überladen) um auf einzelne Objekte eines Containers zugreifen zu können.

Bei der Listen muss man durchlaufen (nur mit ++ oder --)

2. STL Container (Standart Template Library) :

vorgefertigte Templates, die Objekte verwalten und Datenstrukturen zur Verfügung stellen.

· Die Container-Klasse list <T, Allocator> -bietet die für doppelt verkettete Listen typischen Funktionalitäten. Dazu gehören schnelles einfügen und löschen in beliebigen, vorgegebenen Positionen. Sortieren und Mischen definiert.

· Die Container-Klasse deque <T, Allocator> - (double ended Queue) –direkter Zugriff mit dem Indexoperator, sowie Einfügen und Löschen an Anfang und Ende des Containers definiert.

· Die Container-Klasse vector <T, Allocator> : bietet sowohl die für Arrays üblichen Operationen, als auch dynamisches Wachsen und Schrumpfen. Langsames Einfügen , aber schnelles Löschen. Indexoperator überladen.

· Die Container-Klasse (Maps, Multimaps : Element = Schlüssel + Objekt) – gehört zu den assoziativen Containern und verwaltet Objekte in sog. Heaps, das sind Bäume mit minimaler Höhe. Operationen werden anhand von sortierbaren Schlüsseln vorgenommen. Maps und Multimaps speichern Paare von sortierbaren Schlüsseln und Objekten. Der Schlüssel dient zur Identifizierung eines Objekts, wird aber separat gespeichert, das Objekt wird mit dem Schlüssel assoziiert, so dass ein Element einer Map immer zugleich aus einem Schlüssel und einem Objekt besteht.

pair<const Key, T>

{ public:

first; // speichert den Schlüssel; pos->first

second; // speichert das Element; pos->second

Default -Konstruktor

Kopie-Konstruktor

};

· Die Container-Klasse (Sets, Multisets : Element = Schlüssel + Objekt) – gehört zu assoziative Container, verwalten Objekte in sog. Heaps, das sind bäume mit minimaler Höhe. Operationen werden anhand von sortierbaren Schlüsseln vorgenommen. Der Schlüssel ist stets Teil eines Objekts; also ein Datenelement, für das in der entsprechenden Klasse eine Vergleichsrelation definiert werden muss. Standardmassig wird die Kleiner-Relation verwendet (d.h. Operator < muss überladen werden).

3. STL Konzepte

a). Container, linear vs assoziativ :

Container speichern Objekte gleichen Typs und stellen Operationen zur Verwaltung dieser Objekte zur Verfügung (einfügen, löschen hervorholen) Die Speicherverwaltung erfolgt zur Laufzeit dynamisch.

Linear (sequenziell) C. – die Objekte sind sequentiell angeordnet und Zugriff auf ein Objekt direkt oder sequentiell erfolgt. Gehören Vektoren, Stacks, Queues.

Assoziative C. – die Objekte im Allgemeinen werden in einer Baumstruktur verwaltet und mit Hilfe von Schlüsseln angesprochen. Gehören Sets, Maps, Bitsets

b). Adaptorklassen – werden konstruiert aus grundlegenden Template - Klassen( vector, list, deque) . Erhält einen linear C. als Template – Argument und speichert ihn in ein protected- Datenelement.

c).Iterator: siehe oben.

d).Algorithmus:

sind technisch realisierte Funktions-Templates, die als Methoden gekapselt sind (z.b. Sortieren).

e). Vor- und Nachteile verschiedener Container Klassen – beim List-Container kann man schnell Einfügen aber langsam Löschen, bei Vector – langsames Einfügen aber schnelles Löschen. Deque - Einfügen sowohl am Anfang, als auch am Ende ( Vektoren nur am Ende).

4. Wichtige Container-Fertigkeiten

a). Umgang mit linearen Containern-

b). Containerklassen deklarieren :

#include <vector>

............................

int main( ) {

vector <int> einvector;

………………………..

}

c). aus CK ableiten :

class personenliste : public list<person> {

public:

void eingabe( );

void ausgabe( );

//begin( );

//end( ); vererbte Methoden

}

d). CK traversieren:

Im Rahmen einer Schleife durchgehen.

e). Elementzugriff:

Methoden und selbstdefinierte Iteratoren. Methode

front() für den Zugriff auf das erste Element,

back() für den Zugriff auf das letzte Element.

Zugriff mit Indizes:Indexoperator.

f). CK Methoden verwenden:

In den CK vector, deque und list sind die Methoden push_back( ) zum Einfügen am Ende und insert( ) zum Einfügen hinter der vorgegebenen Position definiert. In den Klassen list und deque gibt es außerdem die Methode push_front( ) zum Einfügen am Anfang. Diese Methode ist in der Klasse vector nicht definiert. Die Methode insert( ) ist in den verschiedenen Versionen überladen.