Einführung in die Nutzung der
C++ - Standard - Bibliothek

Literatur:
(Amme) - Ammeraal, L.: STL for C++-Programmers;
Chichester: Wiley, 1997
(Brey) - Breymann, U.: Die C++ Standard Template Library;
München: Addison-Wesley, 1996
(Otte) - Ottewell, Ph.: Phil Ottewell's STL Tutorial; http://www.pottsoft.com/home/stl/stl.htmlx
(Brey_1)- Breymann, U.: C++ - Einführung und professionelle Programmierung; 7. Auflage
München, Wien: Hanser, 2003

Überblick

Einführung

Die Lehrveranstaltung Grundlagen der Informatik hat die Zielstellung,

Algorithmen und
Datenstrukturen

mithilfe der Programmiersprache C++ zu vermitteln. Dazu gehört auch die Vermittlung des Verständnisses, wie Listen, Strings, Templates usw. funktionieren. Wenn die ausgewählten Beispiele verstanden worden sind, ist es jedoch sinnvoll, sie nicht weiter zu entwickeln, sondern die vorgefertigten Komponenten der Standardbibliothek zu benutzen, weil letztere mehr bieten un zudem durch die Compilerhersteller gepflegt werden.
Die C++-Standard-Bibliothek basiert auf der Standard Template Library (STL) von HewlettPackard.

Konzepte der C++-Standard-Bibliothek

Vorteile

Templates
Auswertung der Templates geschieht zur Compilierzeit, es gibt keine Laufzeiteinbußen
Standardisierung
leichter portierbar
leichter wartbar

Schwerpunkte der C++-Standardbibliothek:

Schwerpunkt Header

Algorithmen algorithm

Container algorithm

bitset

deque

list

map

set

stack

vector

Iteratoren iterator

Ein-/Ausgabe fstream

iomanip

ios

iosfwd

iostream

istream

ostream

sstream

streambuf

Nationale Besonderheiten locale

Numerisches complex

limits

numerics

valarray

String string

Laufzeittyperkennung typeinfo

Fehlerbehandlung exeption

stdexept

Speicher memory

new

Hilfsfunktionen und -klassen utility

functional

Schwerpunkt Header

C-Header cassert

cctype

cerrno

cfloat

ciso646

climits

clocale

cmath

csetjump

csignal

cstdarg

cstddef

cstdio

cstdlib

cstring

ctime

cwchar

cwctype

In dem vorliegenden Material soll vorrangig auf die ersten drei Punkte eingegangen werden. Eine Übericht �ber alle Funktionen, die in der C++-Standard-Bibliothek definiert sind, findet sich in (Brey_1), online z.B. http://www.oop-mit-cpp.de/stdbib_html/index.html.

Das grundlegende Konzept

Container

Objekte zur Verwaltung anderer Objekte
- abgelegt als Wert (Wertsemantik) oder
- als Referenz
Verschiedene Arten: vector, list, dequeue, set, multiset, map, multimap, stack, queue, priority_queue
formuliert als Template-Klassen
Algorithmennamen (werden zur Compilezeit ausgewertet) sind für gleichartige Operationen, aber unterschiedliche Container gleich (Beispiel: Die Methode size() gibt die Anzahl der Elemente eines Containers zurück, sei er nun vom Typ vector,list oder map).

Iteratoren

arbeiten wie Zeiger
sind normale Zeiger oder zeigerähnliche Objekte
Zugriff auf Containerelement über Iteratoren
können sich von einem zum nächsten Element weiterbewegen, Methode bleibt aber verborgen (Beispiel: in einem Vektor: ++ das einfache Weiterschalten zur nächsten Position im Speicher; in einem binären Suchbaum: ++ Entlangwandern im Baum)

Algorithmen

arbeiten mit Iteratoren, die auf Container zugreifen
wegen der Allgemeinheit des Entwurfs arbeiten sie auch mit normalen Zeigern

Beispiel

Lesen und Ausgeben einer variablen Anzahl von Integer-Zahlen ungleich 0, die Werte sollen in einer geeigneten Datenstruktur gespeichert werden.

