Standard Template Library (STL) ist ein C ++ Softwarebibliothek, die schwer viele Teile des C ++ Standardbibliothek beeinflusst hat. Es stellt vier Bestandteile genannt Algorithmen, Behälter, funktionell, und iterators zur Verfügung.

Der STL stellt einen Konfektionssatz von allgemeinen Klassen für C ++, wie Behälter und assoziative Reihe zur Verfügung, die mit jedem eingebauten Typ und mit jedem benutzerbestimmten Typ verwendet werden kann, der einige elementare Operationen (wie das Kopieren und die Anweisung) unterstützt. STL Algorithmen sind von Behältern unabhängig, der bedeutsam die Kompliziertheit der Bibliothek reduziert.

Der STL erreicht seine Ergebnisse durch den Gebrauch von Schablonen. Diese Annäherung stellt Übersetzungszeit polymorphism zur Verfügung, der häufig effizienter ist als traditionelle Durchlaufzeit polymorphism. Moderne C ++ Bearbeiter werden abgestimmt, um jede Abstraktionsstrafe zu minimieren, die aus dem schweren Gebrauch des STL entsteht.

Der STL wurde als die erste Bibliothek von allgemeinen Algorithmen und Datenstrukturen für C ++ mit vier Ideen im Sinn geschaffen: allgemeine Programmierung, Abstraktheit ohne Verlust der Leistungsfähigkeit, des Berechnungsmodells von Von Neumann und der Wertsemantik.

Zusammensetzung

Behälter

Der STL enthält Folge-Behälter und assoziative Behälter. Die Standardfolge-Behälter schließen ein, und. Die assoziativen Standardbehälter sind, und.

Es gibt auch Behälteradapter, und, die Behälter mit der spezifischen Schnittstelle mit anderen Behältern als Durchführung sind.

Iterators

Der STL führt fünf verschiedene Typen von iterators durch. Diese werden iterators eingegeben (der nur verwendet werden kann, um eine Folge von Werten zu lesen), Produktion iterators (kann der nur verwendet werden, um eine Folge über Werte zu schreiben), schicken Sie iterators nach (der gelesen, dem geschrieben werden und vorankommen kann), bidirektionaler iterators (sind die fortgeschrittenem iterators ähnlich, aber können sich auch umgekehrt bewegen), und s (kann der frei jede Zahl von Schritten in einer Operation bewegen).

Es ist möglich, bidirektionale Iterators-Tat wie zufälliger Zugang iterators zu haben, weil Fortbewegung von zehn Schritten durch die einfache Fortbewegung eines Schritts auf einmal insgesamt zehnmal getan werden konnte. Jedoch verschiedenen zufälligen Zugang habend, bietet iterators Leistungsfähigkeitsvorteile an. Zum Beispiel würde ein Vektor einen zufälligen Zugang iterator, aber eine Liste nur ein bidirektionale iterator haben.

Iterators sind die Haupteigenschaft, die die Allgemeinheit des STL erlauben. Zum Beispiel kann ein Algorithmus, um eine Folge umzukehren, mit bidirektionalem iterators durchgeführt werden, und dann kann dieselbe Durchführung auf Listen, Vektoren und deques verwendet werden. Benutzergeschaffene Behälter müssen nur einen iterator zur Verfügung stellen, der einen des fünf Standards iterator Schnittstellen durchführt, und alle im STL zur Verfügung gestellten Algorithmen auf dem Behälter verwendet werden können.

Diese Allgemeinheit kommt auch an einem Preis zuweilen. Zum Beispiel kann das Durchführen einer Suche auf einem assoziativen Behälter wie eine Karte oder Satz iterators viel langsamer verwenden als durch das Nennen von Mitglied-Funktionen angeboten durch den Behälter selbst. Das ist, weil Methoden eines assoziativen Behälters Kenntnisse der inneren Struktur ausnutzen können, die zu Algorithmen mit iterators undurchsichtig ist.

Algorithmen

Eine Vielzahl von Algorithmen, um Operationen wie Suche und das Sortieren durchzuführen, wird im STL, jeder durchgeführt zur Verfügung gestellt, um ein bestimmtes Niveau von iterator zu verlangen (und wird deshalb an jedem Behälter arbeiten, der eine Schnittstelle durch iterators zur Verfügung stellt).

