Inhaltsverzeichnis zum Buch Komponenten entwerfen mit der C++ STL
Copyright Addison Wesley Longman 1999

Vorwort zur 2. Auflage xiii 
Vorwort xv 
Teil I Einführung 1 
1 Konzept der C++ Standard Template Library (STL) 3 
1.1 Generizität der Komponenten 4 
1.2 Abstrakte und implizite Datentypen 4 
1.3 Das grundlegende Konzept 5 
1.3.1 Container 5 
1.3.2 Iteratoren 6 
1.3.3 Algorithmen 6 
1.3.4 Zusammenwirken 6 
1.4 Interne Funktionsweise 10 
1.5 Komplexität 15 
1.5.1 O-Notation 17 
1.5.2 Omega-Notation 20 
1.6 Hilfsklassen und -funktionen 21 
1.6.1 Paare 21 
1.6.2 Vergleichsoperatoren 22 
1.6.3 Funktionsobjekte 23 
1.6.4 Funktionsadapter 27 
1.7 Namens- und andere Konventionen 30 
1.7.1 Schreibweisen 30 
1.7.2 Header-Dateien 31 
1.7.3 Namespace für die Beispiele 32 
2 Iteratoren 33 
2.1 Iteratoreigenschaften 34 
2.1.1 Zustände 34 
2.1.2 Standard-Iterator und Traits-Klassen 35 
2.1.3 Distanzen 36 
2.1.4 Kategorien 37 
2.1.5 Reverse-Iteratoren 40 
2.1.6 Markierungsklassen 41 
2.2 Stream-Iterator 42 
2.2.1 Istream-Iterator 42 
2.2.2 Ostream-Iterator 45 
3 Container 51 
3.1 Datentyp-Schnittstelle 51 
3.2 Container-Methoden 52 
3.2.1 Reversible Container 54 
3.3 Sequenzen 54 
3.3.1 Vektor 56 
3.3.2 Liste 59 
3.3.3 Deque 64 
3.3.4 showSequence 64 
3.4 Iteratorkategorien und Container 65 
3.4.1 Auswahl eines Algorithmus abhängig vom Iteratortyp 67 
3.4.2 Ableitung von Wert- und Distanztypen 69 
3.4.3 Erben von Iteratoreigenschaften 72 
3.5 Iteratoren zum Einfügen in Container 72 
4 Abstrakte Datentypen 79 
4.1 Stack 79 
4.2 Queue 80 
4.3 Priority-Queue 82 
4.4 Sortierte assoziative Container 84 
4.4.1 Set 85 
4.4.2 Multiset 90 
4.4.3 Map 90 
4.4.4 Multimap 94 
Teil II Algorithmen 95 
5 Standard-Algorithmen 97 
5.1 Kopierende Algorithmen 97 
5.2 Algorithmen mit Prädikat 98 
5.2.1 Algorithmen mit binärem Prädikat 99 
5.3 Nicht-verändernde Sequenzoperationen 100 
5.3.1 for_each 100 
5.3.2 find und find_if 101 
5.3.3 find_end 103 
5.3.4 find_first_of 104 
5.3.5 adjacent_find 104 
5.3.6 count 107 
5.3.7 mismatch 108 
5.3.8 equal 110 
5.3.9 search 111 
5.3.10 search_n 113 
5.4 Verändernde Sequenzoperationen 114 
5.4.1 iota 114 
5.4.2 copy und copy_backward 115 
5.4.3 copy_if 117 
5.4.4 swap, iter_swap und swap_ranges 119 
5.4.5 transform 121 
5.4.6 replace und Varianten 123 
5.4.7 fill und fill_n 125 
5.4.8 generate und generate_n 126 
5.4.9 remove und Varianten 128 
5.4.10 unique 130 
5.4.11 reverse 131 
5.4.12 rotate 132 
5.4.13 random_shuffle 134 
5.4.14 partition 136 
5.5 Sortieren, Verschmelzen und Verwandtes 137 
5.5.1 sort 137 
5.5.2 nth_element 141 
5.5.3 Binäre Suche 143 
5.5.4 Verschmelzen (Mischen) 146 
5.6 Mengenoperationen auf sortierten Strukturen 151 
5.6.1 includes 151 
5.6.2 set_union 152 
5.6.3 set_intersection 153 
5.6.4 set_difference 154 
5.6.5 set_symmetric_difference 155 
5.6.6 Voraussetzungen und Einschränkungen 156 
5.7 Heap-Algorithmen 158 
5.7.1 pop_heap 160 
5.7.2 push_heap 163 
5.7.3 make_heap 165 
5.7.4 sort_heap 166 
5.8 Minimum und Maximum 168 
5.9 Lexikographischer Vergleich 169 
5.10 Permutationen 170 
5.11 Numerische Algorithmen 172 
5.11.1 accumulate 172 
5.11.2 inner_product 173 
5.11.3 partial_sum 175 
5.11.4 adjacent_difference 176 
Teil III Über die STL hinaus: Komponenten und Anwendungen 179 
6 Mengenoperationen auf assoziativen Containern 181 
6.1 Teilmengenrelation 182 
6.2 Vereinigung 183 
6.3 Durchschnitt 183 
6.4 Differenz 184 
6.5 Symmetrische Differenz 185 
6.6 Beispiel 186 
7 Schnelle assoziative Container 189 
7.1 Grundlagen 189 
7.1.1 Kollisionsbehandlung 191 
7.2 Abbildung 191 
7.2.1 Beispiel 203 
7.3 Menge 204 
7.4 Überladene Operatoren für Mengen 205 
7.4.1 Vereinigung 206 
7.4.2 Durchschnitt 206 
7.4.3 Differenz 207 
7.4.4 Symmetrische Differenz 207 
7.4.5 Beispiel 207 
8 Verschiedene Anwendungen 209 
8.1 Kreuzreferenz 209 
8.2 Permutierter Index 212 
8.3 Thesaurus 215 
9 Vektoren und Matrizen 219 
9.1 Geprüfte Vektoren 219 
9.2 Matrix als geschachtelter Container 221 
9.2.1 Zweidimensionale Matrix 222 
9.2.2 Dreidimensionale Matrix 226 
9.2.3 Verallgemeinerung 229 
9.3 Matrizen für verschiedene Speichermodelle 229 
9.3.1 C-Memory-Layout 233 
9.3.2 Fortran-Memory-Layout 234 
9.3.3 Memory-Layout für symmetrische Matrizen 234 
9.4 Dünn besetzte Matrizen 236 
9.4.1 Indexoperator und Zuweisung 240 
9.4.2 Hash-Funktion für Indexpaare 241 
9.4.3 Klasse Matrixelement 242 
9.4.4 Klasse sparseMatrix 244 
9.4.5 Laufzeitmessungen 247 
10 Externes Sortieren 249 
10.1 Externes Sortieren durch Mischen 250 
10.2 Externes Sortieren mit Beschleuniger 257 
11 Graphen 263 
11.1 Klasse Graph 266 
11.1.1 Einfügen von Ecken und Kanten 268 
11.1.2 Analyse eines Graphen 269 
11.1.3 Ein- und Ausgabehilfen 274 
11.2 Dynamische Priority-Queue 277 
11.2.1 Datenstruktur 278 
11.2.2 Klasse dynamic_priority_queue 278 
11.3 Graph-Algorithmen 285 
11.3.1 Kürzeste Wege 286 
11.3.2 Topologische Sortierung eines Graphen 292 
A Anhang 299 
A.1 Hilfsprogramme 299 
A.1.1 Einlesen der Thesaurus-Datei roget.dat  299 
A.1.2 Einlesen einer Graph-Datei 300 
A.1.3 Erzeugen von Ecken mit Zufallskoordinaten 301 
A.1.4 Nachbarecken verbinden 302 
A.1.5 Eine \LaTeX -Datei erzeugen 304 
A.2 Quellen und Hinweise 305 
A.3 Lösungen zu einigen Übungsaufgaben 306 
A.4 Beschreibung der CD-ROM 313 
A.4.1 Ergänzung des Include-Verzeichnisses 313 
A.4.2 Dateien zu einführenden Beispielen 314 
A.4.3 Dateien zu den Standardalgorithmen 315 
A.4.4 Dateien zu Anwendungen und Erweiterungen 315 
Literaturverzeichnis 317 
Stichwortverzeichnis 319 

zurück