Werbung

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

C++ Template Metaprogramming 101

Wie man konditionale Templates schreibt...

  1. -AB-
    Programmiersprache(n):
    C++
    Vorwort
    Dies ist eine Einführung in die Template-Metaprogrammierung in C++. Kein leichter Stoff, aber mit ein bisschen Mühe kriegen wir am Ende doch halbwegs schönen Code hin :) Vermutlich kommen in Zukunft noch Artikel dazu, die kleinere (Sub-)Probleme bearbeiten.
    Los gehts!

    Templates hat eigentlich jeder schonmal benutzt. Süße kleine Dinger, mit ihren spitzen Klammern und so. Aber man kann mehr mit ihnen machen, als nur einen vector für verschiedene Datentypen bereitzustellen.
    Dieser Text soll etwas mehr in die Details (und in sinnvollere Applikationen) gehen als das bekannte "Fakultät zur compile-time ausrechnen"-Beispiel, kratzt aber dennoch nur die Oberfläche an.
    Wer die Wikipedia-Seite gelesen hat, weiß schon, dass man Schleifen beispielsweise durch Rekursionen ersetzen kann. Aber noch simpler: Wie schreibt man ein simples if mit Templates?
    Hierfür brauchen wir erstmal ein bisschen Beispielcode. Sagen wir, wir möchten ein Set implementieren. Gibts schon, std::set - aber je nach Gebrauch könnte man ein sortiertes oder ein unsortiertes Set bevorzugen.
    (Es hängt immer von der Anzahl der Elemente, Insert- und Suchvorgänge ab, welches perfomanter ist. std::set hält immerhin immer eine ganze Tree-Struktur...) (Und ja, seit C++11 gibt es auch ein std::unordered_set, aber bleiben wir beim Thema.)

    Wir wollen also ein Set, welchem wir zur Compilezeit sagen wollen, ob es sortiert oder unsortiert sein soll. Das Interface für beide Varianten soll dasselbe sein. Außerdem wollen und wir wollen absolut keinen Nachteil bei der Benutzung - das sortierte Set darf z.B. nicht langsamer sein, als ein std::set - eine if-Abfrage zur Laufzeit scheidet also aus.

    Also schreiben wir...
    Code (C++):
    Quelltext kopieren
    1. template <typename T, typename Container=std::vector<T>>
    2. class Set
    3. {
    4. public:
    5.     typedef T value_type;
    6. private:
    7.     Container mData;
    8. };
    Eine Klasse, die einen Member mData vom templateabhängigen Typen Container enthält. Per default-Templateparameter wird ein std::vector vorgegeben, der unser unsortiertes Set darstellen wird, alternativ kann man ein std::set angeben, was, nunja, ein sortiertes Set wird.


    Und so können wir sortierte und unsortierte Sets instantiieren:
    Code (C++):
    Quelltext kopieren
    1.     Set<int> mySet; //exploiting std::vector default parameter
    2.     Set<int, std::set<int>> mySortedSet;
    Natürlich braucht unser Set auch erstmal mindestens eine add()-Methode. Für das std::set wäre da die insert()-Methode angebracht - für denstd::vector würden wir gerne push_back() verwenden, das wiederum gibt es aber nicht für das set. Ein Kompromiss wäre, die insert()-Methode mit vorgeschlagener Einfügeposition (Hint) für beide zu verwenden, und, um die kostspielige Reallokation beim Vektor zu vermeiden, das letzte Element mitzugeben - aber der unter Umständen sehr suboptimale Hint macht das Einfügen in das set natürlich teuer.
    Keine Sorge, diese Unschönheiten bügeln wir später alle noch aus. Erstmal wieder Code:
    Code (C++):
    Quelltext kopieren
    1. #include <vector>
    2. #include <set>
    3. template <typename T, typename Container=std::vector<T>>
    4. class Set
    5. {
    6. public:
    7.     typedef T value_type;
    8.     void add(const T& value)
    9.     {
    10.         //TODO: duplicate check
    11.         mData.insert(mData.end(), value); // insert with hint "at the end"
    12.     }
    13. private:
    14.     Container mData;
    15. };
    16.  
    17. int main()
    18. {
    19.     Set<int> mySet;
    20.     Set<int, std::set<int>> mySortedSet;
    21.     mySet.add(8);
    22.     mySortedSet.add(15);
    23. }
    So weit, so gut. Jetzt laufen wir aber schon in das erste Problem: Im unsortierten Set müssen wir selbst verhindern, dass Duplikate eingefügt werden! Andererseits wollen wir definitiv nicht das std::set sinnlos nach Duplikaten durchsuchen...
    Schreiben wir erstmal eine exists()-Methode, die uns verrät, ob ein Element bereits im Set existiert. std::find bietet sich dann als lineare Suche für den std::vector an - für das std::set würden wir aber gerne dessen Memberfunktion find() aufrufen.
    Oh, Probleme über Probleme!

    Wie würde das Problem ohne Metaprogrammierung gelöst?
    Polymorphie wäre eine Möglichkeit. Man könnte ein SortedSet und ein UnsortedSet von einer gemeinsamen Basisklasse ableiten. Allerdings hat man dann bei jedem Methodenaufruf den virtuellen Funktionsaufruf als overhead dabei, man könnte in das slicing problem laufen, und überhaupt: Es ist zur compilezeit ja schon klar, was ich verwenden will. Warum also zur Laufzeit erst die Entscheidung treffen?
    Klasse umbenennen wäre die zweite Lösung. Einfach zwei Klassen implementieren, Set und UnsortedSet. Aber in diesem Fall müssen wir tatsächlich allen Code doppelt schreiben, auch wenn das meiste ja identisch oder zumindest ähnlich ist.
    Template überladen: Man könnte die Klasse für jedes Template überladen. Letztendlich schreiben wir damit auch alles doppelt, bloß behalten wir denselben Namen bei.
    Oder wir benutzen Metaprogrammierung.
    Es ist doch so: Wir wollen insert() nutzen, if der Container-Typ ein set ist, und push_back() if er ein vector ist.
    if ein vector verwendet wird, wollen wir zuerst suchen, ob das einzufügende Objekt schon existiert, und in der exists()-Methode std::find verwenden. Im Falle if es ein std::set ist, wollen wir beim Einfügen nicht suchen, und im exists()-Check die Memberfunktion find() nutzen.

    Was wir also brauchen, ist ein Template-Metaprogramming "if".
    Wo wir das herbekommen, mag ein wenig verwunderlich sein. Die Antwort lautet oldschool Funktionsüberladung. Ja genau! Wie damals, wo wir eine doSomething(int) und doSomething(double) geschrieben haben, und der Typ, den wir übergeben haben, bestimmt hat, welche der beiden Funktionen aufgerufen wird. Dasselbe Konzept nutzen wir jetzt, um zu entscheiden, was für Aktionen, abhängig von einem Datentypen, ausgeführt oder benutzt werden sollen.
    Also fügen wir Methoden hinzu etwa wie folgt:
    Code (C++):
    Quelltext kopieren
    1. bool exists(const T& value) const
    2. {
    3.     return exists_impl(value, mData);
    4. }
    5. inline bool exists_impl(const T& value, const std::vector<T>&) const
    6. {
    7.     return std::find(mData.begin(), mData.end(), value) != mData.end();
    8. }
    9. inline bool exists_impl(const T& value, const std::set<T>&) const
    10. {
    11.     return mData.find(value) != mData.end();
    12. }
    Wir übergeben mData - das Objekt, was alle Daten hält - an die Memberfunktion. Dort wird dem Parameter aber nicht einmal ein Name zugewiesen, der Compiler wird den Parameter völlig wegoptimieren. Vorher jedoch legt dieser Parameter fest, welche der Methoden aufgerufen wird - die für den std::vector, oder die für das std::set.
    Der Compiler hält uns jetzt zwar für doof, dass wir (fast) dieselbe Methode in exists() nochmal aufrufen, sollte dieses Missgeschick aber ebenfalls ausbügeln - auch ohne inline-Vorschlag. (Eine derart simple Funktion wird in einem optimierten Build ge-inlined.)
    Da die Implementation von exists_impl() für beide Fälle völlig unterschiedlich ist, ist es klar, dass wir die Methode zwei mal schreiben müssen. Die dritte Methode, exists(), müsste aber doch nicht sein, oder? (Keine Sorge, das wird später noch schöner.)
    Außerdem - was, wenn ein Spaßvogel die Set-Klasse mit einem anderen Typen instantiiert, z.B. Set<int, std::multiset<int>>?
    Eigentlich wollen wir ja gar nicht die intern verwendete Klasse nach draußen tragen, wir wollen bloß, dass der Nutzer das Set mit einem "sortiert" oder "unsortiert"-Tag versehen kann. Sprich, wir hätten gern, dass jemand eine Klasse Set<int, sorted> oder Set<int, unsorted> anlegen kann.

    Tag-Klassen
    Willkommen in der wundervollen Wert der tag classes. Wir legen einfach eine leere Klasse sorted und eine Klasse unsorted an - und diese ersetzen unseren zweiten Template-Parameter.

    Code (C++):
    Quelltext kopieren
    1. struct sorted{};
    2. struct unsorted{};
    Mit Tag-Klassen wie diesen lassen sich Funktionen überladen, und dadurch der Kontrollfluss steuern.

    Allerdings laufen wir gleich wieder ins nächste Problem - eine Funktion können wir überladen, aber was machen wir mit der Membervariablen mData?

    Wir könnten einfach hingehen, und in die sorted-Tag-Klasse einen typedef schreiben, der uns container_type zu std::set definiert, und in unsorted definieren wir ihn zu std::vector.
    Vor C++11 ging das noch nicht. std::vector ist ein Template, und ein nicht völlig spezialisiertes Template lässt sich nicht typedef-en.

    Template-Alias
    C++11 erlaubt uns, hier ein Template-Alias zu verwenden - ein Template-Typedef; das Schlüsselwort ist using.

    In den beiden Tag-Klassen können wir also unseren gewünschten Typen angeben, unabhängig davon, welches T dort wiederum verwendet wird:
    Code (C++):
    Quelltext kopieren
    1. struct sorted
    2. {
    3.     template<class T>
    4.     using container_type = std::set<T>;
    5. };
    6.  
    7. struct unsorted
    8. {
    9.     template<class T>
    10.     using container_type = std::vector<T>;
    11. };
    Und unsere Klasse Set können wir jetzt, statt std::vector und std::set als template-Parameter zu verwenden, mit unseren Tag-Klassen templatisieren:
    Code (C++):
    Quelltext kopieren
    1. template <typename T, typename is_sorted=unsorted>
    2. class Set
    3. {
    4. public:
    5.     typedef T value_type;
    6.     void add(const T& value)
    7.     {
    8.         ...
    9.     }
    10. private:
    11.     typedef typename is_sorted::template container_type<T> ContainerType;
    12.     ContainerType mData;
    13. };
    Die Syntax, um an ein template-parametrisiertes, ge-aliastes template heranzukommen ist ein bisschen gewöhnungsbedürftig, das gebe ich zu. :)

    An sich bedeutet die Zeile bloß "in is_sorted gibt es einen Typen, nenn ihn bitte ContainerType":
    typedef is_sorted::container_type ContainerType;
    Dass is_sorted::container_type ein Typename ist, weiß der Compiler aber nicht (es könnte auch eine statische Variable sein!) - hierfür noch der Hinweis "typename".
    typedef typename is_sorted::container_type ContainerType;
    Als nächstes weiß der Compiler zwar, dass is_sorted::container_type ein typ ist - aber so ganz stimmt das auch nicht, denn es ist ja ein templatisierter Typ. Hier kommt das unheimlichste Konstrukt in C++ zum Vorschein - wir müssen *direkt* vor den Typen ein "template" schreiben - nicht vor is_sorted, sondern vor container_type. Dadurch wir das Statement aufgebrochen, und wir sind fast fertig mit:
    typedef typename is_sorted::template container_type ContainerType;
    Allerdings ist container_type ein template <T> - und wir hätten auch gern eins, wollen wir doch selbst ein <T> angeben. Und schon haben wir es:
    typedef typename is_sorted::template container_type<T> ContainerType;
    "Compiler, bitte nenne den Typen, der auch ein Template von T ist, in der Klasse is_sorted von jetzt an ContainerType."

    (Der Compiler musste mich selbst drei mal korrigieren, bis ich das Statement richtig hatte. Er war aber sehr hilfsbereit dabei.)

    Traits-Klassen
    Ohne C++11, oder auch jetzt noch, um Informationen an eingebaute Datentypen zu hängen, benutzt man statt des Alias-Templates eine traits-Klasse. Traits-Klassen werden in C++ immer dann verwendet, wenn man spezifische Informationen an eine weitere Klasse "anhängen" will. In unserem Beispiel wäre es denkbar, dass wir sorted und unsorted auch für eine andere Klasse verwenden wollen - wie etwa einer Map - und in denen bräuchten wir andere Datentypen! Schreiben wir obigen Code doch einfach nochmal neu!

    Wir behalten sorted und unsorted als Tag-Klassen. Diese lassen wir komplett leer (wie Tag-Klassen eigentlich sein sollten) und schreiben eine Klasse set_traits<sorted_tag>, die uns weitere Informationen zum sorted_tag geben kann. Da die Klasse set_traits heißt, ist klar, dass wir z.B. für eine Map eine andere Klasse verwenden würden.
    Da wir diesmal nicht das C++11-Template-Alias verwenden wollen, geben wir hier auch der Traits-Klasse noch einen weiteren Parameter <T>. Das können wir uns hier erlauben, wollten aber vorher nicht eine Tag-Klasse templatisieren.

    Code (C++):
    Quelltext kopieren
    1. template <typename T, typename sorted_tag>
    2. struct set_traits
    3. {
    4.     //generic implementation should be prevented, see another how-to
    5. };
    6.  
    7. template <typename T>
    8. struct set_traits<T, sorted>
    9. {
    10.     typedef std::set<T> container_type;
    11. };
    12.  
    13. template <typename T>
    14. struct set_traits<T, unsorted>
    15. {
    16.     typedef std::vector<T> container_type;
    17. };
    Das sind unsere Traits-Klassen. Die oberste ist die Template-Deklaration, die unteren beiden sind partielle Spezialisierungen für die sorted/unsorted Tag-Klassen. (Man kann mit verschiedenen Tricks noch verhindern, dass die oberste Klasse mit einem anderen Typen instantiiert werden kann, aber das ist eine andere Geschichte, und soll ein andermal erzählt werden.)

    Über eine ähnliche Syntax wie vorhin, bloß einfacher (weil wir kein Template-Alias mehr verwenden) können wir in der Set-Klasse jetzt unseren Container anlegen:
    Code (C++):
    Quelltext kopieren
    1. template <typename T, typename is_sorted=unsorted>
    2. class Set
    3. {
    4. public:
    5.     typedef T value_type;
    6.     void add(const T& value)
    7.     {
    8.         ...
    9.     }
    10. private:
    11.     typedef typename set_traits<T, is_sorted>::container_type ContainerType;
    12.     ContainerType mData;
    13. };
    Jetzt sind wir unserer Wunschlösung schon näher. Wir können mit z.B. Set<int, sorted> oder Set<int, unsorted> sortierte oder unsortierte Sets anlegen.

    Unser vollständiger Code ist also jetzt:
    Code (C++):
    Quelltext kopieren
    1. #include <vector>
    2. #include <set>
    3. #include <algorithm>
    4.  
    5. struct sorted{};
    6. struct unsorted{};
    7.  
    8. template <typename T, typename sorted_tag>
    9. struct set_traits
    10. {
    11.     //generic implementation should be prevented, see another how-to
    12. };
    13.  
    14. template <typename T>
    15. struct set_traits<T, sorted>
    16. {
    17.     typedef std::set<T> container_type;
    18. };
    19.  
    20. template <typename T>
    21. struct set_traits<T, unsorted>
    22. {
    23.     typedef std::vector<T> container_type;
    24. };
    25.  
    26.  
    27. template <typename T, typename is_sorted=unsorted>
    28. class Set
    29. {
    30. public:
    31.     typedef T value_type;
    32.  
    33.     void add(const T& value)
    34.     {
    35.         add_impl(value, is_sorted());
    36.     }
    37.  
    38.     bool exists(const T& value) const
    39.     {
    40.         return exists_impl(value, is_sorted());
    41.     }
    42.  
    43. private:
    44.     inline void add_impl(const T& value, unsorted)
    45.     {
    46.         //linear search
    47.         auto foundAt = std::find(mData.begin(), mData.end(), value);
    48.  
    49.         if(foundAt == mData.end())
    50.             mData.push_back(value);
    51.         else
    52.             *foundAt = value;
    53.     }
    54.  
    55.     inline void add_impl(const T& value, sorted)
    56.     {
    57.         mData.insert(value); // insert without hint
    58.     }
    59.  
    60.     inline bool exists_impl(const T& value, unsorted) const
    61.     {
    62.         return std::find(mData.begin(), mData.end(), value) != mData.end();
    63.     }
    64.  
    65.     inline bool exists_impl(const T& value, sorted) const
    66.     {
    67.         return mData.find(value) != mData.end();
    68.     }
    69.  
    70.     typedef typename set_traits<T, is_sorted>::container_type ContainerType;
    71.     ContainerType mData;
    72. };
    (Anmerkung: die Sets verhalten sich momentan nicht identisch. Das unsortierte Set basiert auf dem ==-Vergleich, wohingegen das sortierte auf kleiner/größer prüft. Nicht ideal - aber das ist ja nur ein Beispiel.)

    exists_impl() und add_impl() sind fast völlig unterschiedlich - da ergibt es nicht viel Sinn, diese noch weiter zusammen zu ziehen. Trotzdem ist es doch unschön, dass wir die exists() und add()-Methoden noch brauchen - und das nur, um die anderen Methoden aufzurufen.
    Leider können wir nicht exists() und add() nicht partiell spezialisieren - der C++-Standard verbietet das. Und natürlich wollen dir das Interface für exists() und add() auch nicht so verändern, dass wir ein weiteres (sorted/unsorted) Objekt verlangen - immerhin haben wir das ja schon der Klasse gegeben!


    Modernes TMP
    Dank C++11 (und vorher schon in boost) gibt es Abhilfe. Es gibt einen Weg, Funktionen sozusagen an- oder auszuschalten. Hierfür schauen wir in den type_traits-Header, und finden std::enable_if.

    std::enable_if macht genau das, was wir von Anfang an wollten. Es setzt ein if um - indem es eine Funktion entweder zeigt, oder sie versteckt. Im type_traits-Header finden wir noch viele weitere kleine Template-Helfer, die uns erlauben, die Bedingung zu formulieren, wann eine Funktion gezeigt oder versteckt werden soll - z.B. std::is_same, was wir benutzen können, um unseren Template-Parameter is_sorted mit sorted und unsorted vergleichen zu können.

    Unsere add()-Methode könnten wir mit std::enable_if wie folgt implementieren:
    Code (C++):
    Quelltext kopieren
    1. template <class sorted_type = is_sorted>
    2.     typename std::enable_if<std::is_same<sorted_type, sorted>::value, void>::type
    3.     add(const T& value)
    4.     {
    5.         mData.insert(value);
    6.     }
    7.  
    8.     template <class sorted_type = is_sorted>
    9.     typename std::enable_if<std::is_same<sorted_type, unsorted>::value, void>::type
    10.     add(const T& value)
    11.     {
    12.         //linear search
    13.         auto foundAt = std::find(mData.begin(), mData.end(), value);
    14.  
    15.         if(foundAt == mData.end())
    16.             mData.push_back(value);
    17.         else
    18.             *foundAt = value;
    19.     }
    Zunächst einmal muss die Methode selbst templatisiert sein - sonst können wir keine Wahl treffen. Das erste (Template-)Argument an std::enable_if ist eine Kondition, die eine zur Compile-Time konstante true oder false-Klasse erwartet - das bringt C++11 zum Glück alles von Haus aus mit. (Früher, ach, früher musste man das alles noch selbst schreiben!) Wir übergeben an dieser Stelle ein std::is_same-Objekt, welches zwei Typen vergleicht - wir vergleichen unseren Template-Parameter sorted_type (aka is_sorted) mit sorted (und in der zweiten Funktion unsorted). Der zweite Parameter wird der Rückgabewert der (aktivierten) Funktion - in unserem Falle void.

    Und schon ist alles einfacher. (Bis auf die Syntax.)

    Leider können wir mit std::enable_if nicht unseren Member mData konditional (de)aktivieren. But wait! Auch dafür bietet der type_traits-Header eine Lösung - std::conditional!
    Unser typedef für unseren Container-Typen sieht mit std::conditional aus wie folgt:

    Code (C++):
    Quelltext kopieren
    1. typedef typename std::conditional< //typedef a conditional type
    2.                         std::is_same<is_sorted, sorted>::value, //if (sorted)
    3.                             std::set<T>, //to be set
    4.                             std::vector<T> //else vector
    5.                         >::type ContainerType; //name it ContainerType
    std::conditional definiert uns einen von zwei übergebenen Typen, der abhängig von einer ebenfalls bergebenen Bedingung ist. Die Bedingung, (sorted/unsorted) haben wir mit std::is_same vorhin schon geschrieben, und die beiden Typen, unter denen wir auswählen wollen, sind std::set und std::vector.

    Und fertig. Unser gesamter Code sieht nun so aus - die traits-Klassen sind wir wieder los geworden! Keine überflüssigen Indirektionen und Member-Funktionen mehr.

    Code (C++):
    Quelltext kopieren
    1. #include <vector>
    2. #include <set>
    3. #include <algorithm>
    4. #include <type_traits>
    5.  
    6. struct sorted{};
    7. struct unsorted{};
    8.  
    9. template <typename T, typename is_sorted=unsorted>
    10. class Set
    11. {
    12. public:
    13.     typedef T value_type;
    14.  
    15.     template <class sorted_type = is_sorted>
    16.     typename std::enable_if<std::is_same<sorted_type, sorted>::value, void>::type
    17.     add(const T& value)
    18.     {
    19.         mData.insert(value);
    20.     }
    21.  
    22.     template <class sorted_type = is_sorted>
    23.     typename std::enable_if<std::is_same<sorted_type, unsorted>::value, void>::type
    24.     add(const T& value)
    25.     {
    26.         //linear search
    27.         auto foundAt = std::find(mData.begin(), mData.end(), value);
    28.  
    29.         if(foundAt == mData.end())
    30.             mData.push_back(value);
    31.         else
    32.             *foundAt = value;
    33.     }
    34.  
    35.     template <class sorted_type = is_sorted>
    36.     typename std::enable_if<std::is_same<sorted_type, sorted>::value, bool>::type
    37.     exists(const T& value) const
    38.     {
    39.         return mData.find(value) != mData.end();
    40.     }
    41.  
    42.     template <class sorted_type = is_sorted>
    43.     typename std::enable_if<std::is_same<sorted_type, unsorted>::value, bool>::type
    44.     exists(const T& value) const
    45.     {
    46.         return std::find(mData.begin(), mData.end(), value) != mData.end();
    47.     }
    48.  
    49. private:
    50.     typedef typename std::conditional< //typedef a conditional type
    51.                         std::is_same<is_sorted, sorted>::value, //if (sorted)
    52.                             std::set<T>, //to be set
    53.                             std::vector<T> //else vector
    54.                         >::type ContainerType; //name it ContainerType
    55.  
    56.     ContainerType mData;
    57. };
    Natürlich ließe sich der Code noch vereinfachen - so müssen wir z.B.nicht jedes mal std::is_same benutzen, da die Bedingung ja innerhalb der Klasse immer gleich ist. Stattdessen könnten wir das Ergebnis einmal zwischenspeichern, und wiederverwenden. Die Umsetzung bleibt dem geneigen Leser überlassen :)

    Anwendung & Nutzen
    Benutzen lässt sich das Set jetzt denkbar einfach:
    Code (C++):
    Quelltext kopieren
    1. int main()
    2. {
    3.     Set<int> myUnsortedSet;
    4.     Set<int, sorted> mySortedSet;
    5.     myUnsortedSet.add(8);
    6.     myUnsortedSet.add(8);
    7.     mySortedSet.add(15);
    8.     mySortedSet.add(15);
    9. }
    Für diesen Code werden jetzt 2 Klassen aus dem Template, was wir bereit gestellt haben, erstellt - eins für <int, unsorted>, und eins für <int, sorted>. Beide dieser Klassen haben exakt 2 Methoden und einen Member, zur Laufzeit findet keine Abfrage statt, man kann es nicht falsch benutzen. Versuche ich, ein Set<int, irgendwas> zu instantiieren, gibt es eine Fehlermeldung vom Compiler.
    Natürlich muss man sich noch einige Methoden, die z.B. über das Set iterieren, es leeren, ausgeben etc. dazudenken - diese Methoden funktionieren dank ähnlichem Interface von std::vector und std::set identisch, müssen also nur einmal geschrieben werden; das std::enable_if kann man sich sparen.

    Natürlich ist ein solches Template immer Teil eines größeren Konstrukts. Niemand würde tatsächlich eine Set-Klasse dieser Art schreiben - es wäre zu einfach, ein SortedSet und ein UnsortedSet zu schreiben, und diese dann einfach zu nutzen.

    Allerdings kann man seinen eigenen Code jetzt schlau gestalten. Erst implementieren wir unsere zehntausend Zeilen Code mit unserem Set, dann messen wir die Performance, und finden zu Beisiel heraus, dass wir relativ viel Speicher als Overhead verbrauchen, wenn kleine Objekte (int, float, char) in einem sortierten Set abgelegt werden. (Bei größeren Objekten dürfte der Overhead zu vernachlässigen sein.)

    Also schreiben wir 5 Zeilen mehr Code, und nutzen wiederum TMP, um dies für den Compiler zu formulieren.

    Code (C++):
    Quelltext kopieren
    1. template <typename T>
    2. using unsorted_set_for_small_types = typename std::conditional<sizeof(T)<=4,Set<T, unsorted>,Set<T, sorted>>::type;
    Dieses Template-Alias könnten wir an einer einzigen Stelle definieren, und dann überall im Code verwenden, wo wir nicht unbedingt ein sortiertes Set benötigen:

    Code (C++):
    Quelltext kopieren
    1. unsorted_set_for_small_types<int> myConditionalsSet;
    2. typedef unsorted_set_for_small_types<char> CharSet;
    (Natürlich können wir auch lokal den Namen beliebig typedef-en, und eben ein CharSet nutzen.)

    Hierbei ist es uns egal, ob ein sortiertes oder unsortiertes Set vorliegt, da das Interface für beide Klassen ja dasselbe ist. Auch, wenn sich heraus stellt, dass sogar Objekte von 8 Bytes noch sinnvollererweise unsortiert untergebracht werden sollten - man kann die Kondition an einer einzigen Stelle umstellen, kein weiterer Code verändert sich.
    Und die Kondition kann quasi beliebig sein. Der type_traits-Header bietet ein ganzes Arsenal von nützlichen Helfern.

    Natürlich gibt es auch - wie bei allem positivem - auch Nachteile.
    Naturgemäß müssen templates in Headern definiert werden - wer Implementationsdetails verstecken will, muss die entsprechenden Operationen in untemplatisierte Funktionen auslagern, die dann "versteckt" werden können.
    Und natürlich steigt die Kompilationszeit an. Meine eigenen Gehversuche haben bisher noch nie den Compiler merkbar beschäftigt; und man muss sich auch hin und wieder vor Augen führen, welche Massen an Code man eventuell über verschiedene Header inkludiert: Wer keine Rekursionen schreibt, wird vermutlich mit eigenen Templates nie an die Rechenleistung heran kommen, die von inkludierten (Fremd-)Headern verschlungen wird. (Aber gesagt musste es werden.)

    Also auf auf, gut template!
    Vermutlich werde ich noch 1, 2 Beiträge zu dem Thema schreiben, bis auch die letzten Klarheiten beseitigt sind. :)

Letzte Rezensionen

  1. German
    German
    5/5,
    Sehr gut erklärtes Tutorial.