Realisierung mit ,,herkömmlichen`` Mitteln:

#include <iostream>
using namespace std;

int main()
{
  int vektor[1000]; // Maximal 1000 Elemente !!
  int i = 0, j;
  int x;
  cout << "Enter positive integers, followed by 0:\n";
  while (cin >> x, x != 0)
    {
      vektor[i] = x;
      i++;
    }
  cout << endl;  
  for ( j = 0; j < i; j++)
    cout << vektor[j] << " ";
  cout << endl;
  return 0;
}

Realisierung mit C++-Standardbibliotheksfunktionen

// readwr.c: Reading and writing a variable number of
//   nonzero integers (followed in the input by 0).
// From: Ammeraal, L. (1997) STL for C++ Programmers,
//       Chichester: John Wiley.

#include <iostream> 
//fuer g++ erst ab Version 2.8 verfuegbar
#include <vector>
using namespace std;
int main()
{  vector<int> v;
   int x;
   cout << "Enter positive integers, followed by 0:\n";
   while (cin >> x, x != 0)
      v.push_back(x);
   vector<int>::iterator i;
   for (i=v.begin(); i != v.end(); ++i) 
      cout << *i << " ";
   cout << endl;
   return 0;
}

Sequentielle Container

Das einführende Beispiel verwendete das Schlüsselwort vector. In diesem Programm kann vector vollständig durch list bzw. dequeue (Abk. für double ended queue) ersetzt werden. Es folgt das Listing für dequeue:

// readwrd.c: Reading and writing a variable number of
//   nonzero integers (followed in the input by 0).
// From: Ammeraal, L. (1997) STL for C++ Programmers,
//       Chichester: John Wiley.
#include <iostream>
#include <deque>
using namespace std;
int main()
{  deque<int> v;
   int x;
   cout << "Enter positive integers, followed by 0:\n";
   while (cin >> x, x != 0)
      v.push_back(x);
   deque<int>::iterator i;
   for (i=v.begin(); i != v.end(); ++i) 
      cout << *i << " ";
   cout << endl;
   return 0;
}

Der Nutzer bemerkt keinen Unterschied zwischen den drei möglich Versionen, Unterschiede bestehen aber in der internen Darstellung und in den möglichen Operationen:

Operation	Funktion	vector	list	deque
Einfügen am Ende	push_back	j	j	j
Löschen am Ende	pop_back	j	j	j
Einfügen am Anfang	push_front	n	j	j
Löschen am Anfang	pop_front	n	j	j
Einfügen irgendwo	insert	(j)	j	(j)
Löschen irgendwo	erase	(j)	j	(j)
Sortieren	sort	j	n	j

Im Folgenden soll ein Beispiel für Einfüge- und Löschoperationen in Listen angegeben werden:

// insdel.cpp: Insertions and deletions in a list.
// From: Ammeraal, L. (1997) STL for C++ Programmers,
//       Chichester: John Wiley.
#include <iostream>
#include <list>          
using namespace std;
void showlist(const char *str, const list<int> &L)
{  list<int>::const_iterator i;
   cout << str << endl << "  ";
   for (i=L.begin(); i != L.end(); ++i)
      cout << *i << " ";
   cout << endl;
}          

int main()
{  list<int> L;                
   int x;
   cout << "Enter positive integers, followed by 0:\n";
   while (cin >> x, x != 0)
      L.push_back(x);
   showlist("Initial list:", L);
   L.push_front(123);
   showlist("After inserting 123 at the beginning:", L);
   list<int>::iterator i = L.begin();
   L.insert(++i, 456);
   showlist(
      "After inserting 456 at the second position:", L);
   i = L.end(); 
   L.insert(--i, 999);
   showlist(
      "After inserting 999 just before the end:", L);
   i = L.begin(); x = *i;
   L.pop_front(); 
   cout << "Deleted at the beginning: " << x << endl;
   showlist("After this deletion:", L);
   i = L.end(); x = *--i;
   L.pop_back();
   cout << "Deleted at the end: " << x << endl;
   showlist("After this deletion:", L);
   i = L.begin();
   x = *++i; cout << "To be deleted: " << x << endl;
   L.erase(i);
   showlist("After this deletion (of second element):", 
      L);
   return 0;
}

