15.1 Konzept der STL - zaik.uni-koeln.de fileZentrum für Angewandte Informatik Köln Arbeitsgruppe Faigle/Schrader Universität zu Köln15 Standard Template Library (STL) 15.1 Konzept

Zentrum für Angewandte Informatik KölnArbeitsgruppe Faigle / SchraderUniversität zu Köln

15 Standard Template Library (STL)

15.1 Konzept der STL

Die STL ist ein Bestandteil der C++ Standardbibliothek,welche im wesentlichen aus den folgenden Teilen besteht:

1. Generische Datenstrukturen und Algorithmen:

• Container

• Iteratoren

• Algorithmen

2. Internationalisierung:

• Zeichensätze, Datumsformat...

3. Exceptions, Diagnose (s. später)

4. Numerisches:

• komplexe Zahlen

• numerische Felder und zugehörige Operationen

5. Streams (Ein-/Ausgabe)

6. Vermischtes:

• Speicherverwaltung und -zugriff

• Datum und Uhrzeit

• Strings (Zeichenketten)

WS 2001/02 Programmierkurs C++ Seite 236


Die STL beinhaltet im wesentlichen den Punkt 1.) derAufzählung. Ihr Schwerpunkt liegt auf dabei aufDatenstrukturen undAlgorithmen und nutzt denTemplate–Mechanismuszur Parametrisierung vonKomponenten (Generizität).

Hinter dem Gedanken der Generizität steckt die folgendeIdee:

Kann ein Algorithmus unabhängig vonRepräsentationsdetails ausgedrückt werden und ist dieserschwinglich erreichbar (d.h. ohne logische Verrenkungen),so sollte man dies tun.

Beispiel:

Jemand, der eine Stack benötigt, braucht nicht unbedingteinen Stack für Zeichen. Ein Stack ist ein allgemeinesKonzept, das unabhängig von dem Begriff Zeichen existiert.Folgerichtig sollte ein Stack deshalb auch unabhängig davonrepräsentiert werden.

Zum Konzept der STL gleich mehr, zunächst eine Übersichtüber ihre wichtigsten Elemente:

Container „Behälter“ für Objekte bzw. Objekte, die zurVerwaltung anderer Objekte dienen (auchbenutzer-definierte Datentypen). Objekte können per Wert(lvalue) oder per Referenz abgelegt werden.



Iteratoren Iteratoren arbeiten wie Zeiger. Je nach

Anwendungsfall können sie selbst gewöhnliche Zeiger

oder Objekte mit zeigerähnlichen Eigenschaften sein.

Iteratoren bewegen sich über die Elemente eines

Containers und stellen den Zugriff auf diese Elemente

bereit.

Algorithmen Die Template–Algorithmen arbeiten mit

Iteratoren, die auf Container zugreifen. Damit diese

sowohl benutzerdefinierte Datentypen unterstützen als

auch die in C++ vorhandenen Datentypen, sind die

Algorithmen so entworfen, daß sie ebenso gut mit

normalen Zeigern arbeiten.

Die Iteratoren entkoppeln also Container und Algorithmen:

Letztere sind als Template implementiert, die über den Typ

des Iterators parametrisiert sind. Damit ist ihre Nutzung nicht

auf einen einzelnen speziellen Typ von Container beschränkt.

Dieser Ansatz der generischen Programmierung mit Hilfe

von Templates bietet gegenüber einem Ansatz mittels

Vererbung und Polymorphismus den großen Vorteil, daß die

Anzahl der notwendigen verschiedenen Container- und

Algorithmentypen drastisch reduziert wird:



Ein Element des Datentypsint soll in einem Container

vector mit Hilfe eines Algorithmusfind() gefunden

werden.

• Fürn Containertypen brauchen wir für jeden Container

einen eigenen Algorithmusfind() .

• Soll das Ganze für einen beliebigen vonm Datentypen

funktionieren, steigt die Anzahl derfind()

Algorithmen aufm× n.

• Betrachtet mank Algorithmen, wäre die

Implementierung vonm× n× k Algorithmen

