[X] Aufbau der STL - Teil 1: Container

[CStoll]

~Ich fange gerade erst an~

1. Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ANSI C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, daß sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muß lediglich darauf achten, daß die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

• Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
• Iteratoren navigieren in Containern oder anderen Datenstrukturen
• Algorithmen führen verschiedene Operationen auf Container-Elementen aus

2. Container

2.1. sequentielle Container

2.2. assoziative Container

3. Iteratoren

4. Algortihmen

5. weitere Klassen

6. ...

[CStoll]

1. Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ANSI C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, daß sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muß lediglich darauf achten, daß die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

• Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
• Iteratoren navigieren in Containern oder anderen Datenstrukturen
• Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standard-Bibliothek von C++, die nicht direkt der STL zugeordnet werden.

2. Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, so daß sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

• value_type - der Typ der gespeicherten Daten
• iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
• ...

Memberfunktionen

• begin() - liefert einen Iterator auf das erste Element des Containers
• end() - liefert einen Iterator hinter das letzte Element des Containers
• rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw hinter das letzte Element des Containers (rückwärts gerechnet)
• size() - liefert die aktuelle Anzahl an Elementen
• max_size() - liefert das maximale Fassungsvermögen des Containers
• insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
• erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[
• assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
• swap(c2) (als Member) und swap(c1,c2) (global) - vertauscht den Inhalt der Container c1 und c2.
• clear() - löscht alle Elemente des Containers

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet werden).

2.1. sequentielle Container

Sequentielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden.

vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:

• capacity()
  Liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wieviele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
• reserve(size)
  Reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.
• resize(size) und resize(size,val)
  Ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
• vec[pos] und at(pos)
  Liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muß.
• push_back(val)
  Hängt das Element 'val' an das Ende des Vektors an.
• front() und back()
  Liefern den Wert des ersten bzw. letzten Elements im Vektor.
• pop_back()
  Löscht das letzte Element aus dem Vektor.

Die Spezialisierung vector<bool> wurde zur platzsparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

• flip()
  Invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
• vec[pos].flip() bzw. at(pos).flip
  Invertiert das Element 'pos' des Vektors

deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, daß sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. Ind der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, daß sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden diese Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden.

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die selben Methoden wie ein Vektor, zusätzlich ermöglicht sie:

• push_front(val)
  Hängt das Element 'val' an den Anfang der Schlange an
• pop_front()
  Löscht das erste Element der Schlange

list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:
[/cpp]#include <list>[cpp]
Im Gegensatz zu Vektoren wird der Inhalt einer list in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

• resize()
• push_back(), pop_back() und back()
• push_front(), pop_front() und front()
• splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
  Hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
• unique(), sort(), merge(list) und reverse()
  Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

string

voller Name:
[cpp]template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;
[/cpp]
Header:

#include <string>

Achtung: Der Header <string.h> exisitiert ebenfalls, dieser enhält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine "offiziellen" STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

2.2. assoziative Container

Assoziative Container sortieren ihre Elemente intern um. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

• count(val)
  Zählt, wie oft das Element (für Set's) bzw. der Schlüsselwert (für Map's) 'val' im Container enthalten ist
• find(val)
  Liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
• erase(val)
  Löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
• lower_bound(val), upper_bound(val) und equal_range(val)
  Liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
• key_comp() und value_comp()
  Liefern den Functor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden

Jeder assoziative Container besitzt einen "eingebauten" Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden - allerdings sollte das verwendete Prädikat eine Ordnungsrelation über dem Schlüsseltyp definieren, da es sonst zu undefiniertem Verhalten kommen kann.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x== gdw !(x<y)&&!(y<x).

set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Set's und Multiset's speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, daß eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Map's und Multimap's speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, daß eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlichen zugeordneten Werten.

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft.
(die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann)

2.3. Container Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen.

stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren.

queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Conntainertyps, um einen FIFO-Speicher zu realisieren.

priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

include <queue>

Eine Priority-Queue implementiert eine Prioritäts-Warteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, so daß jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.

3. Iteratoren

Was nützen die besten Container, wenn man nicht problemlos auf ihren Inhalt zugreifen kann? Vektoren und Deques bieten freien Zugriff auf ihre Elemente, so daß es möglich ist, sich per Index durch ihre Daten durchzuhangeln. Allerdings ist es nicht möglich, effektiv auf einer Listen- oder Baumstruktur nach einem bestimmten Index zu suchen.

Am einfachsten wäre es, für jeden Containertyp eigene Zugriffsmethoden zu definieren, die die besonderen Fähigkeiten des jeweiligen Typs ausnutzen - allerdings würde dieser Ansatz die Austauschbarkeit der Containerklassen erschweren. Deshalb geht die STL einen anderen Weg. Jeder Container bringt seine eigene Iterator-Klasse mit, die über eine definierte Schnittstelle auf seine Elemente zugreifen kann.

3.1. Iterator-Kategorien

Je nach Fähigkeiten werden die verschiedenen Iteratoren in Kategorien eingeordnet. Bei der Einordnung der STL-Iteratoren in diese Kategorien wurde darauf Wert gelegt, daß die existierenden Operationen auch relativ schnell umgesetzt werden können (deshalb definieren z.B. list-Iteratoren keinen operator+=).

Output Iterator

Dies ist wohl der primitivste Iterator. Er kann lediglich Daten schlucken und inkrementiert werden, um im Speicher weiterzulaufen (wobei das Inkrementieren häufig als leere Operation implementiert ist). Es ist noch nicht einmal möglich, zwei gegebene Output-Iteratoren miteinander zu vergleichen.

In diese Kategorie gehören zum Beispiel die ostream_iterator'en oder die inserter.

Input Iterator

Diese Klasse ist ähnlich einfach aufgebaut. Ein Input Iterator kann Werte aus einem Container lesen, inkrementiert werden und mit anderen Iteratoren verglichen werden.
Der C++ Standard garantiert übrigens nicht, daß Kopien eines Input-Interators unabhängig voneinander genutzt werden können, um den selben Datenvorrat zweimal einzulesen.

Der wichtigste Input Iterator ist der istream_iterator. Im Hinblick auf seine Zugriffsmöglichkeiten auf die unterliegenden Werte könnte man einen Set- oder Multiset-Iterator auch in diese Kategorie einordnen.

Forward Iterator

Ein Forward Iterator vereinigt in sich die Fähigkeiten von Output- und Input-Iterator. Er kann sowohl Daten lesen als auch schreiben. Und im Gegensatz zum Input-Iterator können sich verschiedene Kopien auch unabhängig durch die unterliegende Datenstruktur bewegen.

Die STL verwendet (afaik) keine Forward Iteratoren, aber z.B. in einer einfach verketteten Liste wären sie gut vorstellbar.

