Functors - Funktionsobjekte
Functors sind universell verwendbare Funktionsobjekte. Sie erweitern das aus C bekannte Konzept der Funktionszeiger.
Fast jeder C Programmierer hat sich schon mit Zeigern auf Funktionen herumschlagen müssen. Diese kommen immer dann zur Anwendung, wenn eine Funktion als Parameter an eine andere Funktion übergeben werden soll. Beispiele sind die Standard C Library Funktionen bsearch und qsort. Diese können zum Sortieren und Durchsuchen von Feldern verwendet werden und bekommen als Parameter einen Funktionszeiger auf eine Vergleichsfunktion für zwei Feldelemente übergeben. Diese schreibt der Programmierer in der Regel selbst. Der Aufruf der Vergleichsfunktion erfolgt dabei aus bsearch beziehungsweise qsort heraus »zurück« in das Anwenderprogramm, weswegen diese Technik als »Callback« bezeichnet wird. Auch bei der Programmierung grafischer Benutzeroberflächen unter X11 oder der Windows API wird von Callback Funktionen reger Gebrauch gemacht.
Erweiterung von Funktionszeigern
In C++ tritt an die Stelle von Funktionszeigern das allgemeinere Konzept des Funktionsobjekts, welches auch als Functor bezeichnet wird:
Ein Functor ist ein Objekt, welches operator() definiert.
Je nachdem, ob der operator() keinen, einen oder zwei Parameter bekommt, bezeichnet man den Functor dann als Generator, unäre oder binäre Funktion.
Functors werden häufig in Zusammenhang mit STL Algorithmen verwendet. Ein Beispiel für einen Functor ist der iota Generator. Dieser erzeugt bei jedem Aufruf einen um eins erhöhten Wert und kann damit zur Erzeugung der kontinuierlich aufsteigenden Zahlenfolge 0, 1, 2, ... verwendet werden:
class iotaGen { public: int operator()() { return n++; } iotaGen() : n(0) {} private: int n; };
Es handelt sich also um eine ganz normale Klassendefinition, lediglich das Vorhandensein von operator() macht ein Objekt vom Typ iotaGen automatisch zum Functor. Der zusätzlich definierte Konstruktor dient nur dazu, um einen definierten Startwert der Zahlenfolge (hier: 0) zu gewährleisten. Im folgenden Kodeausschnitt wird der iota Generator nun in Zusammenarbeit mit dem der STL Algorithmus generate benutzt, um einen Vektor mit aufsteigenden Werten zu füllen:
#include <algorithm> #include <vector> using namespace std; vector<int> a(10); generate( a.begin(), a.end(), iotaGen());
Es wird zunächst der Vector a mit zehn Elementen erzeugt. Der Algorithmus generate ruft dann für jedes Element des Vektors operator() von iotaGen auf. Damit bekommen die einzelnen Vektorelemente die Werte 0, 1, 2, ... 9 zugewiesen.
Dem Zufall wird nachgeholfen
Mit diesem Wissen sind wir jetzt in der Lage, dem im Artikel »STL Zufälle« vorgestellten Algorithmus random_shuffle einen externen Zufallszahlengenerator zu verpassen. Es gibt nämlich eine Variante von random_shuffle, die als zusätzlichen Parameter einen Functor vom Typ RandomNumberGenerator bekommt. Schauen wir uns die Definition von RandomNumberGenerator an, so sehen wir, dass es sich dabei um einen unären Functor handeln muss. Der Parameter ist der Grenzwert N (Typ integer), der Functor muss dann eine zufällige Zahl f aus dem Bereich 0 <= f < N zurückliefern. Nun können wir das entsprechende Funktionsobjekt definieren:
#include <cstdlib> #include <ctime> class RandomNumber { public: RandomNumber() { srand(time(0)); } int operator() ( int n) { return (int)((double)n * rand()/(RAND_MAX+1.0)); } };
Operator(), der RandomNumber zum Functor macht, benutzt die Standard C Library Implementierung rand() zur Erzeugung der Zufallszahlen. Im Konstruktor von RandomNumber bekommt dieser Zufallszahlengenerator mittels srand(time(0)) einen von der Systemzeit abgeleiteten, »zufälligen« Startwert verpasst (siehe Zufallszahlen).
Der oben erzeugte Vektor a kann nun unter Verwendung dieses Functors zufällig durcheinander geschüttelt werden:
RandomNumber rnd; random_shuffle( a.begin(), a.end(), rnd); // Ausgabe copy( a.begin(), a.end(), ostream_iterator<int>(cout, " "));
Im Gegensatz zum Testprogramm aus »STL Zufälle« ist die Anordnung der Vektorelemente nach random_shuffle jetzt bei jedem Programmdurchlauf eine andere. Das liegt daran, dass wir unseren eigenen Zufallszahlengenerator rnd bei seiner Konstruktion mit einem »zufälligen« Startwert versehen können.
Vordefinierte Functors
Die STL stellt darüber hinaus eine Reihe von vordefinierten Functors zur Verfügung. Diese sind meist als Template realisiert, um mit den unterschiedlichsten Datentypen umgehen zu können. Im nächsten Beispiel werden die Functor-Templates less und greater benutzt, um mittels des sort Algorithmus einen Vektor entweder aufsteigend oder absteigend zu sortieren:
#include <functional> sort( a.begin(), a.end(), less<int>()); // sortiert aufsteigend sort( a.begin(), a.end(), greater<int>()); // sortiert absteigend
Interessant ist auch die Verwendung von vordefinierten Functors als »Callback« Funktionen in den *_if Algorithmen der STL, wie find_if, count_if, replace_if oder remove_if. Im abschließenden Beispiel wird mittels count_if gezählt, wieviele Elemente mit dem Wert 0 im Vektor a vorkommen. Dabei wird auf die Funktionsobjekte bind2nd und equal_to zurückgegriffen:
cout << "number of zero elements in a: " << count_if( a.begin(), a.end(), bind2nd(equal_to<int>(), 0)) << endl;