WikiDer > Standardvorlagenbibliothek

Standard Template Library

Das Standardvorlagenbibliothek oder STL ist ein Softwarebibliothek für die ProgrammierspracheC das ist ein Teil von C-Standardbibliothek. Die Bibliothek definiert viele Standards Vorlagen zur Abwicklung allgemeiner Aufgaben, wie z Behälter, Iteratoren und Algorithmen.

Beschreibung

Der STL besteht aus einem vorgefertigten Set gängiger Veel Klassen, wie Container und assoziative Arrays. Mit dem Vorlagensystem von C können diese Klassen sowohl für integrierte Typen als auch für benutzerdefinierte Typen verwendet werden, solange sie einige grundlegende Operationen (wie Kopieren und Zuweisen) zulassen. Ebenfalls Teil der STL sind eine Reihe von Standardalgorithmen, darunter Sortierung und binäre Suche, die unabhängig von dem Container sind, in dem die Datentypen gespeichert sind.

Da die STL das Vorlagensystem von C verwendet, liefert sie Polymorphismus auf Kompilierungsebene, was in vielen Fällen effizienter ist als herkömmlicher Laufzeitpolymorphismus. Modernes C Compiler Berücksichtigen Sie zusätzliche Abstraktion, wodurch die Kosten für die Verwendung von STL minimiert werden.

Die STL war die erste Softwarebibliothek, die generische Algorithmen und Datenstrukturen verwendet, basierend auf vier Ideen:

  • Generische Programmierung
  • Abstraktion ohne Effizienzverlust
  • Das Von Neumann Architektur
  • Wertesemantik (das bedeutet, dass Werte kopiert werden, anstatt Referenzen zu kopieren)

Geschichte

Die Standardbibliothek von C basiert auf einer Version von STL wie veröffentlicht von Silicon Graphics, Inc. Die standardisierte STL und die Original-STL von Silicon Graphics, Inc. unterscheiden sich jedoch in kleineren Punkten; beide implementieren einige Funktionalitäten, die in der anderen Version nicht vorhanden sind. Außerdem besteht die STL-Version von SGI nur aus einem Satz von Header-Dateien, während der ISO-C-Standard die Implementierung von STL sowohl in Header-Dateien als auch in einer Bibliotheksdatei erlaubt.

Inhalte der Bibliothek

Behälter

Die STL besteht aus sequentiellen Containern und assoziativen Containern. Häufig verwendete sequentielle Container sind Vektor, deque und aufführen. Zu den assoziativen Containern gehören einstellen, Multi-Set, Mappe und Multimap.

ContainerBeschreibung
Sequenzen / Listen - Geordnete Sammlungen
VektorEine dynamische Liste wie a Array in C (d. h. Zustand wahlfreier Zugriff add) mit der zusätzlichen Möglichkeit, die Größe des Arrays automatisch zu ändern. Hinzufügen und Entfernen eines Elements am Ende eines Lieferwagens Vektor hat im Durchschnitt gedauert (amortisiert) konstant Zeitkomplexität. Das Hinzufügen und Entfernen eines Elements am Anfang oder in der Mitte eines Vektors dauert im Durchschnitt linear.
aufführenEine doppelt verkettete Liste. Elemente in einem aufführen werden nicht an aufeinanderfolgenden Orten im Speicher gespeichert, daher ist die Zeitkomplexität der Operationen genau entgegengesetzt zu einem Vektor: Das Abrufen eines Elements ist langsam (lineare Zeitkomplexität), während das Hinzufügen und Entfernen, sobald eine Position gefunden ist, sehr schnell ist (konstante ).
deque (Doppelseitige Warteschlange)Ein Vektor, bei dem das Hinzufügen und Entfernen sowohl am Anfang als auch am Ende der Deque im Durchschnitt in konstanter Zeit erfolgt. Dies geht jedoch auf Kosten gewisser Garantien für die Gültigkeit von Iteratoren beim Hinzufügen und Entfernen von Elementen.
Sammeladapter
WarteschlangeEIN Warteschlange ist ein Warteschlange und liefert a FIFOSchnittstelle mit dem drücken/knallen/vorne/hinten Operationen. Jede Sammlung, die Vorderseite(), zurück(), push_back() und pop_front() Operationen, können verwendet werden, um eine Warteschlange zu erstellen. Dazu gehören die aufführen und der deque.
PrioritätswarteschlangeEIN Prioritätswarteschlange ist eine Warteschlange mit einer Priorität, die jedem Element zugeordnet ist. Elemente mit hoher Priorität befinden sich am Anfang der Warteschlange. Das Prioritätswarteschlange bietet eine Schnittstelle zum drücken/knallen/oben Operationen. Eine Zeile mit wahlfreiem Zugriff, die die Operationen anzeigt Vorderseite(), push_back() und pop_front() unterstützt, kann verwendet werden, um Prioritätswarteschlange erschaffen. Dazu gehören die Vektor und der deque.

Der Elementtyp muss den Vergleichsoperator implementieren, um zu bestimmen, welches Element eine höhere Priorität hat.