Bidirektionaler Iterator

Diese Klasse erweitert den Forward Iterator um die Fähigkeit, "rückwärts" zu laufen. Ein Bidirektionaler Iterator kann sowohl inkrementiert als auch dekrementiert werden.

In diese Kategorie gehören die Iteratoren einer list<> und der assoziativen Container - wobei letztere den Schlüsselwert der iterierten Elemente nicht ändern dürfen.

Random Access Iterator

Random Access Iteratoren sind die mächtigste Kategorie von Iteratoren. Sie können beliebig durch die iterierte Struktur "springen". Zusätzlich zu Operationen, die ein bidirektionaler Iterator unterstützt, bieten sie auch Iterator-Arithmetik nach dem Vorbild der Pointer-Arithmetik von C - sie können um beliebige ganzzahlige Schrittweiten vorwärts und rückwärts durch den Speicher bewegt werden, den Abstand untereinander berechnen und gegeneinander mit <,<=,>= und > verglichen werden.

In diese Kategorie fallen die Iteratoren eines vector<> oder deque<>, aber auch die klassischen Pointer.

3.2. Iterator Adapter

Adapter werden verwendet, um das Verhalten eines Iterators zu ändern.

Insert Iteratoren

Inserter sind reine Output-Iteratoren und übersetzen Schreibzugriffe in insert()-Aufrufe des unterliegenden Containers. Mit ihrer Hilfe kann ein Container während der Arbeit erweitert werden. Auf diese Weise kann z.B. ein Algorithmus Werte in den Container einfügen, ohne sich um den verfügbaren Platz Sorgen machen zu müssen.

Außer einem normalen insert-Iterator gibt es auch noch back_inserter (hängen die ankommenden Daten per push_back() ans Ende ihres Containers an) und front_inserter (hängen die Daten per push_front() an den Anfang des Containers an).

Reverse Iteratoren

Reverse Iteratoren verwenden als Grundlage einen beliebigen Bidirektionalen Iterator und drehen dessen Laufrichtung um (aus ++ wird -- etc.). Auf diese Weise kann man recht schnell "rückwärts" durch eine vorgegebene Sequenz laufen.

Sämtliche Container der STL können über die Methoden rbegin() und rend() geeignete Reverse-Iteratoren auf den Anfang und das Ende der (rückwärts gelesenen) Elementfolge herausgeben.

Stream-Iteratoren

Stream-Iteratoren benötigen einen Eingabe- bzw. Ausgabestream und übersetzen Datenzugriffe in dessen operator>> bzw. operator<<. Auf diese Weise wird es möglich, STL-Algorithmen direkt auf Dateien oder der BEnutzer-Eingabe auszuführen.

Zusätzlich gibt es auch einen streambuf_iterator, der direkt auf einem Stream-Puffer operiert (die Stream-Puffer dienen als "Zwischenlager" zwischen den IO-Streams und ihrer externen Datenrepräsentation).

3.3. Iterator-Hilfsfunktionen

Um die Arbeit mit den Iteratoren etwas zu erleichtern und deren fehlende Fähigkeiten zu kompensieren, existieren einige Hilfsfunktionen:

• advance(it,num)
  Verschiebt den Iterator 'it' um 'num' Positionen nach vorne (bzw. hinten bei negativem Wert). Für Random-Access-Iteratoren wird dafür deren operator+= verwendet, alle anderen Typen werden entsprechend oft inkrementiert oder dekrementiert.
• distance(it1,it2)
  Bestimmt den Abstand zwischen den Iteratoren 'it1' und 'it2'. Für Random-Access-Iteratoren wird deren operator- verwendet, bei allen anderen Typen wird gezählt, wie oft it1 inkrementiert werden muß, um it2 zu erreichen.
• iter_swap(it1,it2)
  Vertauscht die Elemente, auf die 'it1' und 'it2' zeigen, miteinander.

4. Algortihmen

Algorithmen sind das "Arbeitspferd" der STL. Mit ihrer Hilfe kann man fast alles mit einem Container anstellen, was man sich vorstellen kann - und wenn etwas noch nicht in der STL vorgesehen ist, lässt sich die nötige Funktion leicht selber schreiben.

Um flexibler zu sein, werden den Algorithmen keine kompletten Container übergeben, sondern Bereiche. Auf diese Weise kann man auch Ausschnitte eines Containers oder Datensammlungen ohne direkte STL-Unterstützung verarbeiten. Ein Bereich wird definiert durch zwei Iteratoren, von denen der erste auf den Anfang und der zweite direkt hinter das Ende der zu bearbeitenden Daten zeigt - bei einem leerer Bereich fallen Anfang und Ende zusammen. Wenn ein Algorithmus mehrere Bereiche parallel bearbeitet, benötigt er häufig nur vom ersten Bereich beide Endpunkte - die Größe aller weiteren verwendeten Bereiche ergibt sich aus dem Zusammenhang (z.B. erwartet copy(), daß der Zielbereich genauso viel Platz bietet wie der Ursprungsbereich). In diesem Fall ist der Aufrufer der Funktion dafür verantwortlich, daß die weiteren Bereiche genug Elemente enthalten.

Wichtig ist bei der Arbeit mit Algorithmen, daß sie die unterliegende Datenstruktur nicht beeinflussen können. Sie können weder Elemente physich löschen (stattdessen füllen sie Lücken mit nachfolgenden Werten auf und geben einen Iterator auf das "neue" Ende der Sequenz zurück), einfügen (für diesen Zweck können Inserter verwendet werden) noch die Schlüsselwerte eines assoziativen Containers modifizieren (diese sind als const definiert, damit die Ordnung der einzelnen Elemente nicht durcheinandergebracht werden kann).

Hinweis: Von etlichen Algorithmen existieren auch äquivalente Memberfunktion der Container, entweder weil diese Operationen nicht direkt möglich sind (z.B. Modifikationen an Set-Elementen) oder auf der speziellen Containerstruktur effektiver umgesetzt werden können als über die Iteratoren (z.B. Umordnen einer List oder Elementsuche in einem Binärbaum).

Achtung: Wenn ein Algortihmus mit benutzerdefinierten Prädikaten arbeiten, darf er von diesen Kopien anlegen. Deshalb sollten diese ihren internen Status während der Berechnung nicht ändern, da es sonst zu - hmm - merkwürdigen Ergebnissen kommen kann.

Die einzelnen Algorithmen unterteilen sich je nach Wirkung in verschiedene Gruppen:

Nichtmodifizierende Algortihmen

Diese Gruppe verändert die eingegebenen Daten nicht, sondern liest legidlich auf den Daten, um z.B. das größte oder kleinste Element zu bestimmen oder festzustellen, wie oft ein bestimmter Wert in einem Bereich vorkommt.

