Kapitel 9. Generische Programmierung
Generische Programmierung besitzt eine lange Tradition in C++, erlaubt sie es doch, Funktions- und Templateklassen zu definieren, die über Typen parametrisiert werden. Mit Variadic Templates, Zusicherungen zur Compile-Zeit und Aliase Templates wird die generische Programmierung in C++11 noch mächtiger.
Variadic Templates
Variadic Templates sind ein mächtiges Werkzeug für den Bibliotheksautor, Algorithmen zu schreiben, die beliebig viele Argumente annehmen können. Da Templates zur Übersetzungszeit instanziiert werden, steht das Ergebnis zur Laufzeit fest. Die Laufzeit wird spürbar entlastet.
Neben std::tuple profitieren noch andere Funktionen von Variadic Templates – std::thread und die Funktion sizeof, die direkt auf Variadic Templates aufgerufen werden kann.
Struktur
Die Struktur eines Variadic Template ist relativ ungewohnt.
01 template <typename ... Args>
02 void variadicTemplate(Args ... args){
03 // do something with args
04 }Durch die Ellipse ... wird Args zum Template Parameter Pack. Mit einem Parameter Pack sind zwei Operationen möglich. Es kann entpackt oder gepackt werden. Stehen die Punkte links von Args (Zeile 1), wird das Parameter Pack gepackt, stehen sie rechts davon (Zeile 2), wird es entpackt. Die Leerzeichen vor und hinter der Ellipse sind nicht notwendig.
Variadic Templates über Werten
Templates können nicht nur Typen, sie können auch Werte annehmen. Variadic Templates als spezielle Templates können dies natürlich auch. Die Templates in Listing 9.1, die Zahlen addieren bzw. multiplizieren und das Ergebnis zur Laufzeit anbieten, sind bewusst einfach gehalten, um den Blick aufs Wesentliche zu lenken.
calc.cpp
01 #include <iostream>
02
03 // primary template
04 template<int ...> struct sum;
05
06 // specialization for no argument
07 template<>struct
08 sum<>{
09 static const int value= 0;
10 };
11
12 // specialization for one or more arguments
13 template<int i, int ... tail> struct
14 sum<i,tail...>{
15 static const int value= i + sum<tail...>::value;
16 };
17
18 template<int ...> struct mult;
19
20 template<>struct
21 mult<>{
22 static const int value= 1;
23 };
24
25 template<int i, int ... tail> struct
26 mult<i,tail...>{
27 static const int value= i * mult<tail...>::value;
28 };
29
30 int main(){
31
32 std::cout << std::endl;
33
34 std::cout << "sum<>: " << sum<>::value <<std::endl;
35 std::cout << "sum<1,2,3,4,5>::value: "
<< sum<1,2,3,4,5>::value << std::endl;
36 std::cout << "sum<-20,-10,10,20>::value: "
<< sum<-20,-10,10,20>::value << std::endl;
37
38 std::cout << std::endl;
39
40 std::cout << "mult<>: " << mult<>::value
<<std::endl;
41 std::cout << "mult<1,2,3,4,5>::value: "
<< mult<1,2,3,4,5>::value << std::endl;
42 std::cout << "mult<-20,-10,10,20>::value: "
<< mult<-20,-10,10,20>::value << std::endl;
43
44
45 std::cout << std::endl;
46
47 }Zuerst die Ausgabe, dann die Analyse des Programms.
Betrachten wir die drei Klassen-Templates sum in den Zeilen 4, 7 und 13 (Listing 9.1), fällt zuallererst auf, dass das primäre oder allgemeine Template in Zeile 4 lediglich deklariert ist. Die C++-Syntax schreibt vor, dass das primäre Template zumindest deklariert werden muss. Darüber hinaus gilt, dass dies vor seiner Spezialisierung erfolgen muss. Das Klassen-Template calc besitzt zwei Spezialisierungen. In Zeile 7 steht die Spezialisierung für den Aufruf mit keinem Element, Zeile 13 enthält die für den Aufruf mit mindestens einem Element. Dieses Variadic Template verdient eine genauere Betrachtung. In sum<i,tail ... > werden die Argumente entpackt. Dabei wird das erste Argument an i, der Rest an tail gebunden. Die eigentliche Addition findet dann im Template-Körper statt, denn für tail wird sum rekursiv aufgerufen. Nach endlich vielen Iterationen sind alle Argumente abgearbeitet, und die Spezialisierung, die kein Argument erwartet, kommt zum Einsatz. Sie gibt als Ergebnis 0 zurück, das neutrale Element der Addition und das Ergebnis stehen durch ::value zur Verfügung (Zeilen 34 bis 42).
Rekursive Instanziierung
In Abbildung 9.2 ist exemplarisch die rekursive Instanziierung des Klassen-Templates sum für den Wert sum<1,2,3,4,5>::value dargestellt.
Die Klassen-Templates mult folgen der gleichen Struktur wie sum. Es gibt nur zwei kleine Modifikationen zu sum. Das neutrale Element der Multiplikation ist die 1 (Zeile 22), und zur Verrechnung der Elemente wird die Multiplikation verwendet (Zeile 27). Natürlich ist es möglich, dieses Beispiel so generisch zu definieren, dass es zwei Parameter mehr erhält: das neutrale Element und ein Funktions-Template, das die arithmetische Operation definiert. Genau das wird das Thema der Übungsaufgabe sein.
Typsicheres printf mit C++11
Ein Klassiker für den Einsatz von Variadic Templates ist ein typsicheres printf in C++11 (en.wikipedia.org, 2011). Ein kleines Programm darum gestrickt, printf in printf_ umbenannt, damit das C++11-printf_ mit dem C-printf nicht kollidiert, und die neue Funktionalität kann angewandt werden.
printf.cpp
01 #include <iostream>
02 #include <stdexcept>
03 #include <string>
04
05 void printf_(const char *s){
06 while (*s) {
07 if (*s == '%' && *(++s) != '%')
08 throw std::runtime_error("invalid format string:
missing arguments");
09 std::cout << *s++;
10 }
11 }
12
13 template<typename T, typename... Args>
14 void printf_(const char *s, T value, Args... args){
15 while (*s) {
16 if (*s == '%' && *(++s) != '%') {
17 std::cout << value;
18 ++s;
19 printf_(s, args...); // call even when *s == 0 to detect
// extra arguments
20 return;
21 }
22 std::cout << *s++;
23 }
24 throw std::logic_error("extra arguments provided to printf");
25 }
26
27
28 int main() {
29
30 std::cout << std::endl;
31
32 const char* m = "The value of %s is about %g.\n";
33 printf_(m,"pi", 3.14159);
34 printf(m,"pi", 3.14159);
35
36 /*
37 printf_("A string: %s");
38 printf("A string: %s");
39 */
40
41 std::cout << std::endl;
42
43 }Das C++11-printf_ und das C-printf erzeugen die gleiche Ausgabe (Listing 9.2).
Interessanter ist es aber, wenn die fehlerhaften printf-Aufrufe in den Zeilen 37 und 38 angewandt werden. Während die C++11-printf-Funktion mit einer eindeutigen Fehlermeldung das fehlende Argument moniert (Abbildung 9.4), erzeugt die C-printf-Funktion keine Fehlermeldung, dafür aber eine undefinierte Ausgabe (Abbildung 9.5).
Ein paar erläuternde Worte zu Listing 9.2: Die printf-Funktionalität wird durch die printf_-Funktion (Zeile 5) und das printf_-Funktions-Template (Zeile 13) angeboten. Die printf_-Funktion gibt einen Formatstring ohne Argumente direkt aus. Sie prüft in Zeile 8 lediglich, ob dieser ein gültiges Format besitzt. Das Funktions-Template ist da schon deutlich mächtiger. Es erhält drei Argumente: den Formatstring, den ersten Wert und die restlichen Werte als Parameter Pack. Im Formatstring werden die Zeichen, die keine Formatanweisungen sind, sukzessive in Zeile 22 ausgegeben. Wird ein Formatzeichen entdeckt, wird der Wert direkt nach std::cout (Zeile 17) geschrieben, und das Formatzeichen wird übersprungen (Zeile 18). Danach beginnt die eigentliche Rekursion. printf_ wird in Zeile 19 ohne das erste Argument aufgerufen.
fold.cpp
Aufgabe 9-1
Fassen Sie die Algorithmen sum und mult aus Listing 9.1 zu einem generischen Algorithmus zusammen.
Die beiden Algorithmen sum und mult folgen der gleichen Struktur. Sie unterscheiden sich nur in zwei Punkten. Zum einen ist dies das neutrale Element der Addition und der Multiplikation, und zum anderen sind es die Operationen auf den Elementen. Parametrisieren Sie daher das Template über beide Werte und testen Sie anschließend den generischen Algorithmus.
Wem diese Funktion bekannt vorkommt, der täuscht sich nicht. Die klassische fold*-Funktionsfamilie (Fold, 2011) aus der funktionalen Programmierung bietet eine Algorithmenstruktur an, die durch einen Startwert und eine Operation parametrisiert wird. Aber nicht nur in einer funktionalen Programmiersprache wie Haskell ist diese mächtige Funktion zu Hause, auch in Python ist sie unter dem Namen reduce und in C++ unter dem Namen accumulate im Einsatz. Mehr dazu findet sich in Anhang F.
showTuple.cpp
Aufgabe 9-2
Schreiben Sie ein Template, das die Werte eines std::tuple ausgibt.
std::tuple ist sehr umständlich auszugeben, da die Indizes Compile-Zeitkonstanten sein müssen. Hier kann nur Template-Metaprogramming (oder konstante Ausdrücke) eine generische Lösung anbieten. Schreiben Sie ein Template, das die Werte eines std::tuple ausgibt.
Vorsicht, die Aufgabe ist nicht einfach.
Zusicherungen zur Compile-Zeit
static_assert ist das Mittel der Wahl, um in C++11 Bedingungen zur Übersetzungszeit zu formulieren. Die Syntax ist recht einfach:
static_assert(Ausdruck,Text)Dabei muss Ausdruck eine Compile-Zeitkonstante sein, und Text ist die Nachricht, die ausgegeben wird, wenn die Bedingung nicht zutrifft. Der Ausdruck wird validiert, unabhängig davon, in welchem Bereich er sich befindet. Es sei nochmals explizit darauf hingewiesen:
Praxistipp
static_assert verursacht keine Laufzeiteinschränkungen.
static_asserts werden zur Übersetzungszeit ausgewertet. Das heißt insbesondere, dass keine negativen Auswirkungen auf das Laufzeitverhalten des Programms bestehen.
Statische Zusicherungen an den Programmcode sind aber nicht nur für Templates sinnvoll.
static_assert.cpp
01 #include <iostream>
02 #include <type_traits>
03
04 template< class T >
05 struct Add{
06
07 // check the assertion
08 static_assert(std::is_arithmetic<T>::value,
"Argument T must be an arithmetic type");
09
10 } ;
11
12 int main(){
13
14 // will work on my hardware
15 static_assert(sizeof(void*) >= 8,
"64-bit addressing is required for this program");
16
17 // int is arithmetic
18 Add<int> addInt= Add<int>();
19
20 // double is arithmetic
21 Add<double> addDouble= Add<double>();
22
23 // char is arithmetic
24 Add<char> addChar= Add<char>();
25
26 // std::string is not arithmetic
27 Add<std::string> addString= Add<std::string>();
28
29 }Zwei verschiedene static_asserts werden in Listing 9.3 verwendet. In Zeile 15 wird geprüft, ob sizeof(void*) mindestens 8 Byte groß ist. In Zeile 8 wird die Bedingung std::is_arithmetic<T>::value an die Template-Parameter formuliert. std::is_arithmetic ist eine Funktion aus der neuen Type-Traits-Bibliothek, der in Kapitel 19 noch ein eigener Abschnitt „Type-Traits“ gewidmet ist.
Das Übersetzen des Programms scheitert. Offensichtlich ist std::string kein arithmetischer Datentyp. Dies ist ein Beispiel für ein static_assert auf den Klassenbereich und damit eine Bedingung, die von jeder Template-Instanziierung eingehalten werden muss.
Praxistipp
Kombinieren Sie static_assert und die Type-Traits-Bibliothek.
Die volle Mächtigkeit entfaltet static_assert in Kombination mit der Type-Traits-Bibliothek. Erlaubt es die Type-Traits-Bibliothek, mächtige Zusicherungen als Compile-Zeit-Ausdrücke zu formulieren, validiert static_assert diese zur Übersetzungszeit.
myMatrix.cpp
Aufgabe 9-3
Machen Sie sich mit der Type-Traits-Bibliothek vertraut.
In Kapitel 19 im Abschnitt „Type-Traits“ ist die Funktionalität der neuen C++11-Type-Traits-Bibliothek detailliert beschrieben.
Aufgabe 9-4
Implementieren Sie eine einfache statische Matrix.
Implementieren Sie eine einfache statische Matrix. Die Template-Signatur ist in Listing 9.5 vorgegeben. Die Matrix soll über den Datentyp und die Anzahl der Zeilen und Spalten parametrisierbar sein. Stellen Sie zwei Punkte sicher:
Die Anzahl der Zeilen und der Spalten soll nicht negativ sein.
Die Anzahl der Zeilen oder der Spalten soll mindestens die Länge 1 besitzen.
Ziel der Aufgabe ist es, nur die Zusicherung an die Matrix zu stellen. Daher ist es nicht notwendig, die Klasse Matrix vollständig zu implementieren.
Ein paar Beispiele für Instanziierungen der Klasse Matrix:
int main() {
Matrix<int,10,5> intArray;
Matrix<std::string,3,4> strArray;
Matrix<double,0,1> doubleArray;
Matrix<long long,1,0> longArray;
Matrix<char,0,0> charArray;
}Aufgabe 9-5
Verwenden Sie statische Zusicherungen in verschiedenen Bereichen.
Schreiben Sie ein kleines Programm, das eine einfache statische Zusicherung static_assert (1 == 1,"1 == 1") in verschiedenen Bereichen anwendet.
Globaler Bereich
Bereich eines Namensraums
Blockbereich
Funktionsbereich
Klassenbereich
Sind Sie skeptisch, ob alle statischen Zusicherungen durch den Übersetzer geprüft wurden, ändern Sie die Zusicherung auf static_assert (1 == 0,"1 == 0").
Aliase Templates
Aliase Templates, ursprünglich unter dem Namen Template Aliases oder auch Template Typedef bekannt, werden über using definiert. Damit erlaubt es die C++11-Syntax, Synonyme auf teilweise gebundenen Templates zu erklären.
Syntax
Das einfache Klassen-Template Matrix in Listing 9.5, das über seinen Datentyp T, die Anzahl der Zeilen Line und Spalten Column parametrisierbar ist, soll dazu dienen, die Syntax des neuen Features zu veranschaulichen.
01 template < typename T, int Line, int Column > 02 class Matrix; 03 04 template <typename T, int Line > 05 using Square= Matrix< T, Line, Line >; 06 07 template <typename T, int Line > 08 using Vector= Matrix< T, Line, 1 >;
Sowohl Square (Zeilen 4 und 5) als auch Vector (Zeilen 7 und 8) sind Typsynonyme auf teilweise gebundenen Templates. Die partielle Spezialisierung bei Square besteht darin, dass die Matrix genauso viele Zeilen wie Spalten besitzen soll, die von Vektor, dass sie genau eine Spalte besitzt. Genauer betrachtet, besteht das Template-Synonym Square aus den folgenden Komponenten:
Template-Parameter-Deklaration:
template <typename T, int Line >Schlüsselwort:
usingneuer Template-Name:
SquareZeichen:
=Typausdruck:
Matrix< T, Line, Line>
Spezialisierung
Zwar können Synonyme auf die Spezialisierung eines Templates definiert werden (Listing 9.5), Spezialisierungen für Synonyme hingegen sind in C++11 nicht erlaubt. Template-Spezialisierungen auf den std::vector sollen dies verdeutlichen. Die Spezialisierung des Synonyms MyVector für Zeigertypen, die einen speziellen Speicheranforderer besitzen sollen, ist nicht zulässig.
template<typename T> using MyVector = std::vector<T, MyAllocator<T> >; template<typename T> using MyVector= std::vector<T*, MyPointerAllocator<T> >;
Hier ist die Anwendung eines Traits-Templates, das abhängig vom Argumenttyp den Speicheranforderer zurückgibt, die Lösung:
01 template<typename T>
02 struct MyAlloc{
03 typedef MyAllocator<T> type;
04 };
05
06 template<typename T>
07 struct MyAlloc<T*>{
08 typedef MyPointerAllocator<T> type;
09 };
10
11 template <typename T>
12 using MyVector= std::vector<T, typename MyAlloc<T>::type >;
13
14 MyVector<T> myVec1;
15 MyVector<T*> myVec2;Das primäre Template (Listing 9.7) in Zeile 1 stellt MyAllocator<T> (Zeile 3) die Spezialisierung für Zeiger MyPointerAllocator<T> in Zeile 6 über type zur Verfügung. Abhängig davon, ob T ein Zeiger ist, wird über MyAlloc<T>::type in Zeile 12 der richtige Speicheranforderer verwendet.
Die neue using-Syntax lässt sich als einfache Syntax für Synonyme auf Typen durch typedef verwenden.
01 typedef std::vector<int> IntVec; // C++98 02 using IntVec = std::vector<int>; // C++11 03 04 typedef void (*FuncPtr)(int,double); // C++98 05 using FuncPtr = void (*)(int,double); // C++11
Die Paare in Listing 9.8 erklären die gleichen Synonyme auf Typen. Wenn es um die Deklaration eines Funktionszeigers FuncPtr in den Zeilen 4 und 5 geht, ist die neue using-Syntax einfacher anzuwenden und zu lesen.
templateAliase.cpp
Aufgabe 9-6
Definieren Sie ein Typsynonym für std::set.
Die Elemente des STL-Containers std::set sind lexikografisch aufsteigend sortiert. Das ist nicht immer gewünscht. Tatsächlich ist std::set deutlich flexibler:
template <typename T,
typename Compare= less<T>,
typename Allocator= allocator<T> >
class set;Definieren Sie ein Synonym für Typen für std::set, sodass dessen Elemente lexikografisch absteigend sortiert sind.
Aufgabe 9-7
Wenden Sie Ihr Typsynonym aus Aufgabe 9-6 an.
Für die Vergleichsfunktion aus Aufgabe 9-6 gibt es in C++11 drei verschiedene Möglichkeiten:
Funktionen
Funktionsobjekte
Lambda-Funktionen
Spielen Sie alle Variationen durch und vergleichen Sie sie. Ein Funktionsobjekt müssen Sie nicht selbst implementieren, denn die Standard Template Library hat bereits eines im Angebot.