Sortieren

Das folgende Beispiel ist eine Erweiterung des Programms readwr.c. Das Programm sortiert den Vektor v in aufsteigender Reihenfolge.

// sort1.cpp: Sorting a vector.
// From: Ammeraal, L. (1997) STL for C++ Programmers,
//       Chichester: John Wiley.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{  vector<int> v;
   int x;
   cout << "Enter positive integers, followed by 0:\n";
   while (cin >> x, x != 0) v.push_back(x);
   vector<int>::iterator i;
   cout << "Before sorting :\n";
   for (i=v.begin(); i != v.end(); ++i)
      cout << *i << " ";
   cout << endl;
   sort(v.begin(), v.end());
   cout << "After sorting: \n";
   for (i=v.begin(); i != v.end(); ++i) 
      cout << *i << " ";
   cout << endl;
   return 0;
}

Die Sortierung wird durch den Befehl:

sort(v.begin(), v.end());

ausgeführt.

keine Container-Memberfunktion, sondern Generischer Algorithmus oder kurz Algorithmus
Normalerweise ist die Zeile
```
#include <algorithm>
```
notwendig, diese Includedirektive wird aber implizit durch
```
#include <vector>
```
mit eingebunden

Für Arrays ist folgendes Fragment möglich:

int a[10], x, n = 0, *p;
   .....
   while (cin >> x, x != 0 && n < 10) a[n++] = x;
   sort(a, a+n);

Weitere Algorithmen

Die folgend angegebenen Algorithmen werden nur ansatzweise gezeigt:

find