Die Such-Algorithmen in dieser Gruppe geben jeweils einen Iterator auf die gefundene Position zurück - oder das Ende des Suchbereiches, wenn sie keinen Erfolg hatten.

Modifizierende Algorithmen

Diese Gruppe verändert die Daten im übergebenen Datenbereich, indem sie zum Beispiel Werte kopieren, transformieren oder ersetzen. Dies passiert enweder direkt vor Ort oder während die Daten von einem Bereich in einen anderen kopiert werden.

Lösch-Algorithmen

Eine spzielle Gruppe von modifizierenden Algorithmen entfernt einzelne Werte aus dem übergebenen Datenbereich. Da ein Iterator keinen Speicher freigeben kann (z.B. im Fall eines Pointers in ein C-Array), geschieht das Löschen, indem hintenstehende Elemente umkopiert werden und am Ende des Ursprungsbereiches einige ungültige Werte stehen bleiben - diese müssen vom Besitzer der Daten noch manuell aufgeräumt werden. Dazu wird der Endpunkt des gekürzten Bereiches als Rückgabewert geliefert.

"mutating"-Algorithmen

Diese Gruppe lässt die Werte des übergebenen Bereiches unverändert, ändert aber nach bestimmten Kriterien die Reihenfolge der Elemente. In diese Gruppe gehören auch Sortier-Algorithmen, die einen Bereich ganz oder teilweise sortieren, und Heap-Algorithmen, die eine spezielle Baumstruktur (Heap) in einem linearen Datenbereich erzeugen und verwalten.

In dieser Gruppe existieren auch drei verschiedene Sortier-Algorithmen, unter denen je nach Bedarf der günstigste ausgewählt werden kann:

• sort()
  basiert auf dem QuickSort-Ansatz und ist im Schnitt der schnellste Algorithmus. Bei ungünstigen Eingaben kann das Verfahren jedoch quadratische Laufzeit haben
• partial_sort()
  basiert auf HeapSort und ist durchschnittlich etwas langsamer als sort(), hat jedoch garantierte Laufzeit von O(n*log n). partial_sort() kann auch verwendet werden, um nur einen Teil der Eingabe zu sortieren.
• stable_sort()
  basiert auf MergeSort und benötigt zusätzlichen Zwischenspeicher für die sortierten Elemente, um seine volle Geschwindigkeit zu entfalten. Der größte Vorteil dieses Algorithmus besteht darin, daß identische Elemente ihre ursprüngliche Reihenfolge behalten.
• next_permutation()
  Indem alle möglichen Permutationen einer Zahlenfolge durchlaufen werden, trifft man irgendwann auch die korrekt sortierte Folge - auf diese Weise lässt sich der wohl langsamste bekannte Sortieralgorithmus umsetzen:

template<typename BidIt>
void slow_sort(BidIt st, BidIt en)
{
  while(next_permutation(st,en));
}

Mengen-Algorithmen

Diese Gruppe implementiert wichtige Mengenoperationen wie Vereinigung, Schnittmenge oder Elementsuche auf Wertebereichen. Sie erwarten als Vorbedingung, daß die übergebenen Bereiche sortiert sind (entsprechend dem als Parameter übergebenen Vergleichskriterium 'pred').

numerische Algorithmen

Header:

#include <numeric>

Diese Gruppe wendet verschiedene mathematische Operationen auf Datenbereiche an, entweder um alle Elemente eines Bereiches zusammenzurechnen oder um Teilsummen der Elemente zu ermitteln.

for_each()

template<typename It, typename func>
func for_each(It st, It en,func op);

Der for_each()-Algorithmus ist die "eierlegende Wollmilchsau" der STL. Er wendet die übergebene Operation auf jedes Element des Bereiches [st,en[ an und gibt sie am Ende an den Aufrufer zurück. Indem verschiedenste unäre Funktionen oder Funktoren verwendet werden, kann man nahezu alles mit den Elementen des Ursprungsbereiches anstellen - z.B. den Mittelwert zusammenrechnen, Werte ausgeben oder verarbeiten.

5. weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der STL.

pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Map's und Multimap's genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglicht sie es einer Funktion, zwei Werte gemeinsam zurückzugeben (diese Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen).

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (multi)Map einzufügen.

Funktoren

<functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++ Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++ Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Set's und Map's verwendet wird).

Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit dem selben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.

komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung von komplexen Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden, außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;
class gslice;

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, daß sie parallel auf alle Elemente angewendet werden.

template<typename T>class std::slice_array;
template<typename T>class std::gslice_array;
template<typename T>class std::mask_array;
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Index-Operationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches.

bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitset's bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags platzsparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden.

Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im C++ Standard vorgesehen ist. Auto-Pointer sorgen dafür, daß ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, daß immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz seines Objektes.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr) besser geeignet.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren können, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

6. Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, daß sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++ Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

7. Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Klassen der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden.
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab)

7.1. eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu entwerfen und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise liese sich ein STL-Interface um ein Array oder ein Datenbank-System herum aufbauen.

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, daß sie ein STL-artiges Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

7.2. eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator<>, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename D=ptrdiff_t,typename P=T*,typename R=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidiretional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden. Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien. Die nötigen Operationen müssen allerdings selber bereitgestellt werden.

7.3. eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmen-Entwicklung die Frage, was der Algorithmus eigentlich machen soll.

Um den Algorithmen die Arbeit zu erleichtern, exisitert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen oder die Implementation so zu optimieren, daß sie die "besten" Operationen des Iterator-Typs verwendet.

Außer der allgemeinen Version der iterator_traits gibt es noch Spezialisierungen für Pointer und const-Pointer - und Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen, dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

7.4. eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;
//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

8. weitere Informationen

C++ Referenz
The C++ Standard Library | ISBN: 0201379260

[estartu]

Solange daran noch niemand korrigiert hat, kannst du ruhig editieren, da ist die Historie maximal für dich wichtig.

[CStoll]

estartu schrieb:

Solange daran noch niemand korrigiert hat, kannst du ruhig editieren, da ist die Historie maximal für dich wichtig.

Gut zu wissen - *editiert den Bericht fleißig weiter*

PS: Wieso steht der Artikel immer noch auf "nicht angefangen" in der Artikelübersicht?

[estartu]

Weil ich hin und wieder mal ne Aktualisierung vergesse/übersehe.
Sorry.

Gibt gleich ne aktualisierte Version.
Einfach mal anschubsen, wenn ich was nicht sehe.

[CStoll]

So, der Grobaufbau des Artikels steht - ich bitte um Anmerkungen und Verbesserungsvorschläge der Kollegen.