Functors

Der STL schließt Klassen ein, die den Funktionsmaschinenbediener überladen. Klassen, die das tun, werden functors oder Funktionsgegenstände genannt. Sie sind nützlich, um Zustandinformation in in andere Funktionen passierten Funktionen zu behalten und wiederzubekommen. Regelmäßige Funktionszeigestöcke können auch als functors verwendet werden.

Ein besonders allgemeiner Typ von functor ist das Prädikat. Zum Beispiel mögen Algorithmen nehmen ein unäres Prädikat, das auf den Elementen einer Folge funktioniert. Algorithmen wie Sorte, partial_sort, nth_element und alle sortierten Behälter verwenden ein binäres Prädikat, das eine strenge schwache Einrichtung zur Verfügung stellen muss, d. h. muss sie sich wie ein Mitgliedschaft-Test auf einem transitiven, irreflexive und antisymmetrischer binärer Beziehung benehmen. Wenn niemand geliefert wird, verwenden diese Algorithmen und Behälter weniger standardmäßig, der der Reihe nach weniger als Maschinenbediener Vor 1987 ruft, hatten Stepanov und Musser entwickelt und eine Bibliothek von Ada für die Liste veröffentlicht, die in einer Prozession geht, der die Ergebnisse von viel von ihrer Forschung über die allgemeine Programmierung aufgenommen hat. Jedoch hatte Ada viel Annahme außerhalb der Verteidigungsindustrie nicht erreicht, und C ++ ist wahrscheinlicher geschienen, weit verwendet zu werden und gute Unterstützung für die allgemeine Programmierung zur Verfügung zu stellen, wenn auch die Sprache relativ unreif war. Ein anderer Grund dafür, sich C ++ zuzuwenden, den Stepanov bald anerkannt hat, war der C/C ++ Modell der Berechnung, die sehr flexiblen Zugang zur Lagerung über Zeigestöcke erlaubt, die für das Erzielen der Allgemeinheit entscheidend ist, ohne Leistungsfähigkeit zu verlieren.

Viel Forschung und Experimentieren waren erforderlich, um nicht nur individuelle Bestandteile zu entwickeln, aber eine gesamte Architektur für eine auf der allgemeinen Programmierung gestützte Teilbibliothek zu entwickeln. Zuerst an AT&T Glockenlaboratorien und später an Forschungslaboratorien von Hewlett Packard (HP) hat Stepanov mit vielen architektonisch und Algorithmus-Formulierungen, zuerst in C und später in C ++ experimentiert. Musser hat in dieser Forschung zusammengearbeitet, und 1992 hat sich Meng Lee dem Projekt von Stepanov am HP angeschlossen und ist ein Hauptmitwirkender geworden.

Diese Arbeit hätte zweifellos für einige Zeit fortgesetzt, gerade ein Forschungsprojekt zu sein, oder am besten wäre auf einen HP Eigentumsbibliothek hinausgelaufen, wenn sich Andrew Koenig von Glockenlaboratorien der Arbeit nicht bewusst geworden wäre und Stepanov gebeten hätte, die Hauptideen auf einer Sitzung im November 1993 des ANSI/ISO Komitees für C ++ Standardisierung zu präsentieren. Die Antwort des Komitees war überwältigend günstig und hat zu einer Bitte von Koenig für einen formellen Vorschlag rechtzeitig für die Sitzung im März 1994 geführt. Trotz der enormen Zeitnot sind Alex und Meng im Stande gewesen, einen Draftvorschlag zu erzeugen, der einleitende Billigung auf dieser Sitzung erhalten hat.

