Copyright Addison Wesley Longman 1999
1815 verlor Napoleon in der Nähe eines kleinen Ortes namens Waterloo im heutigen Belgien eine entscheidende Schlacht gegen Wellington und Blücher. Seitdem verbindet man mit dem Wort "Waterloo" katastrophale Niederlagen. Nicht so im Falle der STL: 1994 wurde in einer kleinen Stadt namens Waterloo in Ontario die STL als Teil des ISO/ANSI -Standards akzeptiert, und kaum jemandem ist dieses Ereignis als Fehlschlag in Erinnerung geblieben. Ganz im Gegenteil. Seit jenem Sommer hat sich die STL ihren Platz als eine der beliebtesten C++ -Basisbibliotheken erobert.
Die STL ist das Ergebnis jahrelanger Forschungsarbeiten bei Hewlett-Packard. Bjarne Stroustrup hat Alexander Stepanov und Meng Lee darin bestärkt, das Resultat ihrer Arbeit dem C++ -Standardisierungskomitee als Teil der C++-Standardbibliothek vorzuschlagen. Von dieser Idee waren bei weitem nicht alle Komiteemitglieder begeistert. Bei jenem legendären Treffen in Waterloo wurde der Vorschlag kontrovers und zum Teil recht emotional diskutiert. Dennoch ging die STL aus dieser Entscheidungsschlacht siegreich hervor und wurde als Teil des ISO/ANSI -Standards akzeptiert. Allerdings wurde daran die Bedingung geknüpft, daß der Quellcode der STL öffentlich zugänglich gemacht werden muß. Und so geschah es auch.
Seitdem steht der C++-Welt mit der STL eine umfangreiche Klassenbibliothek zur Verfügung. Viele -Programmierer haben sich dafür interessiert, daran Gefallen gefunden, und einige können sich kaum noch vorstellen, ihre Arbeit ohne eine Basisbibliothek wie die STL erledigen zu können. Der offensichtlichste Wert der STL liegt in den Datenstrukturen und Algorithmen, die sie zur Verfügung stellt. Darüber hinaus fungiert sie aber auch als Framework, das Programmierer um eigene Komponenten erweitern können. Diese Flexibilität wurde durch ein intelligentes Konzept erreicht, das heute als "Generisches Programmieren" bekannt ist. Insgesamt zeichnet sich die STL durch eine konsistente, elegante und daher gut verständliche Architektur aus. Im Zuge der Standardisierung hat sich die STL natürlich verändert, so daß die heutige Standard-STL von der Waterloo-Version an einigen Stellen deutlich abweicht. An der Grundidee hat sich aber nichts geändert.
Als Ulrich mich im Herbst 1995 fragte, ob ich Lust hätte, das Buch zusammen mit ihm zu schreiben, war mein erster Gedanke: Braucht die Welt wirklich noch ein STL-Buch? Drei Bücher zu diesem Thema waren zu jener Zeit bereits auf dem Markt. Ich selbst war heftig damit beschäftigt, das Wissen über die STL weiterzugeben: eine regelmäßige Kolumne im Report, Konferenzenvorträge, und Vorbereitung und Durchführung von STL-Kursen im Auftrag meines damaligen Arbeitgebers. Meiner Meinung nach gab also genug Quellen für STL-interessierte Programmierer. Ungefähr ein Jahr später hielt ich dann die erste Auflage der (inzwischen ins Englische) übersetzten deutschen Ausgabe in der Hand, überflog die Seiten und begann zu lesen - mit zunehmendem Vergnügen, wie ich zugeben muß. Im Gegensatz zu den STL-Büchern, die ich bis dahin gesehen hatte, geht dieses Buch über die bloße Einführung in die STL hinaus. Es erklärt Techniken zur Implementierung eigener Datenstrukturen und Algorithmen auf Basis der STL, und dieser Ansatz nutzt die STL als das, was sie ist - ein Framework. Endlich einmal ein Buch, das diesen wichtigen Aspekt beschreibt. Die Welt brauchte also doch noch ein weiteres STL-Buch.
Wie erwartet, beginnt das Buch mit einer Einführung in die STL, wie man sie auch in anderen Veröffentlichungen findet. Allerdings erlauben bereits die ersten Erläuterungen den Blick hinter die Kulissen der STL. Es werden Interna wie zum Beispiel die typische Implementierung eines Iterators beschrieben. Diese Art von Information ist wichtig und wesentlich, um Leserinnen und Leser zu befähigen, den Bereich bloßer Benutzung der STL zu verlassen und das STL-Framework um eigene Containerklassen und Algorithmen zu erweitern. Der für mich spannendste Teil des Buchs ist Teil III "Über die STL hinaus". Dort werden elegante und durchdachte Erweiterungen auf Basis der STL gezeigt, darunter bekannte Datenstrukturen wie Matrizen, Graphen und Hash-Tabellen.
Die nun vorliegende zweite Auflage ist eine der aktuellsten Informationsquellen zur STL. Sie reflektiert den kürzlich verabschiedeten C++ -Standard. Mittlerweile gibt es Compiler, die den größten Teil des -Sprachstandards verstehen und damit in der Lage sind, die STL und ihre Anwendungen zu übersetzen. Die Beispiele des Buchs sind daher alle übersetzbar und lauffähig.
Alles in allem habe ich das Buch mit Freude gelesen und schätze es als fundierte und seriöse Informationsquelle zur STL.
Angelika Langer
Juli 1998
Die Standard Template Library (STL)
Einer der Erfolge von beruht darauf, daß
mittlerweile zahlreiche Bibliotheken (libraries) am Markt vorhanden
sind, die die Entwicklung von Programmen erheblich erleichtern,
weil sie verläßliche und erprobte Komponenten anbieten.
Eine besonders sorgfältig konstruierte Bibliothek ist die
Standard Template Library, die bei Hewlett-Packard von
Alexander Stepanov, Meng Lee und ihren Kollegen entwickelt wurde.
Sie ist vom ANSI/ISO-Komitee als Teil des C++ -Standards
[ISO/IEC14882] akzeptiert worden.
Ihr Schwerpunkt liegt auf Datenstrukturen für Behälter
Container und Algorithmen, die damit arbeiten. Das technische
Referenzdokument der STL ist in modifizierter Form im C++ -Standard
enthalten. Beide bilden die Grundlage für die ersten beiden
Teile dieses Buchs. Das Dokument ist frei benutzbar
einschließlich der Vervielfältigung, wenn die
Copyright-Bedingungen angegeben werden. Diese Bedingungen sowie
Hinweise auf Quellen sind im Anhang zu finden.
Die C++ Standardbibliothek und die STL
Die STL umfaßt nicht die gesamte C++ -Standardbibliothek und auch nicht alle ihre Templates, sie stellt aber den wichtigsten und interessantesten Teil dar. Die C++ -Standardbibliothek umfaßt mehrere Gebiete:
Der rot gekennzeichnete Bereich ist das Thema dieses Buchs - mit anderen Worten, das Buch behandelt nicht die historische STL, sondern den Teil der C++ -Standardbibliothek, der aus der STL entstanden ist. Dabei liegt neben einer Einführung der Schwerpunkt auf beispielhaften Anwendungen und der Konstruktion neuer Komponenten auf Basis der STL.
Dieser Teil der C++ -Standardbibliothek stimmt wegen einiger
Änderungen durch das ISO/ANSI-Standardkomitee nicht mehr genau
mit der ursprünglichen STL überein. Ein genauerer, wenn
auch zu langer Titel, für dieses Buch wäre daher
Komponenten entwerfen mit der C++ -Standardbibliothek - Eine
Einführung in generische Algorithmen und Datenstrukturen, ihre
Anwendungen und die Konstruktion neuer Komponenten. Die
Änderungen betreffen nur Einzelheiten, aber nicht das Konzept,
weswegen der Name Standard Template Library und die
Abkürzung STL beibehalten werden.
Die STL als Framework
Die STL ist eine Allzweck-Library mit dem Schwerpunkt auf
Datenstrukturen und Algorithmen, die den Template-Mechanismus zur
Parametrierung von Komponenten nutzt. Die einheitliche Art der
Schnittstellen erlaubt eine flexible Zusammenarbeit der Komponenten
und auch die Konstruktion neuer Komponenten im STL-Stil. Damit
stellt die STL ein universell einsetzbares und erweiterbares
Framework dar, dessen Benutzung Vorteile in Bezug auf
Qualität, Verläßlichkeit, Effizienz und
Produktivität bietet. Das erfolgreiche Konzept ist bereits
kopiert worden, wie die Java Generic Library zeigt.
Ziel des Buchs
Das Buch hat zwei Ziele. Das oben angegebene Referenzdokument ist als technische Spezifikation kaum geeignet, die Konzepte der STL zu erklären. Das erste Ziel ist daher zu vermitteln, wie die STL sinnvoll genutzt werden kann. Interne Details der STL werden soweit dargestellt, wie sie zum Verständnis der Funktionsweise nötig sind.
Das Buch geht jedoch über eine Einführung deutlich
hinaus: Zweitens soll die Anwendung der STL als Werkzeugkasten
demonstriert werden, indem an ausführlichen Beispielen gezeigt
wird, wie mächtigere und teilweise schnellere Komponenten
zusammengebaut werden können. Diese Komponenten sind
komplexere Datenstrukturen und Algorithmen, die mit den Bausteinen
der STL effektiv implementiert werden. Die Algorithmen werden
bezüglich ihrer Laufzeiteigenschaften in Abhängigkeit von
der Menge der zu verarbeitenden Daten abgeschätzt
(Zeitkomplexität). Es sind aber nicht nur die Bausteine selbst
und ihre Kombination interessant, sondern auch die in der STL und
diesem Buch angewendete Programmiertechnik.
Für wen ist dieses Buch geschrieben?
Dieses Buch ist für alle geschrieben, die mit der
Entwicklung von Software in zu tun haben, sei es als
Systemdesigner, Projektmanager, Informatikstudent oder
Programmierer. Um Software portabel, wartbar und wiederverwendbar
zu gestalten, ist die Einhaltung und Nutzung von gültigen
Standards unbedingt anzuraten - sonst bräuchte man keine. Die
Benutzung vorgefertigter Komponenten wie die der STL erhöht
die Zuverlässigkeit der Software und die Produktivität
der Entwickler. Voraussetzung zum Verständnis dieses Buchs
sind Kenntnisse der Programmiersprache und ihres
Template-Mechanismus, wie sie durch aktuelle, am Standard
orientierte Lehrbücher vermittelt werden, zum Beispiel das
Buch "C++ - Eine Einführung" vom
selben Autor.
Aufbau des Buchs
Das Buch gliedert sich in drei Teile. Der erste Teil führt in die STL ein und beschreibt ihre Konzepte und Elemente, wobei der Schwerpunkt auf Iteratoren und Containern liegt. Beide bilden die Grundlage für das Arbeiten der Algorithmen.
Der zweite Teil diskutiert die Standard-Algorithmen, wobei fast allen Algorithmen Beispiele zugeordnet sind. Er ist wegen der Vielzahl der beschriebenen Algorithmen eher als Katalog zum Nachschlagen zu betrachten.
Der dritte Teil beschreibt Anwendungen und Erweiterungen. Anhand
ausführlicher Beispiele wird gezeigt, wie mit Hilfe der
Bausteine, die die STL liefert, komplexere Datenstrukturen und
Algorithmen sowie mächtige abstrakte Datentypen entworfen
werden können.
Beispiele
Es wird nicht nur die Wirkungsweise von Elementen der STL beschrieben, sondern zu fast jedem Element sowie zu den Anwendungen des dritten Teils wird jeweils ein lauffähiges Beispiel präsentiert, das auf dem Rechner der Leserin bzw. des Lesers nachvollziehbar ist. Damit ist die Grundlage für eigenes Experimentieren und ein vertieftes Verständnis geschaffen. Die Beispiele sind auf der beiliegenden CD-ROM zu finden, aber auch über das Internet erhältlich.
Hinweise
Die Public-domain-Implementierung der STL von Hewlett-Packard unterscheidet sich in einigen Punkten vom -Standard, weil nach Integration der STL Änderungen und Ergänzungen vorgenommen wurden. Mittlerweile sind auch andere Implementierungen verfügbar, wie zum Beispiel die von Silicon Graphics oder die von RogueWave. Es ist zu erwarten, daß einige Zeit nach Veröffentlichung des International Standards die Compilerhersteller eine standardkonforme Implementierung der STL mitliefern werden, so daß Unterschiede in verschiedenen Implementierungen nur noch eine sehr untergeordnete Rolle spielen. Schon jetzt existieren weitgehend standardkonforme Compiler (siehe zum Beispiel www.edg.com). Aus diesem Grund bezieht sich dieses Buch konsequent auf das Standard-Dokument [ISO/IEC14882].
Im Text sind programmtechnische Dinge wie Variablen,
Schlüsselwörter, und Programmbeispiele durch diese
Schreibweise gekennzeichnet. Erläuterungen, die den Text
eines Programms unterbrechen, werden als eingerückter
Kommentar, gekennzeichnet durch /* ... */, kenntlich
gemacht. Die Namen von Dateien sind kursiv und
Bildschirmausgaben in Schrägschrift gedruckt. Ein
Symbol für eine Glühbirne markiert einen wichtigen
Hinweis oder Tip zur Programmierung.
Anregungen und Kritik
sind erwünscht. Wenn Sie Fehler mitteilen oder Anregungen
und Kritik äußern möchten, können Sie den
Autor über den Verlag oder direkt erreichen:
Danksagung
Von meinen Kollegen Ulrich Eisenecker (Fachhochschule
Heidelberg), Bernd Owsnicki-Klewe (Fachhochschule Hamburg) und
Andreas Spillner (Hochschule Bremen) sowie von Andreas Scherer
(RWTH Aachen) habe ich etliche Anregungen erhalten, und ich danke
ihnen sehr für die kritische und gründliche Durchsicht
des Manuskripts und viele hilfreiche Hinweise. Sämtliche
übriggebliebenen Schwächen und Fehler bleiben
natürlich trotzdem Verdienst des Autors.
Ulrich Breymann
Bremen, im September 1998