Axel Rogat
Objektorientiertes Programmieren mit C++ und JAVA
 
20.6: Funktions-Objekte Kapitel 20 21.1: Geschichte von JAVA 
 
  20.7 Standard-Algorithmen  
 

In <algorithm> (verweist auf std/algo.h) ist eine Vielzahl von STL-Container-bezogenen Algorithmen definiert. Sie sind alle generisch -- als Typparameter werden Iteratoren eingesetzt. Sie können also mit den STL-Containern und eigenen Strukturen verwendet werden, solange die Iterator-Anforderungen erfüllt werden.

Die Algorithmen arbeiten auf sogenannten Sequenzen. Eine Sequenz ist eine linear geordnete Folge von Elementen, beispielsweise ein zusammenhängender Ausschnitt aus einem Container, der durch zwei Iteratoren festgelegt wird, die auf den Anfang und direkt hinter das Ende zeigen. Die Sequenz wird dann intervallartig geschrieben als [i,j) mit Iteratoren i und j.

Es gibt manchmal verschiedene Versionen desselben Algorithmus:

Das Suffix "_if" wird dann verwendet, wenn es gefährlich erscheint, die normale Version zu überladen. Beispielsweise haben Paare wie find/find_if und count/count_if dieselbe Anzahl von Parametern (der Wert value wird gegen das Prädikat pred getauscht). Unter ungünstigen Umständen wäre keine korrekte Type-Unification möglich.

Alle STL-Funktionen sind im Anhang C aufgeführt. Es folgen einige kurze Beispiele zu ihrer Anwendung.

Beispiel: find_if

Auf folgende Weise findet man in einer Szenerie l aus Shapes den ersten Kreis:

list<Shape*>::iterator it=find_if( l.begin() , l.end() , is_circle() ); if (it==l.end()) cout << "Kein Kreis enthalten\n"; else cout << "gefunden, Referenzpunkt " << (*it)->getref() << endl;
Dabei ist is_circle folgendes Prädikat:
struct is_circle { bool operator () (const Shape *s) { return (typeid(*s)==typeid(Circle)); } };
Beispiel: for_each

So kann man auch eine ganze Szenerie in ein Fenster zeichnen lassen:

Window mywindow(64,40); (void)for_each(l.begin(),l.end(),do_draw(mywindow));

Das Funktions-Objekt do_draw ist folgendes:

class do_draw { private: Window &w; public: do_draw(Window &ww) : w(ww) { } void operator () (const Shape *s) const { w.draw(*s); } };

Beispiel: search

Auf folgende Weise kann man mit Hilfe von search eine Funktion indexof wie bei unserer String-Klasse implementieren:

int indexof(char *s1, char *s2) { vector<char> v1(s1,s1+strlen(s1)), v2(s2,s2+strlen(s2)); vector<char>::iterator i=search(v1.begin(),v1.end(),v2.begin(),v2.end()); return (i==v1.end())?(-1):(i-v1.begin()); }
Beispiel: next_permutation

Alle Permutationen von (0,...,n-1) erhält man wie folgt:

const int n=4; vector<int> v(n); for (int i=0;i<n;++i) v[i]=i; do { copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); cout << endl; } while (next_permutation(v.begin(),v.end()));
Beispiel: partition, find_if, sort

Wir wenden sort nicht auf ein ganzes Array, sondern auf zwei Teil-Arrays an. Das dient nur zur Demonstration, denn insgesamt werden wir dadurch meistens langsamer werden.

template <class T> struct is_negative { bool operator () (const T& x) { return x<0; } };
Wir partitionieren das Array zunächst mit dem Prädikat is_negative in eine negativen und einen nicht-negativen Teil. Danach suchen wir mit find_if die erste nicht-negative Zahl und wenden sort getrennt auf den ersten und auf den zweiten Teil an.
static int array[]={ 3,-1,2,5,-6,-9,0,-3,10,12,-5,-22,-1,5 }; const int n=sizeof(array)/sizeof(int); vector<int>::iterator fpos; vector<int> v(array,array+n); partition(v.begin(),v.end(),is_negative<int>()); fpos=v.end()-(find_if(v.rbegin(),v.rend(),is_negative<int>())-v.rbegin()); if (fpos!=v.begin()) sort(v.begin(),fpos); sort(fpos,v.end());
Zu beachten ist, daß find_if hier einen reverse_iterator zurückliefert, weil wir schließlich auch reverse_iterators (als die ersten beiden Parameter) übergeben haben. Für die Anwendung in sort müssen wir ihn in einen iterator umrechnen.

 
20.6: Funktions-Objekte Startseite 21.1: Geschichte von JAVA 
 

© 1998 Axel Rogat