....
   cin >> x;
   vector<int>::iterator i = 
      find(v.begin(), v.end(), x);
   if (i == v.end()) 
      cout << "Not found\n";
   else
   {  cout << "Found"; 
....

copy und ein Insert Iterator

....
{  int a[4] = {10, 20, 30, 40};
   vector<int> v(a, a+4);
   list<int> L(4);  // A list of 4 elements
   copy(v.begin(), v.end(), L.begin()); // copying 4 elements to L
   list<int>::iterator i;
   for (i=L.begin(); i != L.end(); ++i)
      cout << *i << " "; // Output: 10 20 30 40
.....

Problem: Im obigen Beispiel werden Elemente der Zielliste L überschrieben, was manchmal (häufig) nicht gewünscht ist. Lösung: Nutzung eines inserter

....
{  int a[4] = {10, 20, 30, 40};
   vector<int> v(a, a+4);
   list<int> L(5, 123);  // A list of 5 elements, all are 123
   list<int>::iterator i = L.begin();
   ++i; ++i;
   copy(v.begin(), v.end(), inserter(L, i));
....

merge - Mischen

....
  vector<int> a(5);
   a[0] = 2; a[1] = 3; a[2] = 8; 
   a[3] = 20; a[4] = 25;
   int b[6] = {7, 9, 23, 28, 30, 33};
   list<int> c; // List c is initially empty
   merge(a.begin(), a.end(), b, b+6, 
      inserter(c, c.begin()));
....

Strings

siehe Scriptum ,,Grundlagen der Informatik, Teil 2``, S. 21ff.

Iteratoren

Iteratoreigenschaften

Zustände

Iteratoren sind eine Verallgemeinerung von Zeigern. Sie erlauben es, mit verschiedenen Containern auf gleichartige Weise zu arbeiten. Ein Iterator kann verschiedene Zustaende haben.

kann ohne Verbindung zu einem Objekt erzeugt werden
kann während der Erzeugung oder danach mit Container verbunden werden. Die Methode begin() zeigt auf den Beginn des Containers, bei einem nichtleeren Container ergibt das Dereferenzieren den Wert des ersten Elements.
Methode end() liefert Zugriff auf die Position unmittelbar nach dem letzten Element des Containers, ist aber nicht dereferenzierbar.

Kategorien

Es gibt verschiedene Kategorien von Iteratoren in einer hierarchischen Anordnung:

Eingabe-Iterator
Ein Input-Iterator ist zum sequentiellen Lesen von Daten gedacht, zum Beispiel aus einem Container oder aus einer Datei. Ein Zurückspringen an eine schon gelesene Stelle ist nicht möglich (der - - -Operator ist nicht definiert).
Ausgabe-Iterator
Ein Output-Iterator kann sequentiell in einen Container oder in eine Datei schreiben, wobei der Dereferenzierungsoperator verwendet wird. Beispiel:
```
//>>Ausgabe<< ist ein Output-Iterator
*Ausgabe++ = Wert;  //in die Ausgabe schreiben und weiterschalten
```
Forward-Iterator
Wie Input- und Output-Iterator kann der Forward-Iterator sich vorwärts bewegen. Im Unterschied zu den vorgenannten Iteratoren können jedoch Werte des Iterators gespeichert werden, um ein Element des Containers wiederzufinden (z.B. Anker-Element einer einfach verketteten Liste).
Bidirectional-Iterator
Ein Bidirectional-Iterator kann all das, was ein Forward-Iterator kann. Darüber hinaus kann er noch mit dem
- - -Operator rückwärts gehen, sodass er für doppelt verkettete Listen geeignet ist.
Random-Access-Iterator
Ein Random-Access-Iterator kann alles, was ein Bidirectional-Iterator kann. Zusätzlich ist ein wahlfreier Zugriff möglich, wie er für einen Vektor benötigt wird. Der wahlfreie Zugriff wird durch den Indexoperator operator[]() realisiert.

=15cm $\epsffile{iterator.ps}$ Der Iteratortyp wird jeweils zur Compilezeit festgelegt, damit wird entsprechend der Containerklasse und eines auszuführenden Algorithmus der jeweilig am besten geeignete Typ ausgewählt.

Assoziative Container

mapKey, Type, Compare
multimapKey, Type, Compare
setKey, Compare
multisetKey, Compare

Map und Multimap

#include <map>

Sichern Schlüßel-Wert-Paare
Multimaps erlauben duplizierte Schlüssel, Maps nur einfache

Some Map Access Functions	Purpose
begin()	Returns iterator pointing to
	first element
end()	Returns iterator pointing _after_
	last element
swap( , )	Swap two elements
insert( , )	Insert a new element
size()	Number of elements in map
max_size()	Maximum possible number of elements
	in map
empty()	True if map is empty
	Subscript search access operator

// Beispiel fuer Abbildung (map)
#include<map>
#include<string>
using namespace std;

// zur Abkuerzung zwei typedefs
// Vergleichsobjekt:  less<long>()
typedef map<long, string> Abbildungstyp;
typedef Abbildungstyp::value_type Wertepaar;


int main()
{
    Abbildungstyp Abbildung;

    Abbildung.insert( Wertepaar(836361136, "Andreas"));
    Abbildung.insert( Wertepaar(274635328, "Bernd"));
    Abbildung.insert( Wertepaar(260736622, "Juergen"));
    Abbildung.insert( Wertepaar(720002287, "Karin"));
    Abbildung.insert( Wertepaar(138373498, "Thomas"));
    Abbildung.insert( Wertepaar(135353630, "Uwe"));
    // Einfuegen von Xaver wird nicht ausgef�hrt, weil
    //   der   Schluessel schon vorhanden ist.
    Abbildung.insert( Wertepaar(720002287, "Xaver"));

/* 

Die Ausgabe der Namen ist wegen der unterliegenden 
Implementierung nach Nummern sortiert: 

*/ 

cout << "Ausgabe:\n";
    Abbildungstyp::iterator iter = Abbildung.begin();
    while(iter != Abbildung.end())
    {
          cout << (*iter).first << ':'     // Nummer
               << (*iter).second           // Name
               << endl;
          ++iter;
    }


    cout << "Ausgabe des Namens nach Eingabe der Nummer\n"
         << "Nummer: ";
    long Nummer;
    cin >> Nummer;
    iter = Abbildung.find(Nummer);    // O(log N), siehe Text


    if(iter != Abbildung.end())
        cout << (*iter).second << ' ' // O(1)
             << Abbildung[Nummer]     // O(log N)
             << endl;
    else cout << "Nicht gefunden!" << endl;
}

Set und Multiset

#include <set>

Set speichert nur einfache Schlüssel, das heißt der Schlüssel ist der Wert.

Some Set Access Functions	Purpose
begin()	Returns iterator pointing to first
	element
end()	Returns iterator pointing _after_
	last element
swap( , )	Swap two elements
insert( , )	Insert a new element
size()	Number of elements in set
max_size()	Maximum possible number of
	elements in set
empty()	True if set is empty

// Beispiel fuer Menge (set)
#include<set>
#include<showseq>

using namespace std;
int main()
{
    int i;
    set<int> Menge;  // Vergleichsobjekt:  less<int>()

    for(i = 0; i < 10; i++) Menge.insert(i);
    for(i = 0; i < 10; i++) Menge.insert(i); // ohne Wirkung
    showSequence(Menge);                     // 0 1 2 3 4 5 6 7 8 9

/*
Die Anzeige demonstriert, da� die Elemente der Menge wirklich genau
einmal vorkommen. Im folgenden werden Elemente geloescht, wobei in 
der ersten Variante zunaechst das Element gesucht wird, um
es dann mit dem gefundenen Iterator zu loeschen. In der zweiten 
Variante wird die Loeschung ueber den angegebenen Schl�ssel 
vorgenommen. 
*/ 

cout << "Loeschen per Iterator\n"
            "Welches Element loeschen? (0..9)" ;
    cin >> i;
    set<int>::iterator iter = Menge.find(i);
    if(iter == Menge.end())
       cout << i << " nicht gefunden!\n";
    else
    {
        cout << "Es gibt " << Menge.count(i)            // 1
             << "-mal das Element " << i << endl;
        Menge.erase(iter);
        cout << i << " geloescht!\n";
        cout << "Es gibt " << Menge.count(i)            // 0
             << "-mal das Element " << i << endl;
    }
    showSequence(Menge);
}

Algorithmen

Es existieren 60 Algorithmen, die in 8 Klassen eingeteilt werden können:

Nichtmodifizierende Sequenzoperationen - diese exttrahieren Informationen, suchen Positionen, modifizieren keine Elemente, z.B. find()
Modifizierende Sequenzoperationen - Vielfältige Operationen, die Elemente, auf die sie jeweils zugreifen, verändern, z.B. swap(), fill()
Sortieren - Sortieren und Prüfen der Konsistenz (Gültigkeit von Indizees), z.B. sort(), lower_bound()
Mengenalgorithmen - Erzeugen von sortierten Strukturen, Mehrmengenoperationen, z.B set_union(), set_intersection().
Heap-Operationen z.B. make_heap(), push_heap(), sort_heap().
Minimum und Maximum - z.B. min(), max(), min_element(), max_element().
Permutationen - z.B. next_permutation(), prev_permutation().
Numerische Algorithmen - z.B. partial_sum().
```
#include <numeric>
```

Detaillierte Beschreibung - siehe (Brey, Brey_1)

Über dieses Dokument ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

The command line arguments were:
latex2html -split 0 c++stdlib.tex

The translation was initiated by Dr.Andreas Mueller on 2007-10-22

Dr.Andreas Mueller 2007-10-22

Schwerpunkt	Header
Algorithmen	algorithm
Container	algorithm
	bitset
	deque
	list
	map
	set
	stack
	vector
Iteratoren	iterator
Ein-/Ausgabe	fstream
	iomanip
	ios
	iosfwd
	iostream
	istream
	ostream
	sstream
	streambuf
Nationale Besonderheiten	locale
Numerisches	complex
	limits
	numerics
	valarray
String	string
Laufzeittyperkennung	typeinfo
Fehlerbehandlung	exeption
	stdexept
Speicher	memory
	new
Hilfsfunktionen und -klassen	utility
	functional

Schwerpunkt	Header
C-Header	cassert
	cctype
	cerrno
	cfloat
	ciso646
	climits
	clocale
	cmath
	csetjump
	csignal
	cstdarg
	cstddef
	cstdio
	cstdlib
	cstring
	ctime
	cwchar
	cwctype