erforderlich.

• Die Verwendung von Templates erlaubt es, die Anzahlm

auf1 zu reduzieren.

• Durch die Entkopplung von Containern und Algorithmen

über die Iteratoren reduziert sich die Anzahl zu

implementierender Algorithmen aufn+ k.

Da Templates bereits zur Compilationszeit ausgewertet

werden, besitzt dieses Vorgehen darüber hinaus den Vorteil

derTypsicherheit.



Nebenbemerkungen:

• Die STL stellt einen Rahmen zur Verfügung, den

Programmierer relativ leicht um eigene Komponenten

erweitern können.

• Die STL ist mit dem Ziel hoher Effizienz entworfen. Je

nach Art und Größe des zu bearbeitenden Containers

kann die Laufzeit eines Algorithmus stark variieren (s.a

15.2).

• Die zur STL gehörenden Algorithmen sind nicht nur auf

STL–Container sondern auch auf einfache Felder

anwendbar (s.a. 15.3).

• Durch die Aufnahme der STL in die C++

Standardbibliothek führt ihre Verwendung anstelle von

„selbst–gestrickten“ Bibliotheken dazu, daß die

Programme

– leichter portierbar (Compiler–Hersteller orientieren

sich an Standards)

– und leichter wartbar (verbreitetes Know-how)

sind.



15.2 Beispiele aus der STL

Die Anzahl der Container der STL und ihrer Methoden läßt

sich hier nicht komplett darstellen. Eine gute Übersicht findet

sich unter

http://www.sgi.com/tech/stl/

Hier werden nur einige Container–Klassen präsentiert, im

folgenden Abschnitt 15.3 das Zusammenspiel zwischen den

einzelnen STL–Komponenten näher beleuchtet.

Containerklassevector

Die Container–Klassevector<T> (T steht für einen

Datentyp) ist eine Sequenz von Elementen, die einem Feld

von Daten sehr ähnlich ist. Sie ist die einfachste der

STL–Container–Klassen.

Der Standard schreibt für Container keine spezielle interne

Darstellung vor, sondern Schnittstellen und Anforderungen

zur Komplexität. Fürvector ist die Datenstruktur der

Elemente einem Feld angenähert:

GroesseDarstellung

vector:Elemente extra Platz



Eigenschaften:

• leichter und effizienter Zugriff auf einzelne Elemente in

beliebiger Reihenfolge (random access iterator).

• Einfügen und Entfernen von Elementen am Vektorende

in konstanter Zeit.

• Einfügen und Entfernen von Elementen an anderen

Positionen in linearer Zeit.

• Zahl der Elemente dynamisch variierbar. Das

Speichermanagment wird automatisch vom Container

übernommen (letzteres gilt für alle Container–Klassen).

Beispiel:

Wir wollen eine Liste von Fenstern verwalten.

#include <vector>

using namespace std;

typedef int window;

int main()

{

vector<window> msw;

}



Die Typvereinbarung dient lediglich dazu, die Klasse

window nicht definieren zu müssen, im Prinzip darf hier

jeder Datentyp stehen.

Bei der Vereinbarung des Containersmswwird der

Default–Konstruktor der Template–Klassevector

aufgerufen.

Die Methode

vector<T>::size_type max_size()

liefert die maximale Anzahl von Elementen, die im

Vektor des DatentypsT gespeichert werden kann. Diese

ist system–abhängig.

vector<T>::size_type capacity()

liefert die Anzahl der Elemente, für die Speicher

allokiert wurde.

cout << msw.capacity() << endl;

$>> 0

Bemerkung:Die im folgenden aufgeführten Methoden sind

auch für die anderen STL-Container vorhanden

$>> soll im folgenden immer die Ausgabe des Vektors

bedeuten.



Es läßt sich auch ein Vektor vereinbaren, der Speicher füreine anzugebende Zahl von Elementen allokiert:

vector<window> msw2(10);

Der Zugriff auf Elemente des Vektors kann dann mittels desOperators[index] erfolgen (nur für Container mitrandom

access).

