Funktionsobjekte

Wie kann man eigentlich Algorithmen der Standardbibliothek noch flexibler gestalten? Eine mögliche Antwort lautet: Funktionsobjekte. C++ bietet die Möglichkeit, Objekte zu bauen, die sich aufrufen lassen wie Funktionen. Alles, was man dafür tun muss, ist die Überladung des richtigen Operators. Damit geht dann alles Mögliche: Übergabe als Parameter an andere Funktionen, Speichern von Kontext etc.

Video

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
 
struct Wrapper
{
    int value;
     
    Wrapper(int v)
        : value(v)
        {
        }
};
 
struct CompareWrapper
{
    bool operator()(Wrapper const &v1, Wrapper const &v2)
    {
        return v1.value > v2.value;
    }
};
 
int main()
{
    std::vector<Wrapper> v;
    v.push_back(Wrapper(10));
    v.push_back(Wrapper(13));
    v.push_back(Wrapper(8));
    v.push_back(Wrapper(7));
    v.push_back(Wrapper(4));
 
    std::sort(v.begin(), v.end(), CompareWrapper());
     
    for(Wrapper const &w : v) {
        std::cerr << w.value << std::endl;
    }
}

Erklärung

In der C++-Standardbibliothek gibt es einige Anwendungsfälle, wo die vorhandenen Algorithmen Informationen von außen brauchen. C++11 bietet bspw. Algorithmen wie std::copy_if oder std::remove_if, die eine Bedingung erwarten, mit der sie entscheiden können, ob ein Objekt zu kopieren oder entfernen ist. Ebenso braucht std::sort ein Sortierkriterium. Im Standardfall verwendet der Algorithmus einfach den operator<() des ValueTypes der gegebenen Iteratoren. Das muss aber nicht immer passen. Manchmal möchte man nach ganz anderen Kriterien sortieren oder man hat für den gegebenen ValueType gar keinen operator<() definiert. Zu dem Zweck bietet der Algorithmus an, eine Vergleichsfunktion zu übergeben, die eine einfache Frage beantwortet: wenn ich zwei Objekte a und b habe, kommt a vor b?

Nun bietet C++ erstmal nicht die Möglichkeit, Funktionen als Parameter zu übergeben (es gibt zwar Funktionspointer, aber darüber schweigen wir hier mal grad). Funktionen sind schlicht keine first-class-citizen im Typsystem, wie das in anderen Sprachen, wie Python oder LISP der Fall ist. Dafür bietet C++ was anderes: man kann ein beliebiges Objekt wie eine Funktion aufrufen, indem man für den entsprechenden Typ den operator() implementiert und ihn so zum Funktionsobjekttyp macht. Objekte kann man dann ja wieder beliebig durch die Gegend reichen, mit Zustand anreichern oder in Datenstrukturen speichern. Dort, wo sie dann gebraucht werden, werden sie einfach wie Funktionen aufgerufen.

Im Beispiel oben ist die Klasse CompareWrapper ein Funktionsobjekt. Verantwortlich dafür ist der in Zeile 18 zu findende operator() (Achtung: doppelte Klammer! Die erste, leere Klammer gehört zum Operatornamen, die zweite enthält die eigentliche Parameterliste. Ein Operator mit ohne Parameter sähe also so aus: operator()()) der einen Funktionsaufruf mit zwei Parametern implementiert. Erzeugen wir also ein Objekt der Klasse, bspw. CompareWrapper c, dann können wir dieses Objekt als Funktion mit zwei Parametern aufrufen: c(param1, param2). Tatsächlich aufgerufen wird dann der entsprechenden Operator.

Von diesem Aufruf Gebrauch macht std::sort: das Objekt, welches als dritter Parameter übergeben wird, muss ein Funktionsobjekt sein, das man mit zwei zum ValueType der gegebenen Iteratoren (in unserem Fall Wrapper) kompatiblen Objekten aufrufen kann. Im Beispiel ist diese Anforderung durch die beiden Wrapper const & erfüllt. std::sort erwartet als Antwort ein true, wenn das erste übergebene Objekt vor dem zweiten kommen muss und ansonsten ein false. Die Antwort muss eine Halbordnung definieren, sprich: wenn a < b gilt, und b < c, dann muss auch a < c gelten. b < a, c < a und c < b dürfen hingegen nicht gelten. Eigentlich logisch, aber speziell wenn man eigene Vergleiche für Objekte mit mehreren Feldern implementiert, dann kann das schonmal leicht chaotisch werden. std::sort läuft zwar auch dann, wenn diese Bedingungen nicht erfüllt sind (es kann sie ja eh nicht prüfen), man sollte allerdings vom Ergebnis nicht überrascht sein.

Der Aufruf von std::sort ist dann ganz einfach: wir übergeben – wie so oft bei den Algorithmen – die Bereichsgrenzen in Form von Iteratoren und als dritten Parameter das Vergleichsobjekt. Der Algorithmus arbeitet dann in-place, d.h. die Objekte des Bereichs sind sortiert, nachdem der Aufruf zurückkehrt. Zusätzlicher Platz wird nicht benötigt (was für große Bereiche durchaus interessant ist).