(Wo sollte ich ausfühtlicher werden? Was könnte ich kürzen? Wo gibt es noch Unklarheiten? ...)

PS @estartu: Ist es eigentlich erlaubt, die Artikel noch nach Veröffentlichung zu ändern?

[estartu]

CStoll schrieb:

PS @estartu: Ist es eigentlich erlaubt, die Artikel noch nach Veröffentlichung zu ändern?

Sagen wir es mal so: Es ist möglich (ihr habt ja Editrechte) aber ich sehe es nicht gerne.

Sehr gravierende Sachen (wie mein Castfehler neulich) dürfen behoben werden.
Sowas wie das PDF nachreichen von Tobias ist auch okay, da der Artikel davon kaum betroffen ist.
Aber es soll nicht darauf hinauslaufen, dass hier halbe Artikel veröffentlicht werden, wo dann hinterher noch die Hälfte geärndert wird.

In solchen Fällen würde ich den Artikel zurückziehen und korrigiert wieder rausschicken oder einen Teil 2 vorschlagen.

Wieso fragst du?

...ich versuche nachher oder Morgen früh mal zu gucken. Was STL angeht bin ich rel. ahnungslos, habs damals nur per Copy&Paste genutzt.

[CStoll]

estartu schrieb:

Wieso fragst du?

Es geht mir im Moment um die Bemerkungen "weitere Informationen folgen später" in einigen Teilen des Artikels (z.B. zu Strings oder IO-Streams) - die würde ich gerne später gegen Links zu anderen (noch nicht existierenden) Artikeln ersetzen, die das Thema ausführlicher behandeln.

[evilissimo]

Hi,

Schön wäre es wenn du zu jedem Container ein paar kleine beispiele für die typische verwendung (minimalistisch sprich auf reserve & solche sachen kannst du natürlich verzichten) hinzufügst.

Als Beispiel für std::vector<>

std::vector<int> vec;
// hinzufügen
vec.push_back(10); 
vec.push_back(21);
vec.push_back(32);
// direkter zugriff
vec[2] = 33;
//iteration
for(std::vector<int>::const_iterator it = vec.begin(), end = vec.end(); 
    it != end; ++it){
   std::cout << *it << std::endl;
}

std::list<>

std::list<int> lst;
lst.push_back(10);
lst.push_front(21);
lst.insert(lst.begin(),32);
for(std::list<int>::const_iterator it = lst.begin(), end = lst.end();
    it != end; ++it){
    std::cout << *it << std::endl;
}

etc

Ich empfinde es als viel zu trocken wenn keine Beispiele dabei sind.

Auch interessant könnte folgendes sein:

http://www.linuxsoftware.co.nz/containerchoice.png

Das soll dem Programmierer helfen den passenden Container zu finden den er sucht und das mit hilfe eines Struktogramms.

Ich weiß, dass das Thema Aufbau der STL ist, aber ehrlich gesagt ist mir der Aufbau eigentlich relativ schnuppe mich würde eher die Verwendung als Otto-Normal-Leser interessieren und Newbies werden es dir danken

BR
evilissimo

[Artchi]

Erstmal klasse das du dir soviel Mühe gemacht hast!

Hätte da aber ein Verbesserungsvrschlag: willst du diesen Artikel nicht lieber aufteilen? Ich pers. (und wahrscheinlich auch die Mehrheit der Leser) fühle mich bei solchen Textmengen in einem Magazin erschlagen. Es ist ja kein Buch, wo ich weiß, das ich viel Text bekomme. Das ganze ist jetzt wirklich nur psychologisch gemeint, nicht das ich deinen Artikel an sich kritisiere. Das ganze ist ja ein Magazin, und da erwartet man als Leser kompakte Informationen, die man sich ruck zuck neben bei mal durchlesen kann. Auch wenn es nicht vollständig ist.

Einige Artikel ufern nämlich aus, als ob es bald Lehrbücher werden.

Ich pers. lese Zeitschriften gerne, weil ich mal in 5 Minuten erfahre worum es geht. Die STL z.B. kann man in einem Zeitungsartikel nicht wirklich erklären. Aber man kann 1. den Leser informieren das es das überhaupt gibt, 2. worum es geht und 3. erste Erfahrungen mitgeben. Wenns weiter gehen soll, kann man das in weiteren Artikeln fortführen. Ich denke die Artikel zu Spirit, GDI+ und vorallem Build-Tools sind gute Beispiele. Die sind kurz, man weiß das es diese Sachen gibt und man findet einen Einstieg. Alles weitere muß man sich in einem Buch erlesen oder man wartet auf weitere Artikel.

Vielleicht kannst du das ganze ja aufteilen und mit Fazits abschliessen? Z.B. könnte man bei den Strings oder Assoziativen Containern einen Cut machen und dann in der nächsten Ausgabe weiter machen?

Das ganze ist jetzt auch eine Frage an alle anderen Autoren? Sollte man da nicht (neben der Layout-Frage) nicht auch solche Fragen festlegen?

[CStoll]

@evil: Ja, das mit den Beispielen klingt ganz gut - aber irgendwie fällt mir auf Anhieb nichts besseres ein als "erzeuge einen Vektor, fülle ihn mit Werten und schau dir das Ergebnis an". Meinst du, sowas reicht zur Motivation?

@Artchi: Erstmal danke für das Kompliment.

Hätte da aber ein Verbesserungsvrschlag: willst du diesen Artikel nicht lieber aufteilen?

Da habe ich auch schon drüber nachgedacht. Aber ich bin mir nicht sicher, wo ich da einen vernünftigen Cut reinbringen könnte.

[evilissimo]

CStoll schrieb:

@evil: Ja, das mit den Beispielen klingt ganz gut - aber irgendwie fällt mir auf Anhieb nichts besseres ein als "erzeuge einen Vektor, fülle ihn mit Werten und schau dir das Ergebnis an". Meinst du, sowas reicht zur Motivation?

Was machst du denn sonst mit einem Vector?
Das sollte doch ausreichen. Eventuell erklärst du das noch mit den Template Parametern (sprich welche wichtig für die Verwendung sind) für die, die selbst noch nichts mit templates gemacht haben.

BR
evilissimo

[CStoll]

evilissimo schrieb:

CStoll schrieb:

@evil: Ja, das mit den Beispielen klingt ganz gut - aber irgendwie fällt mir auf Anhieb nichts besseres ein als "erzeuge einen Vektor, fülle ihn mit Werten und schau dir das Ergebnis an". Meinst du, sowas reicht zur Motivation?

Was machst du denn sonst mit einem Vector?

Stimmt auch wieder.

Eventuell erklärst du das noch mit den Template Parametern (sprich welche wichtig für die Verwendung sind) für die, die selbst noch nichts mit templates gemacht haben.