Aber Achtung: Der Zugriff über den Operator geschiehtohne Überprüfung der Gültigkeit des Index:

msw2[0] = 2; // erlaubt

msw2[9] = 5; // erlaubt

msw[0] = 2; // compiliert,

// aber Programmabsturz

Der Vorteil der STL-Container ist aber gerade, daß diese sichselbst um die Allokation von Speicher kümmern. Deshalbgibt es Methoden, die ein Einfügen von Elementen auchermöglichen, wenn der Container vorher keinen Speicherallokiert hat.

Dervector ist insbesondere effizient, wenn Elemente ansEnde eingefügt werden

msw.push_back(17);

msw.push_back(42);

cout<<"("<< msw[0] <<","<< msw[1] <<")"<<endl;

$>> msw = (17,42)



Einfügen kann man natürlich auch an anderen Positionen:

iterator insert(iterator pos, const T& x)

Einfügen eines Elements vom DatentypT vor der

Position, auf die der Iteratorpos zeigt.

Iteratoren sollen bis auf wenige Bemerkungen im weiteren

nicht näher behandelt werden.

Sequenz–Container besitzten einige ausgezeichnete

Iteratoren:

17 42msw

begin() end()

iterator begin()

Liefert einen Iterator, der auf den Beginn des Vektors

zeigt.

iterator end()

Liefert einen Iterator, der auf das Ende des Vektors zeigt.

Ende bedeutet hier hinter das letzte Element des

Containers.

msw.insert(msw.begin(),100);

msw.insert(msw.end(),3);

$>> msw = (100,17,42,3)



Iteratoren verhalten sich ähnlich wie Zeiger

vector<window>::iterator first = msw.begin();

vector<window>::iterator last = msw.end();

while(first != last){

cout << *first;

first++;

}

$>> 100 17 42 3

• Wie ein Zeiger besitzt ein Iterator den

Dereferenzierungsoperatoroperator* . Er liefert den

Wert des Datentypes, der im Container verwaltet wird.

• Wie ein Zeiger kann ein Iterator mit dem Operator

operator++ inkrementiert werden (genaues vom

Iteratortyp abhängig).

Es wurde schon gesagt, daß über die Iteratoren Algorithmen

und Container entkoppelt werden, z.B. gibt es die

Möglichkeit, den Container zu sortieren. Der Bereich, der

sortiert werden soll, wird durch zwei Iteratoren

gekennzeichnet:

sort(msw.begin(),msw.end());

$>> msw = (3,17,42,100)

(algorithm einbinden, umsort() verwenden zu können.)



Weitere Konstruktoren und Zuweisung:

vector(size_type n, const T& t)

Erzeugt einen Vektor mitn Kopien der Datenstrukturt .

vector(const vector&)

Copy–Konstruktor

vector& operator=(const vector&)

Zuweisungsoperator

vector(InputIterator, InputIterator)

Erzeugt einen Vektor aus dem Wertebereich einesanderen Vektors

vector<window> v1 (3,17)

vector<window> v2 (msw);

vector<window> v3 = v2;

$>> v1 = (17,17,17) v2 = v3 = (3,17.42,1)

vector<window> v4 (msw.begin(),msw.end()-2);

$>> v4 = (3,17)

AuchVergleichsoperatorenexistieren. So lassen sich zweiVektoren über== auf Gleichheit überprüfen,< führt einenlexikographischen Vergleich durch (d.h. zuerst werden dieersten Elemente verglichen, bei Gleichheit die zweiten usw.).

Die übrigen Vergleichsoperatoren lassen sich aus diesenableiten (using namespace std::rel_ops ), z.B.



template <class T>

inline bool operator != (const T& x, const T& y)

{

return !(x == y);

}

Weitere Methoden:

reference front()

Liefert das erste Element des Vektors

cout << msw.front() << endl;

$>> 3

reference back()

Liefert das letzte Element des Vektors

void pop_back()

Entfernt das letzte Element des Vektors

void clear()

Entfernt alle Elemente des Vektors

bool empty() const

Liefert true , wennsize() == 0

