Standard Template Library

Die STL (Abkürzung für englisch standard template library) ist eine weitgehend auf generischer Programmierung basierende Programmbibliothek für die Programmiersprache C++ mit dem Schwerpunkt Datenstrukturen und Algorithmen.

Die STL wurde ursprünglich bei Hewlett-Packard (HP) entwickelt und zu weiten Teilen in die so genannte C++-Standardbibliothek der Programmiersprache C++ übernommen.

Die STL und die C++-Standardbibliothek

Anders als die C++-Standardbibliothek ist die STL nicht Bestandteil der Programmiersprache C++. Die STL unterliegt auch keiner Norm, und dadurch bedingt ist der Begriff STL nicht eindeutig definiert. Im Gegensatz zur C++-Standardbibliothek hat der Wortbestandteil "standard" in standard template library nichts mit "Standard" im Sinne einer Norm zu tun.

Alexander Stepanov und Meng Lee, damals Mitarbeiter bei Hewlett-Packard, nannten die von ihnen entwickelte Template-Bibliothek STL. Später wurde die STL gemeinfrei. Danach, im Jahr 1993, also zu einer Zeit als sich C++ noch in einem frühen Entwicklungsstadium befand, wurde vorgeschlagen, C++ um Funktionalität der STL zu erweitern. Die Einzelheiten dieses Vorschlags wurden im Laufe der Zeit vom C++-Standardisierungskomitee ausgearbeitet, was schließlich zur Integration führte.

Stepanov wechselte später zu Silicon Graphics (SGI) und setzte auch danach die Arbeiten an seiner Bibliothek fort.

Von der heutigen C++-Bibliothek, stammt zwar ein Großteil aus der STL in ihrer bei HP entwickelten Fassung auf dem Stand von 1993; in verschiedenen Details unterscheidet sie sich aber davon. Aus diesem Grund ist es nicht möglich, eine Untermenge der C++-Standardbibliothek als STL zu benennen. Auch enthielt die STL in der damaligen Fassung weder Zeichenketten (Strings) noch Ein-/Ausgabedatenströme (Streams). In der C++-Norm kommt der Begriff STL nicht vor.

Inoffiziell hat die Bezeichnung STL weite Verbreitung. Die unterschiedlichen Vorstellungen über die Bedeutung dieses Begriffs führen aber bisweilen zu Missverständnissen. Bei SGI ist damit beispielsweise die dort veröffentlichte Bibliothek gemeint.

Bestandteile der STL

Die STL unterscheidet:

Wie der Name bereits andeutet, ist nahezu jede Komponente der STL ein Template. Das Template-Konzept hat den großen Vorteil der Wiederverwendbarkeit, d. h. zum Beispiel, dass jeder Container (nahezu) beliebige Objekte aufnehmen kann, bzw. Algorithmen für eine ganze Reihe von Datentypen gelten.

Container

Container (Behälterklassen) sind Datenstrukturen, die aus einer Anzahl verschiedener Objekte des selben Datentyps bestehen. Die grundlegenden Container der STL sind:

Vektoren (engl. vector)
Doppelt-verkettete Listen (engl. list)
Warteschlangen (engl. queue)
Stapel (engl. stack)
Mengen (engl. set)
Abbildungen (engl. map)

Iteratoren

Jeder Container verfügt über verallgemeinerte Zeiger, die so genannten Iteratoren (lateinisch iterare: wiederholen), mit deren Hilfe auf einzelne Elemente des Containers zugegriffen werden kann. Bezogen auf ihre Aufgabe sind die Iteratoren reine Zugriffsobjekte. Sie entkoppeln die Algorithmen von den Daten, so dass diese typenunabhängig werden. Bei den Iteratoren gibt es folgende Kategorien:

Eingabe-Iteratoren : lesenden Zugriff für einen einzelnen Durchlauf
Ausgabe-Iteratoren : schreibender Zugriff für einen einzelnen Durchlauf
Forward-Iteratoren : sequentieller Zugriff mit relativem Bezug auf Iteratoren, in eine Richtung
Bidirektionale Iteratoren : wie Forward-Iteratoren jedoch in beide Richtungen
Iteratoren mit wahlfreiem Zugriff: wahlfreier Zugriff, auch mit Index-Operator ([])

Algorithmen

Algorithmen sind Funktionen mit bestimmten Manipulationsvorschriften, die auf einen Container angewendet werden. Dabei sind sie unabhängig von der speziellen Implementierung der Container. Sie können nur über Iteratoren auf die Elemente in den Containern zugreifen. Sie enthalten u. a. die Standard-Algorithmen der Informatik, wie z. B. Sortieralgorithmen oder Verfahren zur Erzeugung von Zufallszahlen. Die meistbenutzten sind:

for_each : wendet eine Operation auf alle Elmente eines Datensatzes an
transform : transformiert einen Datensatz mit einer Funktion in einen anderen
copy : kopiert den Datensatz in einen anderen
sort : sortiert den Datensatz

Funktionsobjekte

Bei Funktionsobjekten oder Funktoren handelt es sich um Objekte, die genauso aufgerufen werden können wie Funktionen. Bei ihnen ist der Funktionsoperator () mit der Operatorfunktion "operator(){}" überladen. Es sind Objekte, die sich wie Funktionen verhalten, aber trotzdem alle Eigenschaften von Objekten haben. Bei den Funktionsobjekten gibt es folgende Kategorien:

Generatoren ohne Funktionsparameter f()
Unäre Funktionen mit einem Funktionsparameter f(x)
Binäre Funktionen mit zwei Funktionsparametern f(x,y)

Grundsätzlich benötigen die Algorithmen der STL keine Funktionsobjekte mit mehr als zwei Parametern.

Beispiele

std::vector<int> daten(10);         //Datenfeld mit int der Länge 10 anlegen
std::vector<int>::iterator dIter;   //Iterator anlegen
dIter = daten.begin();              //Iterator zeigt auf ersten Eintrag

for( int i=0;                 //Zähler i initialisieren, 
     dIter != daten.end();    //for-Schleife solange durchgehen, bis dIter aufs Ende des Datenfelds zeigt
     ++i, ++dIter ) {         //Zähler i erhöhen, Iterator auf nächsten Eintrag zeigen lassen
        *dIter = i;           //i dem Datenfeld zuweisen, auf das dIter zeigt
}
//daten: 0 1 2 3 4 5 6 7 8 9

std::vector<int> datenZwei(10);

std::copy( daten.begin(), daten.end(), //welche Daten sollen kopiert werden
           datenZwei.begin() );        //und wohin
//datenZwei: 0 1 2 3 4 5 6 7 8 9

//binärer Funktor std::multiplies<int>() braucht zwei Argumente
std::transform( daten.begin(), daten.end(), //auf welchem Bereich soll Algorithmus arbeiten
                datenZwei.begin(),          //zweite Datenquelle
                datenZwei.begin()           //wohin sollen Ergebnisse gehen
                std::multiplies<int>()  );  //miteinander multiplizieren
//datenZwei: 0 1 4 9 16 25 36 49 64 81

//unärer Funktor std::negate<int>() braucht ein Argument
std::transform( daten.begin()+4, daten.end(), //diesmal nicht von vorne, sondern vom fünftem Element an
                daten.begin(),
                std::negate<int>() );  //Negation
//daten: 0 1 2 3 -4 -5 -6 -7 -8 -9

std::sort( daten.begin(), daten.end() ); //sortieren
//daten: -9 -8 -7-6 -5 -4 0 1 2 3

Weblinks