Kurzfassung: Alle Parameter sind wichtig (außer eventuell dem Allocator, da leistet der Default recht gute Dienste).

@Aufteilung: Das ist noch nicht zu Ende gedacht, aber wäre die folgende Splittung des Artikels brauchbar?

1. Containerklassen (jetzt Kapitel 1/2)
2. Iteratoren und Algorithmen (Kapitel 3/4)
3. Hilfsklassen (Kapitel 5ff)
4. IO-Streams
5. Strings

[evilissimo]

Naja die IOStreams gehören nicht zur STL, wenn dann müsstest du den Titel in "Aufbau der C++ Standard Bibliothek" umbennen.

Ansonsten gibt es auch andere Default Parameter in der STL, z.b. bei map und set den Typ für Key Compare (std::less<>/std::greater<>) die aber natürlich auch interessant und imho wichtig sind.

Bei std::string wäre es interessant wenn du auf std::basic_string<> zu sprechen kommen würdest (z.B. das man sich halt auch eigene strings relativ einfach basteln kann in dem man die chartraits modifiziert)

Was siehst du als Hilfsklassen an? exceptions, functoren, etc?

BR
evilissimo

[CStoll]

evilissimo schrieb:

Naja die IOStreams gehören nicht zur STL, wenn dann müsstest du den Titel in "Aufbau der C++ Standard Bibliothek" umbennen.

Stimmt auch wieder - die IO-Bibliothek wird trotzdem eins der nächsten Themen, die ich bearbeiten will (außer darum kümmert sich schon jemand anderes).

Ansonsten gibt es auch andere Default Parameter in der STL, z.b. bei map und set den Typ für Key Compare (std::less<>/std::greater<>) die aber natürlich auch interessant und imho wichtig sind.

Stimmt - momentan wird der Punkt wohl etwas kurz behandelt.

Bei std::string wäre es interessant wenn du auf std::basic_string<> zu sprechen kommen würdest (z.B. das man sich halt auch eigene strings relativ einfach basteln kann in dem man die chartraits modifiziert)

Strings bekommen ebenfalls einen eigenen Artikel (die gehören genausowenig direkt zur STL wie die Streams).

Was siehst du als Hilfsklassen an? exceptions, functoren, etc?

pair, complex, bitsets etc. (siehe oben - Kapitel 5) - Exceptions könnte ich auch nochmal näher beleuchten, oder reicht da ein Link auf Reyx' Artikel?

[evilissimo]

Also bezgl der exceptions würde ich nicht sagen das da ein Link reicht, er kommt ja selbst nicht auf std::exception und seine Kinder zusprechen, und davon gibt es ne ganze Menge. Interessant ist es halt das es sie gibt, und meiner meinung nach eigene exceptions davon ableiten sollte

So und sonst wird das schon eine sehr runde sache sein wenn du all das behandelt hast. (Btw ist mir ein paar Tage bevor der Vorschlag aufgekommen ist der Gedanke gekommen so etwas zu schreiben. Aber da mir die Zeit ja schon für meinen eigenen Artikel fehlt, bzw ich wenn ich mal Zeit hab mich mit anderen sachen auch noch beschäftige, hab ich den gedanken erst mal in den Hintergrund rücken lassen. Ich kenne halt keine anfänger gerechte einführung in die STL und das wäre halt mal was )

BR
evilissimo

[Artchi]

online gibts vielleicht keine anfängererechte Einführung. Aber das Buch von Kuhlins und Schrader aus dem Springer Verlag ist es meiner Meinung sehr wohl.

Die STL gibt es offiziell doch eigentlich garnihct im ISO-Standard?! Ist doch alles C++ Standardlib. Die STL unterscheidet sich sogar an einigen Stellen von der C++ Standardlib. STL wird nur im Volksmund als Begriff genannt...

Meiner Meinung nach hast du dir hier gerade eine Lebensaufgabe aufgebürgt, die ganze C++ Standardlib zu behandeln, wenn andere dafür ganze Bücher schreiben. Ich hätte mir das nicht vorgenommen. Bin gespannt drauf!

[CStoll]

Artchi schrieb:

online gibts vielleicht keine anfängererechte Einführung. Aber das Buch von Kuhlins und Schrader aus dem Springer Verlag ist es meiner Meinung sehr wohl.

Das Buch habe ich leider nicht verfügbar - ich bin aber bislang recht gut mit dem Jossutis ausgekommen

Meiner Meinung nach hast du dir hier gerade eine Lebensaufgabe aufgebürgt, die ganze C++ Standardlib zu behandeln, wenn andere dafür ganze Bücher schreiben. Ich hätte mir das nicht vorgenommen. Bin gespannt drauf!

Ob ich da letztendlich die ganze Standardlib erkläre, belibt abzuwarten. Auf jeden Fall - drück mir die Daumen

[evilissimo]

Artchi schrieb:

Die STL gibt es offiziell doch eigentlich garnihct im ISO-Standard?! Ist doch alles C++ Standardlib. Die STL unterscheidet sich sogar an einigen Stellen von der C++ Standardlib. STL wird nur im Volksmund als Begriff genannt...

Man nennt sie halt so, und das tun wir nun mal auch :P. Aber ja das ist richtig, wenn man es genau nimmt ist es das einfach nur die C++ Standard Bibliothek

BR

[CStoll]

~So, jetzt wird der Artikel zur besseren Übersicht in drei Teile zerlegt~

Inhalt

Teil 1:

1. Vorbemerkungen
2. Container
3. sequentielle Container
4. assoziative Container
5. Container-Adapter
6. Zusammenfassung

Teil 2:

1. Iteratoren
2. Iterator-Kategorien
3. Iterator-Adapter
4. Iterator-Hilfsfunktionen
5. Algorithmen

Teil 3:

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1. Vorbemerkungen

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ISO C++, der leider häufig unterschätzt oder falsch eingesetzt wird. [...]

Wie der Name schon andeutet, sind die einzelnen Komponenten der STL als Templates aufgebaut. Das hat den Vorteil, daß sie mit beliebigen Datentypen und Erweiterungen zusammenarbeiten können, ohne auf Vererbungshierarchien Rücksicht nehmen zu müssen. Der Anwender der STL muß lediglich darauf achten, daß die benötigten Operationen von seinen Typen unterstützt werden (z.B. benötigt der Schlüsseltyp einer set<> einen <-Operator oder eine äquivalente Vergleichfunktion).

Die STL kann grob in drei Hauptbestandteile untergliedert werden:

• Container dienen zur Aufbewahrung und Verwaltung großer Datensammlungen
• Iteratoren navigieren in Containern oder anderen Datenstrukturen
• Algorithmen führen verschiedene Operationen auf Container-Elementen aus