insert(iterator p, size_type n, const T& x)

Einfügen vonn Kopien vonx vor die Position des

Iteratorsp



insert(iterator pos, InputIterator f,

InputIterator l)

Einfügen eines Bereiches[f...l] vor die Position

pos

erase(iterator f, iterator l)

Entfernen des Bereiches[f...l]

Achtung, Iteratoren können ungültig werden!

Containerklasselist

Darstellunglist

Eigenschaften:

• Sequenzklasse, die für das Einfügen und Löschen von

Elementen optimiert ist.

• Iteratoren bleiben dabei gültig.

• aus Effizienzgründen kein Index–Zugriff.

• vor– / rückwärts durchlaufbar (bidirectional iterator).



Containerklassedeque

Queue mit zwei Enden (double–ended queue). Diese istdahingehend optimiert, daß die Operationen an den beidenEnden so effizient wie bei Listen sind und der Index–Zugriffsich der Effizienz eines Vektors annähert.

Effizienz des Einfügens / Löschens:

Container Anfang mittendrin Ende

Vector linear linear konstant∗

List konstant konstant konstant

Deque konstant∗ linear konstant∗

∗ kann linear werden, wenn wegen Reallokation von Speicher

Elemente kopiert werden

Container Operation Iterator

vector insert Reallokation notwendig

alle Iteratoren ungültig

keine Reallokation – alle Iteratoren

vor Einfügeposition gültig

erase alle Iteratoren ab Position

an der gelöscht wird, ungültig



Container Operation Iterator

list insert alle Iteratoren bleiben gültig

erase nur Iteratoren auf das gelöschte

Element werden ungültig

deque insert alle Iteratoren werden ungültig

erase alle Iteratoren werden ungültig

15.3 Zusammenwirken derSTL–Komponenten

Mit Hilfe eines einfachen Programmes in verschiedenen

Varianten, soll das Wirken der STL–Komponenten

demonstriert werden:

In dem Programm soll ein per Dialog einzugebender

int –Wert in einem Array gefunden werden, wozu eine

Funktionfind() benutzt wird, der auch als Algorithmus

der STL vorliegt.

Die Beispiele wurden aus „Komponenten entwerfen mit der C++

STL“ von Ulrich Breymann, Addison–Wesley entnommen.



Ohne STL:

int main() {

const int Count = 100;

int aContainer[Count]; // define container

// pointer to the beginning

Iterator begin = aContainer;

// position after the last element

Iterator end = aContainer + Count;

// fill container with even numbers

for(int i = 0; i < Count; ++i)

aContainer[i] = 2*i;

int Number = 0;

while(Number != -1) {

cout << " enter required number (-1 = end):";

cin >> Number;

if(Number == -1) break;

Iterator pos = find(begin,end,Number);

if (pos != end)

cout << "found at position "

<< (pos - begin) << endl;

else

cout << Number << " not found!" << endl;

}}}



Der TypnameIterator ist hier als Zeiger aufint

vereinbart und soll die Ähnlichkeit von Zeigern und

Iteratoren ausdrücken:

typedef int* Iterator;

Der Algorithmusfind ist wie folgt implementiert:

Iterator find(Iterator begin,

Iterator end,

const int& Value) {

// pointer comparison &&

// dereferencing and object comparison

while(begin != end

&& *begin != Value)

++begin;

return begin;

}

• find() muß nichts über den Container wissen

• Der Iterator (Zeiger) benötigt einige wenige Fähigkeiten:

– Inkrement++

– Dereferenzierung*

– Vergleich über!=



Algorithmus find() als Template:

template<class Iteratortype, class T>

Iteratortype find(Iteratortype begin,

Iteratortype end,

const T& Value) {

// iterator comparison

// dereferencing and object comparison

while(begin != end && *begin != Value)

++begin;

return begin;

}

! Programm weiter lauffähig

! Der Algorithmus kann mit jeder Klasse von Iteratoren

zusammenarbeiten, die die Operationen!= und* zur

Verfügung stellen.

STL-Container vector:

