Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 13)

Klassenbibliotheken

• Vorgefertigte Container mit vielseitigen Funktionen
• Größtenteils standardisiert

STL

• Containerkonzept
• Begin() und End() sind die wichtigsten Interatoren einer Elementsequenz
• Ein Iterator ist ein Typ der mindestens die Operationen „++“, „*“ und „==“ beherrscht

Vector

• lückenloses und gekapseltes Datenfeld
• Zeiger zeigt auf das erste Element
• Beim Einfügen / Insert von Elementen werden alle Folgenden verschoben
• Wenn das letzte Element eingefügt wird muss nichts verschoben werden
• Alle Zeiger sind nach einem Insert / Delete unbrauchbar → neu bestimmen

Liste

• Funktionsweise nach außen hin wie bei Vector
• Aufbau „unter der Haube“ jedoch ganz anders
• leere List enthält mindestens das leere Element

Iterator

• Verbesserte Funktion der Zeiger

Accumulate

• Enthalten in <numeric>
• Verschieben des Zeigers auf das 1. Element um 1
• Addition der Summe + „1. Element“
• Überladen mit 4 Parametern

template
T accumulate( IterIn first, IterIn last, T init ){
while( first!=last ) {
init = init + *first;
++first;
}
return init;
}

//Anwendungsbeispiel
void f( vector& vd, int* p, int n )
{
	// addiere die Elemente von vd:
	// der Typ des 3. Arguments bestimmt auch die Rechengenauigkeit
	double sum = accumulate( vd.begin(), vd.end(), 0.0 );

	// addiere die int Werte in ein int (Überlauf gut möglich):
	// p+n kann man sich grob als &p[n] vorstellen
	int si = accumulate( p, p+n, 0 );

	// addiere die int Werte in ein long:
	long sl = accumulate( p, p+n, long(0) );

	// addiere die int Werte in ein double:
	double s2 = accumulate( p, p+n, 0.0 );

	// die Variable für den Rückgabewert kann im Initialisierer verwendet werden
	double s3 = 0;
	s3 = accumulate( vd.begin(), vd.end(), s3 );
}

int main()
{
	int sum = accumulate( v.begin(), v.end(), 0 );
	// sum wird 10
	// StdLib Header für accumulate(): numeric
}

template
T accumulate( IterIn first, IterIn last, T init, BinOp op )
{
	while( first!=last )
		{
			init = op( init, *first );
			// d.h. "init op *first"
			++first;
		}
	return init;
}

//Anwendungsbeispiel für Multiplikation
#include
void f( list& ld ) {
	double product = accumulate( ld.begin(), ld.end(), 1.0,
	multiplies() );
}

Funktoren

• Objekt, dass sich wie eine Funktion verhält und einen Rückgabetyp hat
• Erzeugung mittels Überladung der Operatorfunktion „()“

Klausur

• Funktoren könnten dran kommen

Multiplies

• bei nicht standardisierten Datentypen muss dieser Funktor überladen werden

Matrizen

• Objekt im 3. Raum → Tensor

Der map-Container

• Beinhaltet eine geordnete Sequenz von Schlüssel- Wert-Paaren, in der man anhand des Schlüssels nach dem zugehörigen Wert suchen kann

int main() {
  map<string,int> words; // Worte und ihre Häufigkeit
  string s;
  while( cin>>s && s!="quit" )
    ++words[s]; // der Schlüssel von words ist vom Typ string
                // die int Werte von words werden mit 0 initialisiert
                // wenn s schon enthalten ist, erhöht map dessen Wert mit ++ um 1
                // wenn s noch nicht enthalten ist, wird ein (s,0)-Paar
                // eingefügt und mit ++ auf den Wert 1 erhöht
                // words[s] liefert int& als Anzahl des Worts s
  typedef map<string,int>::const_iterator Iter;
  for( Iter p = words.begin(); p != words.end(); ++p )
    cout << p->first << ':' << p->second << '\n';
  return 0;
}

Ende: Seite 42