Das Komitee hatte mehrere Bitten um Änderungen und Erweiterungen (einige von ihnen größer), und eine kleine Gruppe von Komitee-Mitgliedern, die mit Stepanov und Lee getroffen sind, um zu helfen, die Details auszuarbeiten. Wie man zeigen musste, haben die Voraussetzungen für die bedeutendste Erweiterung (assoziative Behälter) entsprochen, indem sie sie, eine Aufgabe an Musser delegierter Stepanov völlig durchgeführt worden ist. Es wäre für das ganze Unternehmen ziemlich leicht gewesen, aus der Kontrolle an diesem Punkt zu spinnen, aber wieder haben Stepanov und Lee die Herausforderung entsprochen und haben einen Vorschlag erzeugt, der Endbilligung im Juli 1994 ANSI/ISO Ausschusssitzung erhalten hat. (Zusätzliche Details dieser Geschichte können in Stevens gefunden werden.) Nachher wurde das Dokument 17 von Stepanov und Lee in den ANSI/ISO C ++ Draftstandard (1, Teile von Klauseln 17 bis 27) vereinigt. Es hat auch andere Teile des C ++ Standardbibliothek wie die Schnur-Möglichkeiten beeinflusst, und einige der vorher angenommenen Standards in jenen Gebieten wurden entsprechend revidiert.

Trotz des Erfolgs von STL mit dem Komitee, dort ist die Frage dessen geblieben, wie STL seinen Weg in die wirkliche Verfügbarkeit und den Gebrauch machen würde. Mit dem STL Voraussetzungsteil des öffentlich verfügbaren Draftstandards konnten Bearbeiter-Verkäufer und unabhängige Softwarebibliotheksverkäufer natürlich ihre eigenen Durchführungen entwickeln und sie als getrennte Produkte oder als Verkauf von Punkten für ihre anderen Waren auf den Markt bringen. Einer der Autoren der Erstausgabe, Atul Sainis, war unter dem ersten, um das kommerzielle Potenzial anzuerkennen, und hat begonnen, es als eine Branche für seine Gesellschaft, Modena Software Incorporated sogar zu erforschen, bevor STL vom Komitee völlig akzeptiert worden war.

Die Aussichten für die frühe weit verbreitete Verbreitung von STL wurden mit der Entscheidung von Hewlett Packard beträchtlich verbessert, seine Durchführung frei verfügbar im Internet im August 1994 zu machen. Diese Durchführung, die von Stepanov, Lee, und Musser während des Standardisierungsprozesses entwickelt ist, ist die Basis von vielen Durchführungen geworden, die durch den Bearbeiter und die Bibliotheksverkäufer heute angeboten sind.

Kritiken

Qualität der Durchführung

Quality of Implementation (QoI) des C ++ Bearbeiter hat einen großen Einfluss auf Brauchbarkeit von STL (und Templated-Code im Allgemeinen):

• Fehlermeldungen, die mit Schablonen verbunden sind, neigen dazu, sehr lang und schwierig zu sein, zu entziffern. Dieses Problem ist so streng betrachtet worden, dass mehrere Werkzeuge geschrieben worden sind, die vereinfachen und prettyprint STL-zusammenhängende Fehlermeldungen, um sie verständlicher zu machen.
• Der unbesonnene Gebrauch von STL Schablonen kann führen, um bloat zu codieren. Das ist mit speziellen Techniken innerhalb der STL Durchführung entgegnet worden (void* Behälter innerlich verwendend), und durch die Besserung von durch Bearbeiter verwendeten Optimierungstechniken.
• Schablone instantiation neigt dazu, Übersetzungszeit und Speichergebrauch (sogar durch eine Größenordnung) zu vergrößern. Bis sich die Bearbeiter-Technologie genug verbessert, kann dieses Problem nur durch das sehr sorgfältige Codieren und Vermeiden bestimmter Idiome teilweise beseitigt werden.

Andere Probleme