Ersetze den Container durch einen Container der STL. DieIteratorenbegin undend werden durch die Methoden derKlassevector<T> ersetzt, die einen entsprechendenIterator zurückgeben.

#include <vector>

using namespace std;

typdef vector<int>::iterator Iterator;



int main() {

const int Count = 100;

vector<int> aContainer(Count); //!!!

for(int i = 0; i < Count; ++i)

aContainer[i] = 2*i;

int Number = 0;


cin >> Number;

if(Number == -1) break;

// globale Funktion find() benutzen

Iterator pos = ::find(aContainer.begin(),

aContainer.end(), Number);

if (position != aContainer.end())


<< (position - aContainer.begin());

else cout << Number << " not found!";

}}

• STL-Container arbeitet mit unseremfind() zusammen

• Mit Iteratoren ist Arithmetik möglich (Differenzbildung)

komplett mit STL

• Ersetze::find() durchfind() (d.h. Namespacestd ).

• Ergänze#include<algorithm> .

• Die typedef Anweisung ist nicht mehr notwendig



15.4 Interne Funktionsweise

• Verwendung einer selbstgeschriebenen Klasseslist ,

die sich wie ein Container der STL verhält.

• Die Klasse wird nicht vollständig definiert.

• Laufzeitverhalten unerheblich.

int main() {

const int count = 100;

slist<int> aContainer; // Container

// Container "von vorne" fuellen

for(int i = count; i >= 0; --i)

aContainer.push_front(2*i);

int Number = 0;


cin >> Number;

if (Number == -1) break;

slist<int>::iterator Position =

find(aContainer.begin(),aContainer.end(),

Number);

if(Position != aContainer.end())


<< (Position - aContainer.begin());

else cout << "not found\n";

}}



Defintion von slist

template<class T>

class slist {

public:

slist() : firstElement(0), Count(0) {}

void push_front(const T& Datum) {

firstElement =

new ListElement(Datum, firstElement);

++Count;}

private:

struct ListElement {

T Data;

ListElement *Next;

ListElement(const T& Datum,ListElement* p)

: Data(Datum), Next(p) {}

};

ListElement *firstElement;

size_t Count;

• push_front() erzeugt ein neues Listenelement undfügt es am Anfang der Liste ein.

• Listenelemente als geschachtelte öffentliche Klassestruct definiert. Zugriff von außerhalb nicht möglich.

• Elemente als einfach verkette Liste vorgehalten (keinOperator[] .



slist stellt Iterator zur Vefügung

public:

class iterator {

public:

iterator(ListElement* Init = 0)

: current(Init){}

// Dereferenzierung

T& operator*() {

return current->Data;}

const T& operator*() const {

return current->Data;}

// Praefix

iterator& operator++() {

if(current) // Ende erreicht?

current = current->Next;

return *this;}

// Postfix

iterator operator++(int) {

iterator temp = *this;

++*this;

return temp;}

Bemerkung:Innerhalb der Postfix-Variante des++–Operators

wird der Kopierkonstruktor benötigt. Die Präfix–Variante

sollte deshalb bevorzugt werden.



bool operator==(const iterator& x) const {

return current == x.current;}

bool operator!=(const iterator& x) const {

return current != x.current;}

// Differenzoperator

int operator-(Iterator fromWhere){

int count = 0;

while(fromWhere.current != current

&& fromWhere.current != 0){

++count;

++fromWhere;}

return count;

}

private:

// Zeiger auf aktuelles Element

ListElement* current;

}; // class iterator

Bemerkung:Die Differenz zwischen zwei Iteratoren ist durchdie Anzahl der Inkrementierungen gegeben, die benötigtwerden, um vom ersten Iterator zum zweiten zu gelangen.

public:

iterator begin() const

{ return iterator(firstElement);}

iterator end() const { return iterator();}


Documents

15.1 Konzept der STL - zaik.uni-koeln.de fileZentrum für Angewandte Informatik Köln Arbeitsgruppe Faigle/Schrader Universität zu Köln15 Standard Template Library (STL) 15.1 Konzept