StapelBietet eine Schnittstelle für a LIFO Haufen, mit dem drücken/knallen/oben Operationen (das letzte hinzugefügte Element steht oben). Jede Sammlung, die die Operationen zurück(), push_back(), und Pop zurück() Werkzeuge, kann verwendet werden, um Stapel initiieren. Dazu gehören die Vektor, aufführen und deque.
Assoziative Container - Ungeordnete Sammlungen
einstellenEine sortierte Menge (Sammlung). Beim Hinzufügen und Entfernen von Elementen bleiben Iteratoren gültig. Auch Operationen wie Verband, Überschneidung, Unterschied, symmetrische Differenz- und Anwesenheitsprüfung verfügbar. Der in einem Set gespeicherte Datentyp muss der Vergleichsoperator sein < (kleiner-als) oder geben Sie eine alternative Vergleichsfunktion an. Eine Menge wird implementiert mit a implemented selbstausgleichender binärer Suchbaum.
Multi-SetDies entspricht einem Satz, erlaubt jedoch doppelte Elemente.
MappeEin sortiertes assoziatives Array, mit dem Objekte eines Typs zu Objekten eines anderen bestimmten Typs hinzugefügt werden können. Das erste Objekt wird als Schlüssel oder Schlüssel bezeichnet und muss der Vergleichsoperator sein < implementieren. Der zweite Typ heißt Wert oder Wert und hat diese Anforderung nicht. Auch eine Karte wird mit a . implementiert selbstausgleichender binärer Suchbaum.
MultimapEine Multimap ist mit einer Map identisch, erlaubt jedoch doppelte Elemente.
hash_set

hash_multiset
hash_map
hash_multimap

Diese sind äquivalent zu set, multiset, map bzw. multimap, werden aber mit a . implementiert Hash-tabelle. Die Schlüssel werden nicht sortiert, sondern verwenden eine Hash-Funktion, die für den Datentyp verfügbar sein muss. Diese Container sind nicht Teil der C-Standardbibliothek, sondern in einer erweiterten STL-Version von Silicon Graphics erhältlich. Viele Implementierungen der STL enthalten diese Erweiterung, zum Beispiel die GNU C-Bibliothek in der __gnu_cxx Namensraum. Derzeit ist geplant, diese als Teil des C-Standards unter einem anderen Namen (unordered_set, unordered_multiset, unordered_map bzw. unordered_multimap) hinzuzufügen.

Iteratoren

Ein Iterator bietet ungefähr die gleiche Grundfunktionalität wie Zeiger, bietet jedoch eine zusätzliche Generalisierung durch Abstraktion des Containers, in dem die Daten gespeichert sind. Die STL implementiert fünf verschiedene Typen Iteratoren, Eingabe-Iteratoren (diese können nur zum sequentiellen Lesen von Werten verwendet werden), Ausgabe-Iteratoren (diese können nur zum sequentiellen Schreiben von Werten verwendet werden), Vorwärts-Iteratoren (diese können gelesen, geschrieben und nach vorne verschoben werden), bidirektionale Iteratoren (als Vorwärts-Iteratoren, können aber auch rückwärts verschoben werden) und Iteratoren mit wahlfreiem Zugriff (diese können in einem Arbeitsgang mehrere Schritte in jede Richtung frei bewegt werden).

Algorithmen

Ein großer Teil der Algorithmen, die Operationen wie Suchen und Sortieren implementieren, sind Teil der STL. Jeder Algorithmus wird speziell für die verschiedenen Iteratortypen implementiert, sodass der Algorithmus auf jeden Container angewendet werden kann, der einen bestimmten Iteratortyp liefert.

Funktionen

Die AWL enthält Klassen, die den Funktionsoperator (Operator()) Überlast. Diese Klassen werden Funktionen oder aufgerufene Funktionsobjekte. Diese können verwendet werden, um Funktionen einen Zustand zu geben. Als Funktoren können auch normale Zeiger auf Funktionen verwendet werden.

Kritik

Anforderungen an den Compiler

Die Benutzerfreundlichkeit der AWL wird maßgeblich von der Qualität des verwendeten C-Compilers bestimmt:

  • Fehlermeldungen im Zusammenhang mit Vorlagen werden in der Regel sehr lang und sind schwer zu entziffern. Dieses Problem wird als so schwerwiegend angesehen, dass einige Dienstprogramme geschrieben wurden, um STL-bezogene Fehlermeldungen zu vereinfachen und einzurücken. Es gibt auch einen Vorschlag für den C-Standard (genannt Concept-Checking), der versucht, dieses Problem zu reduzieren.
  • Unachtsamer Umgang mit den STL-Vorlagen kann zu Code aufblähen.
  • Das Kompilieren von C mit Vorlagen führt zu einer erhöhten Kompilierungszeit und einem höheren Speicherverbrauch, manchmal sogar um ein Vielfaches höher.

Verweise

Siehe auch

  • ankurbeln: eine große Sammlung von C-Bibliotheken, die portabel und qualitätsgeprüft sind. Einige Boost-Bibliotheken werden in der nächsten Überarbeitung des C-Standards hinzugefügt.

Externe Links