• Die Initialisierung von STL Behältern mit Konstanten innerhalb des Quellcodes ist nicht so leicht, wie Datenstrukturen von C (gerichtet in C ++ 11 mit Initialisierungsprogramm-Listen) geerbt haben.
• STL Behälter sind nicht beabsichtigt, um als Grundklassen verwendet zu werden (ihre destructors sind absichtlich nichtvirtuell); auf einen Behälter zurückzuführen zu sein, ist ein häufiger Fehler.
• Das Konzept von iterators, wie durchgeführt, durch STL kann schwierig sein, zuerst zu verstehen: Zum Beispiel, wenn ein Wert, der auf durch den iterator angespitzt ist, gelöscht wird, ist der iterator selbst dann nicht mehr gültig. Das ist eine allgemeine Quelle von Fehlern. Die meisten Durchführungen des STL stellen eine Fehlersuchprogramm-Weise zur Verfügung, die langsamer ist, aber solche Fehler, wenn verwendet, ausfindig machen kann. Ein ähnliches Problem besteht auf anderen Sprachen, zum Beispiel Java. Reihen sind als eine sicherere, flexiblere Alternative zu iterators vorgeschlagen worden.
• Bestimmte Wiederholungsmuster stellen zum STL iterator Modell nicht kartografisch dar. Zum Beispiel, Rückrufaktionsenumeration APIs kann nicht gemacht werden, das STL Modell ohne den Gebrauch von Koroutinen zu passen, die von der Plattform abhängig oder nicht verfügbar sind, und außerhalb des C ++ Standard sind.
• Bearbeiter-Gehorsam versichert nicht, dass Verteiler Gegenstände, die für das Speichermanagement für Behälter verwendet sind, mit dem zustandabhängigen Verhalten arbeiten wird. Zum Beispiel kann eine tragbare Bibliothek keinen Verteiler-Typ definieren, der Gedächtnis von verschiedenen Lachen mit verschiedenen Verteiler-Gegenständen dieses Typs ziehen wird. (Meyers, p. 50) (gerichtet in C ++ 11).
• Der Satz von Algorithmen ist nicht abgeschlossen: Zum Beispiel wurde der Algorithmus ausgelassen, obwohl er in C ++ 11 hinzugefügt worden ist.
• Die Schnittstelle von einigen Behältern (in der besonderen Schnur) wird diskutiert, um aufgebläht zu sein (Sutter und Alexandrescu, p. 79); andere werden diskutiert, um ungenügend zu sein.
• Behälter von Hashing wurden aus dem ursprünglichen Standard ausgeschlossen, aber sind in C ++ 11 und im Technischen Bericht 1, einer neuen Erweiterung auf C ++ hinzugefügt worden.

Durchführungen

• Ursprüngliche STL Durchführung durch Stepanov und Lee. 1994, Hewlett Packard. Nicht mehr aufrechterhalten.
• SGI STL, gestützt auf der ursprünglichen Durchführung durch Stepanov & Lee. 1997, Silikongrafik. Nicht mehr aufrechterhalten.
• libstdc ++ vom Gnu (war ein Teil von libg ++)
• libc ++ vom Klappern
• STLPort, der auf SGI STL gestützt ist
• Schelm-Welle-Standardbibliothek (HP, SGI, SunSoft, Siemens-Nixdorf)
• Reelle STL Bibliothek durch P.J. Plauger
• Der Microsoft STL, welche Schiffe mit Visuellem C ++ eine lizenzierte Ableitung des STL von Dinkum sind.
• Apache C ++ Standardbibliothek (Zeigen die Urheberrechtszeichen in den Quelldateien an, dass das auf - oder dasselbe als - die Schelm-Welle-Standardbibliothek basiert.)

Siehe auch

• Liste von C ++ Schablone-Bibliotheken
• C ++ 11
• Erhöhen Sie C ++ Bibliotheken
• qlibc

Zeichen

• Alexander Stepanov und Meng Lee, Die Standardschablone-Bibliothek. HP-Laboratorien Technischer Bericht 95-11 (R.1), am 14. November 1995. (Revidierte Version von A. A. Stepanov und M. Lee: Die Standardschablone-Bibliothek, Technischer Bericht X3J16/94-0095, WG21/N0482, ISO Programmiersprache C ++ Projekt, Mai 1994.)

• Stepanov denkt über das Design des STL nach.
• Atul Saini und David R. Musser, STL Tutorenkurs und Bezugsführer: C + +, mit der Standardschablone-Bibliothek Programmierend. Vorwort von Alexander Stepanov; [Copyright Modena Software Inc.] internationale Standardbuchnummer von Addison-Wesley 0-201-63398-1

Außenverbindungen

• C/C ++ STL Verweisung, schließt C ++ 0x ein zeigt
• STL Programmierer-Führer führt von SGI
• Apache (früher Schelm-Welle) C ++ Standardbibliotheksklassenverweisung
• Apache (früher Schelm-Welle) C ++ Standardbibliotheksbenutzerführer
• Bjarne Stroustrup auf Dem Erscheinen des STL (Seite 5, Abschnitt 3.1)