Standard Template Librar y Übersicht

Standard Template Librar y
Übersicht
• STL
– Library mit allgemeinen Datenstrukturen und Algorithmen
– Bestandteil der Standard-Librar y im ISO/ANSI-Standard
– Unterstützt generisches Programmieren
• Template-Klassen und Template-Funktionen
• Wichtige STL-Komponenten
– Container-Klassen
• vector, list, set, map, etc. (ISO/ANSI: string)
– Generische Algorithmen
• find, sor t, reverse, for_each, etc.
• Unabhängig von Container-Classen (keine Member-Functions)
– Iteratoren
• Verallgemeiner tes Pointer-Konzept
© 2005 AG Rechnernetze
5-stl.1
Standard Template Librar y
Container-Klassen
• Sequence-Container
– Alle Objekte linear angeordnet
• vector<T>
– Variable Länge; random access; O(1)-insert/delete am Ende
• deque<T>
– Wie vector, O(1)-inser t/delete am Anfang und Ende
• list<T>
– Variable Länge; O(n)-access; O(1)-insert/delete an jeder Stelle
• T a[n]
– Normale C++-Arrays; feste Länge
– Alle generischen Algorithmen auch auf Arrays definier t
© 2005 AG Rechnernetze
5-stl.2
Standard Template Librar y
Container-Klassen
• Sortierte, assoziative Container
– Objekt-Zugriff über Key
– Zeitbedarf für Zugriff O(log N)
• set<Key>
• multiset<Key>
– Mengen von Keys
– Mehrere Kopien bei multiset; eindeutig bei set
• map<Key, T>
• multimap<Key, T>
– Assoziative Tabellen (Hash-Tabellen)
– Z. B. Zuordnung Name → Telefonnummer
© 2005 AG Rechnernetze
5-stl.3
Standard Template Librar y
Vector-Klasse
#include <iostream>
#include <vector>
vector<char> vec(char *s) {
vector<char> v;
while (*s != ’\0’)
v.push_back(*s++);
return v;
}
int main() {
vector<char> v = vec("hello");
cout << v.size() << endl;
vector<double> d(10, 3.141);
cout << d[3] << endl;
vector<Employee> e(20);
© 2005 AG Rechnernetze
5-stl.4
Standard Template Librar y
Vector-Klasse
#include <iostream>
#include <map>
#include <vector>
int main() {
map<char * ,long> telefonbuch;
telefonbuch["polizei"] = 110;
telefonbuch["Uni"] = 2187595;
telefonbuch["Uni Fax"] = 2187000;
cout << telefonbuch["Uni"] << endl;
telefonbuch.erase("Uni");
vector<map <char *, long> > telefonbuecher;
© 2005 AG Rechnernetze
5-stl.5
Standard Template Librar y
Iteratoren
#include <algorithm>
int main() {
vector<char> v = vec("hello");
sort(v.begin(), v.end());
– begin() und end() liefern Iteratoren
vector<char>::iterator begin(), end();
– Verallgemeiner tes Pointer-Konzept
– Iterator-Paar first und last definier t Iterator-Range:
[first, last)
– Auch normale Pointer sind Iteratoren:
int a[5] = { 12, 3, -4, 7, 0 };
sort(a, a+5);
© 2005 AG Rechnernetze
// sort(&a[0], &a[5])
5-stl.6
Standard Template Librar y
Iteratoren
• Iterator-Konzept
– Iteratoren entkoppeln Algorithmen von Container-Klassen
– Ermöglichen generische Funktionen
– sor t() keine Memberfunktion!
• Beispiel: generische find()-Funktion
– Suchen eines Elements in Arrays, Vektoren, Listen...
template <class Iterator, class T>
Iterator find(Iterator first, Iterator last, const T& value) {
while (first != last && *first != value)
++first;
return first;
}
© 2005 AG Rechnernetze
5-stl.7
Standard Template Librar y
Iteratoren
• Beispiel: generische find()-Funktion
vector<char> v = vec("hello");
vector<char>::iterator result;
...
if ((result = find(v.begin(), v.end(), ’h’)) == v.end())
// not found...
– find() kann auch auf Arrays angewendet werden
– Instantiierung z. B. für int* möglich:
int* find(int* first, int* last, const int& value) {
while (first != last && *first != value)
++first;
return first;
}
© 2005 AG Rechnernetze
5-stl.8
Standard Template Librar y
Iteratoren
• Anforderungen an Iteratoren
– Womit kann der Iterator-Typ in find() instantiier t werden?
• int*, double*
→ OK
• int, double
→ Nein, Operation *first undefinier t
– Interatoren in find() müssen diese Operationen unterstützen:
✘ first != last
✘ ++first
(auch Postfix)
✘ *first
(lesender Zugriff)
– Anforderungen erfüllt von:
• Normale Pointer-Typen
• vector<char>::iterator, etc.
• Input-Iterator
– Familie von Typen, die diese Anforderungen erfüllen
© 2005 AG Rechnernetze
5-stl.9
Standard Template Librar y
Iterator-Hierarchie
Input Iterator
Output Iterator
read-only
write-only
Forward Iterator
a++ ++a a==b a!=b *a
Bidirectional
Iterator
Forward Iterator
a-- --a
Random Access
Iterator
Bidirectional Iterator
a+i i+a a-i a+=i a-=i
a-b a<b a>b a<=b a>=b