Copyright Addison Wesley Longman 1999

Vorwort zur 2. Auflage

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

zurück


Vorwort

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:
mailadresse
 

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

zurück