Außerdem gibt es einige weitere Funktionen und Klassen in der Standard-Bibliothek von C++, die nicht direkt der STL zugeordnet werden.

2. Container

Container werden verwendet, um viele gleichartige Objekte gemeinsam unterzubringen und zu verwalten. Alle Containerklassen der STL haben einige gemeinsame Definitionen und Methoden, so daß sie teilweise gegeneinander ausgetauscht werden können. Die wichtigsten davon sind:

Typdefinitionen:

• value_type - der Typ der gespeicherten Daten
• iterator und const_iterator - der hauseigene Iteratortyp des Containers (für variable bzw. konstante Container)
• size_type - ein Typ zur Angabe von Größenwerten (vorzeichenloser Integer)
• allocator_type - der Typ der verwendeten Allokator-Klasse

Memberfunktionen

• begin() - liefert einen Iterator auf das erste Element des Containers
• end() - liefert einen Iterator hinter das letzte Element des Containers
• rbegin() und rend() - liefern Reverse-Iteratoren auf das erste bzw hinter das letzte Element des Containers (rückwärts gerechnet)
• size() - liefert die aktuelle Anzahl an Elementen
• max_size() - liefert das maximale Fassungsvermögen des Containers
• insert(pos,wert) - fügt ein Element an der Stelle 'pos' ein (bei assoziativen Containern ist 'pos' nur ein Hinweis, wo das Element eingefügt werden könnte)
• assign(st,en) - weist dem Container den Inhalt des Bereiches [st,en[ zu.
• c1.swap(c2) und swap(c1,c2) - vertauscht den Inhalt der Container c1 und c2.
• clear() - löscht alle Elemente des Containers
• erase(pos) und erase(st,en) - löscht das Element an der Stelle 'pos' bzw. alle Elemente im Bereich [st,en[

Zu den Template-Parametern, die ein Container bekommt, gehört neben dem Wertetyp auch immer ein Allokator-Typ. Dessen Methoden werden verwendet, wenn der Container neuen Speicher anfordern, initialisieren und freigeben will. Der Defaulttyp hierfür ist std::allocator<T> und verwendet die Operatoren new und delete, um den Speicher zu verwalten. Experten können die Speicherverwaltung jedoch auch anders implementieren, indem sie eine eigene Allokator-Klasse schreiben und dem Container mitgeben (z.B. kann eine Datenbank oder ein Garbage Collector verwendet oder zurückgegebene Speicherbereiche für schnelleren Zugriff zwischengelagert werden).

3. sequentielle Container

Sequentielle Container speichern ihre Elemente in der Reihenfolge, in der sie eingefügt wurden. Natürlich ist es auch möglich, diese Reihenfolge manuell anzupassen, indem man ein Element in der Mitte des Containers einfügt oder die vorhandenen Elemente direkt ändert.

3.1. vector

voller Name:

template<typename T,typename A=allocator<T> >
class std::vector;

Header:

include <vector>

Ein Vektor verwendet einen zusammenhängenden Speicherbereich, in dem er seine Elemente unterbringen kann. Dadurch kann er sehr schnell über den Index auf ein Element zugreifen und neue Elemente am Ende der Sequenz anhängen und löschen. Einfüge- und Lösch-Operationen in der Mitte oder gar am Anfang des Containers benötigen jedoch deutlich mehr Zeit, weil alle nachfolgenden Elemente entsprechend verschoben werden müssen.

Ein Beispiel zum Umgang mit Vektoren:

#include <vector>
#include <iostream>//für Ausgaben
using namespace std;

int main()
{
  vector<int> data;
  data.push_back(1);
  data.push_back(2);
  data.push_back(3);

  //Ausgabe aller Elemente:
  for(int i=0;i<data.size();++i)
    cout<<data<<" ";
  cout<<endl;

  data[1]=20;//direkter Elementzugriff
  data.front()=11;
  data.pop_back();

  data.resize(10,4);

  //nochmal Ausgabe:
  for(int i=0;i<data.size();++i)
    cout<<data[i]<<" ";

  return 0;
}

Ein Vektor reserviert sich in der Regel mehr Speicherplatz als für seine aktuelle Größe notwendig ist. Solange diese Kapazität noch nicht erreicht wird, können push_back()-Operationen in konstanter Zeit durchgeführt werden. Bei Überschreitung der Kapazität werden alle vorhandenen Elemente in einen neuen (entsprechend größeren) Speicherbereich umkopiert - dadurch werden erstens alle Referenzen, Zeiger und Iteratoren in den Vektor und zweitens kostet diese Operation recht viel Zeit. Deshalb ist es günstig, vor aufwendigen Operationen mit dem Vektor per reserve() genug Speicher anzufordern.

Achtung: Ein Vektor gibt die einmal reservierte Kapazität erst im Destruktor wieder frei.

Zusätzlich zu den generellen Methoden, seinen Inhalt zu manipulieren, bietet ein Vektor noch einige spezielle Zugriffsfunktionen:
*

** resize(size) und resize(size,val)
Ändert die Größe des Vektors auf 'size', indem am Ende Elemente entfernt oder angefügt werden. Neue Elemente werden mit dem Defaultwert des Elementtyps bzw. mit 'val' belegt.
** [i]vec**[pos]** und at(pos)
Liefern das Element mit dem Index 'pos' zurück. Der Unterschied zwischen beiden Methoden besteht in der Fehlerbehandlung - der Index-Operator liefert undefinierte Werte, wenn er mit einem Index außerhalb des Intervalls [0,vec.size()[ aufgerufen wird, die Methode at() wirft eine out_of_range Ausnahme, die vom Anwender aufgefangen werden muß.

• push_back(val)
  Hängt das Element 'val' an das Ende des Vektors an.
• front() und back()
  Liefern den Wert des ersten bzw. letzten Elements im Vektor.
• pop_back()
  Löscht das letzte Element aus dem Vektor.
• capacity()
  Liefert die aktuelle Kapazität des Vektors zurück. Dieser Wert gibt an, wieviele Elemente er aufnehmen könnte, ohne neuen Speicher anfordern zu müssen.
• reserve(size)
  Reserviert genug Speicherplatz für mindestens 'size' Elemente. Der neu angelegte Speicherplatz wird nicht initialisiert.

Die Spezialisierung vector<bool> wurde zur platzsparenden Speicherung von 1-Bit-Werten vorgesehen und bietet ein paar Zusatzmethoden zur Manipulation einzelner Bits:

• flip()
  Invertiert alle Elemente des Vektors (aus true wird false und umgekehrt)
• vec[pos].flip() bzw. at(pos).flip
  Invertiert das Element 'pos' des Vektors

3.2. deque

voller Name:

template<typename T,typename A=allocator<T> >
class std::deque;

Header:

#include <deque>

Eine Deque (Double Ended QUEue) hat insofern Ähnlichkeit mit dem Vektor, daß sie ihren Inhalt auch in zusammenhängendem Speicher organisiert. Ind der Regel wird jedoch nicht ein einzelner Speicherblock dafür verwendet, sondern mehrere kleinere Blöcke, die beim Durchlaufen der Deque virtuell zusammengefügt werden. Ihr Vorteil ist, daß sie sowohl am Ende als auch am Anfang problemlos erweitert werden kann. Änderungen in der Mitte des Containers sind wie beim vector langsam und sollten besser vermieden werden.

Wenn eine Deque ihre reservierte Kapazität ausgeschöpft hat, reserviert sie einen neuen Speicherbereich, der vor bzw. hinter den vorhandenen Speicherblöcken in die Kontrollstruktur eingefügt wird. Im Gegensatz zum Vektor werden die einzelnen Speicherblöcke auch wieder freigegeben, wenn sie nicht mehr benötigt werden (wann das geschieht, ist normalerweise von der Implementation abhängig).

Eine Deque bietet - mit Ausnahme von capacity() und reserve() - die selben Methoden wie ein Vektor, zusätzlich ermöglicht sie:

• push_front(val)
  Hängt das Element 'val' an den Anfang der Schlange an
• pop_front()
  Löscht das erste Element der Schlange

3.3. list

voller Name:

template<typename T,typename A=allocator<T> >
class std::list;

Header:

#include <list>

Im Gegensatz zu Vektoren wird der Inhalt einer list in Form einer doppelt verketteten Liste gespeichert. Auf diese Weise ist es sehr effizient, Werte an beliebiger Stelle einzufügen und wieder zu entfernen. Im Gegenzug ist es sehr langwierig, ein bestimmtes Element anhand seines Index wiederzufinden.

Eine List bietet keinen direkten Elementzugriff über den Index-Operator bzw. at(), aber unterstützt die meisten anderen Funktionen, die auch von Vektoren und Deques zur Verfügung gestellt werden:

• resize()
• push_back(), pop_back() und back()
• push_front(), pop_front() und front()
• splice(pos,list), splice(pos,list,spos) bzw. splice(pos,list,sbeg,send)
  Hängt einzelne Elemente aus 'list' aus und fügt sie vor dem Iterator 'pos' in die Liste ein. Je nach Version wird die komplette Liste 'list', das einzelne Element 'spos' bzw. der Bereich [sbeg,send[ umgehängt.
• unique(), sort(), merge(list) und reverse()
  Diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch auf der Listenstruktur effizienter umgesetzt werden als mit den Iterator-basierten Algorithmen (z.B. braucht reverse() nur alle Vorgänger- und Nachfolger-Zeiger zu vertauschen anstatt Elemente umzukopieren).

Ein Beispiel zur Anwendung einer Liste:

#include <list>
#include <iostream>
using namespace std;

int main()
{
  list<int> data;
  //Liste füllen
  for(int i=1;i<5;++i) data.push_back(i);
  data.push_front(4711);

  //Ausgabe (nicht über Index möglich, deshalb benötigt man Listen-Iteratoren)
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;

  list<int>::iterator pos1=data.begin();
  ++pos1;//Iterator auf 2. Element
  data.insert(pos1,0x0815);

  //nochmal Ausgabe:
  for(list<int>::iterator pos=data.begin();pos!=data.end();++pos)
    cout<<*pos<<" ";
  cout<<endl;
}

3.4. string

voller Name:

template<typename C,typename Tr=char_traits<T>,typename A=allocator<C> >
class std::basic_string;

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

Header:

#include <string>

Achtung: Der Header <string.h> exisitiert ebenfalls, dieser enhält jedoch die char*-Verarbeitungsfunktionen der C-Standardbibliothek.

Strings sind zwar keine "offiziellen" STL-Container, aber sie bieten genug Unterstützung an, um analog zu den anderen Containern verwendet zu werden. Ihre Hauptverwendung ist die Verwaltung von Zeichenketten, deshalb bieten sie auch Operationen zur Verkettung und zur Zusammenarbeit mit char*-Feldern an.

Mit Strings werde ich mich ausführlicher in einem späteren Artikel beschäftigen.

4. assoziative Container

Assoziative Container sortieren ihre Elemente intern nach ihrer Größe. Dadurch geht es deutlich schneller, einen bestimmten Wert im Container wiederzufinden, allerdings spielt es für die Reihenfolge in der Regel keine Rolle, welches Element zuerst eingefügt wurde.

Im Allgemeinen nutzen alle assoziativen Container die gleiche Grundstruktur (ein balancierter Binärbaum), um ihren Inhalt zu speichern, sie unterscheiden sich lediglich im Typ der eingetragenen Elemente und der Art, wie Duplikate verwaltet werden.

Alle assoziativen Container bieten einige zusätzliche Methoden, um bestimmte Elemente suchen zu können (diese Methoden entsprechen den gleichnamigen Algorithmen, können jedoch in der Baumstruktur effizienter arbeiten als auf einem linear angeordneten Iterator-Bereich):

• count(val)
  Zählt, wie oft das Element (für Set's) bzw. der Schlüsselwert (für Map's) 'val' im Container enthalten ist
• find(val)
  Liefert einen Iterator auf ein Containerelement mit dem (Schlüssel-)Wert 'val' oder end(), wenn es nicht existiert
• erase(val)
  Löscht alle Elemente mit dem (Schlüssel-)Wert 'val' aus dem Container
• lower_bound(val), upper_bound(val) und equal_range(val)
  Liefern die erste, letzte bzw. beide Position im Container (als pair), an der der (Schlüssel-)Wert 'val' in den Container eingefügt werden kann
• key_comp() und value_comp()
  Liefern den Functor, mit dem die Schlüsselwerte bzw. Elemente des Containers sortiert werden (bei Set's sind beide identisch, bei Map's vergleicht value_comp() die ersten Elemente eines pair mit Hilfe von key_comp())

Jeder assoziative Container besitzt einen "eingebauten" Vergleichstyp, mit dessen Hilfe die einzelnen Elemente verglichen werden. Dieser wird bei der Definition des Containers als zweiter bzw. dritter Template-Parameter übergeben. Der vorgegebene Typ "less<T>" verwendet < als Vergleichskriterium, sortiert die Elemente also aufsteigend. Aber jeder Funktortyp, der zwei Schlüsselwerte als Parameter akzeptiert und einen bool zurückliefert, kann theoretisch als Vergleichskriterium eingesetzt werden.

Die Vergleichsrelation des Containers wird auch verwendet, um zwei Elemente auf Gleichheit zu testen: x==y gdw !(x<y)&&!(y<x).

Wichtig für die Anwendung von set's und map's ist, daß der verwendete Vergleichstyp eine "strict weak ordering" ~wie kann man das auf Deutsch ausdrücken?~ bildet, andernfalls kommt es zur Laufzeit des Programmes zu undefiniertem Verhalten - und kein Compiler kann kontrollieren, ob eine beliebig gegebene Relation diese Anforderungen erfüllt.

4.1. set und multiset

voller Name:

template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::set;
template<typename K,typename P=less<K>,typename A=allocator<K> >
class std::multiset;

Header:

#include <set>

Set's und Multiset's speichern einzelne Schlüsselwerte. Ihr Unterschied besteht darin, daß eine Set jeden Wert maximal einmal enthält, während eine Multiset auch Duplikate enthalten kann.

map und multimap

voller Name:

template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::map;
template<typename K,typename V,typename P=less<K>,typename A=allocator<pair<const K,V> > >
class std::multimap;

Map's und Multimap's speichern Paare aus einem Schlüssel und einem zugeordneten Wert. Auch hier besteht der Unterschied darin, daß eine Map eindeutige Schlüssel enthält, während die Schlüssel in der Multimap mehrfach vorkommen können - sogar mit unterschiedlichen zugeordneten Werten. Die Elemente in einer (Multi-)Map sind Paare aus konstantem Schlüssel und Wert, wodurch die insert-Operationen etwas komplizierter geschrieben werden müssen:

map<string,int> id_liste;

//(1) - exakter Typ:
id_liste.insert(map<string,int>::value_type("Carsten",4711);

//(2) - pair:
id_liste.insert(pair<string,int>("CStoll",0x0815);

//(3) - make_pair:
id_liste.insert(make_pair("Admin",1);

(im ersten Fall wird der Typ exakt so übergeben, wie die map ihn benötigt, im zweiten und dritten Fall ist eine implizite Typumwandlung von pair<string,int> bzw. pair<const char*,int> nach pair<const string,int> notwendig)

Eine Map bietet als besonderes Extra direkten Elementzugriff über den Index-Operator m[ind]. Im Gegensatz zu einem Array oder Vektor wird hierbei der Wert zurückgegeben, der zum Schlüssel 'ind' zugeordnet wurde. Wenn dieser Schlüssel nicht in der Map existiert, wird er angelegt und mit einem Defaultwert verknüpft.
(die Multimap bietet dieses Feature nicht, da sie keine eindeutige Zuordnung zwischen einem Schlüssel und seinem Wert herstellen kann)

5. Container Adapter

Diese Adapter verwenden die Standard-Container, um darauf spezielle Datenstrukturen aufzubauen. Sie bieten ein halbwegs einheitliches Interface zur Verwendung an, unterscheiden sich jedoch in der Definition, welches Element das "erste" ist.

• push(val)
  fügt das Element "val" in den unterliegenden Container ein
• top()
  liefert das "erste" Element des Containers
• pop()
  löscht das "erste" Element des Containers (der Wert muß vorher verarbeitet werden)

Diese Methoden verwenden keinerlei Fehlerkontrolle - wenn versucht wird, das erste Element eines leeren Stacks zu lesen, ergibt sich deshalb undefiniertes Verhalten.

Alle Adapter erwarten, daß der verwendete Containertyp die Operationen bereitstellt, die sie verwenden wollen, andernfalls weigert sich der Compiler, sie zu erzeugen.

5.1. stack

voller Name:

template<typename T,typename C=deque<T> >
class std::stack;

Header:

#include <stack>

Ein Stack nutzt die Memberfunktionen push_back(), back() und pop_back() des unterliegenden Containertyps, um einen LIFO-Speicher zu realisieren - die Elemente werden in der umgekehrten Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für den Stack kann theoretisch jeder sequentielle Container eingesetzt werden - der Standardtyp ist die deque, weil sie im Gegensatz zum Vektor auch wieder Speicher freigeben kann.

5.2. queue

voller Name:

template<typename T,typename C=deque<T> >
class std::queue;

Header:

#include <queue>

Eine Queue (oder Warteschlange) nutzt die Memberfunktionen push_back(), front(), und pop_front() des unterliegenden Conntainertyps, um einen FIFO-Speicher zu realisieren - die Elemente werden in der selben Reihenfolge herausgegeben, in der sie eingefügt wurden.

Als Grundlage für die Warteschlange können entweder deque's oder Listen verwendet werden, da sie als einzige Standard-Container eine pop_front()-Methode definieren.

5.3. priority_queue

voller Name:

template<typename T,typename C=vector<T>,typename P=less<typename C::value_type> >
class std::priority_queue;

Header:

#include <queue>

Eine Priority-Queue implementiert eine Prioritäts-Warteschlange auf dem unterliegenden Containertyp - die Elemente werden entsprechend ihrer Größe umgeordnet, so daß jeweils das größte aus der Warteschlange entnommen werden kann. Der Adapter nutzt die Methoden push_back(), front() und pop_back() sowie die Heap-Algorithmen make_heap(), push_heap() und pop_heap(), um seine Elemente zu organisieren.
Das Prädikat P dient dabei zur Feststellung, welches Element größer ist. Genau wie bei den assoziativen Containern muß die verwendete Vergleichsfunktion eine Ordnungsrelation definieren, sonst funktioniert die Priority-Queue nicht richtig.

Als Grundlage für eine Prioritäts-Schlange können Vektoren, Deque's oder Strings verwendet werden - Listen bieten keine Random-Access-Iteratoren und können deshalb nicht mit den Heap-Algorithmen genutzt werden.

6. Zusammenfassung

Es gibt keine "perfekte" Containerklasse für alle Anwendungsbereiche. Deshalb ist es von Vorteil, wenn man die unterschiedlichen Container der STL kennt und auswählen kann, welcher gerade am günstigsten geeignet ist. Dabei ist es auch mit geringem Aufwand möglich, die Container gegeneinander auszutauschen, wenn man zum Beispiel während der Entwicklung feststellt, daß eine deque<> doch bessere Eigenschaften hat als eine list<>.

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Ausblick

Container sind ein hilfreiches Werkzeug zur Datenorganisation. Aber ihre volle Stärke entwickeln sie erst in Zusammenarbeit mit den Iteratoren und Algortihmen - deshalb werde ich diese Bestandteile der STL im zweiten Teil der Serie ausführlicher behandeln.

[Artchi]

Die Standard Template Library (STL) ist ein wesentlicher Bestandteil von ANSI C++

ISO C++. ANSI C++ ist nur die nationale Version, genauso wie es DIN C++ gibt.