Softwaredesign mit Traits und Tag Dispatching

Inhaltsverzeichnis

Tag Dispatching ermöglicht es, eine Funktion auf der Grundlage der Typeingenschaften auszuwählen. Diese Entscheidung findet zur Compiletime statt und basiert auf Traits.

Tag Dispatching basiert auf Traits. Folgerichtig möchte ich ein paar Worte über Traits schreiben.

Traits

Traits sind Klassen-Templates, die Merkmale eines generischen Typs bereitstellen. Sie können ein oder mehrere Merkmale eines Klassen-Templates extrahieren.

Du hast es vielleicht schon vermutet: Die Metafunktionen aus der type-traits-Bibliothek sind typische Beispiele für Traits in C++. Ich habe bereits ein paar Beiträge über sie geschrieben:

• Typprüfungen
• Typvergleiche
• std::is_base_of
• Korrektheit
• Optimierung
  

Bevor ich in diesem Beitrag in das Tag-Dispatching einsteige, möchte ich die Iterator-Traits vorstellen. Der folgende Codeschnipsel zeigt ihre partielle Spezialisierung für Zeiger:

template<T> 
struct iterator_traits<T*> { 
    using difference_type = std::ptrdiff_t; 
    using value_type = T; 
    using pointer = T*; 
    using reference = T&; 
    using iterator_category = std::random_access_iterator_tag; 
};

Die Iterator Kategorien bilden die folgende Hierarchie:

struct input_iterator_tag{}; 
struct output_iterator_tag{}; 
struct forward_iterator_tag: public input_iterator_tag{}; 
struct bidirectional_iterator_tag: public forward_iterator_tag{}; 
struct random_access_iterator_tag: public bidirectional_iterator_tag{}; 

Die verschiedenen Iterator-Kategorien lassen sich den Containern der Standard Template Library zuordnen.

Für die Iterator-Kategorien und ihre unterstützenden Operationen gelten die folgenden Beziehungen: Ein Iterator mit wahlfreiem Zugriff ist ein bidirektionaler Iterator, und ein bidirektionaler Iterator ist ein Forward-Iterator. Das bedeutet, dass std::array, std::vector und std::string einen Iterator mit wahlfreiem Zugriff unterstützen. Das gilt aber nicht für std::list.

Tag Dispatching

Jetzt kann ich Tag Dispatching anwenden und einen maßgeschneiderten advance_-Algorithmus implementieren, der für den verwendeten Container optimiert ist. Zunächst einmal ist std::advance bereits Bestandteil der Standard Template Library:

template< class InputIt, class Distance >
void advance( InputIt& it, Distance n );            (until C++17)

template< class InputIt, class Distance >
constexpr void advance( InputIt& it, Distance n );  (since C++17)

std::advance setzt einen gegebenen Iterator it um n Positionen weiter. Wenn n negativ ist, wird der Iterator dekrementiert. Folglich muss der Container, der den Iterator bereitstellt, in diesem Fall bidirektional sein.

Hier ist meine Implementierung von advance_:

// advance_.cpp

#include <iterator>
#include <forward_list>
#include <list>
#include <vector>
#include <iostream>

template <typename InputIterator, typename Distance>           
void advance_impl(InputIterator& i, Distance n, 
                  std::input_iterator_tag) {
    std::cout << "InputIterator used" << '\n'; 
    if (n >= 0) { while (n--) ++it; }
}

template <typename BidirectionalIterator, typename Distance>       
void advance_impl(BidirectionalIterator& i, Distance n,
                  std::bidirectional_iterator_tag) {
    std::cout << "BidirectionalIterator used" << '\n';
    if (n >= 0) 
        while (n--) ++i;
    else 
        while (n++) --i;
}

template <typename RandomAccessIterator, typename Distance>     
void advance_impl(RandomAccessIterator& i, Distance n,
                  std::random_access_iterator_tag) {
    std::cout << "RandomAccessIterator used" << '\n';
    i += n;                                                       // (5)
}

template <typename InputIterator, typename Distance>              // (4)
void advance_(InputIterator& i, Distance n) {
    typename 
      std::iterator_traits<InputIterator>::iterator_category category;
    advance_impl(i, n, category);         
}
  
int main(){
    
    std::cout << '\n';
    
    std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};         // (1)
    auto myVecIt = myVec.begin();               
    std::cout << "*myVecIt: " << *myVecIt << '\n';
    advance_(myVecIt, 5);
    std::cout << "*myVecIt: " << *myVecIt << '\n';
    
    std::cout << '\n';
    
    std::list<int> myList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};          // (2)
    auto myListIt = myList.begin();       
    std::cout << "*myListIt: " << *myListIt << '\n';
    advance_(myListIt, 5);
    std::cout << "*myListIt: " << *myListIt << '\n';
    
    std::cout << '\n';
    
    std::forward_list<int> 
      myForwardList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};                // (3)
    auto myForwardListIt = myForwardList.begin();     
    std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
    advance_(myForwardListIt, 5);
    std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
    
    std::cout << '\n';
    
}

In dem Beispiel verwende ich einen std::vector (1), eine std::list (2) und eine std::forward_list (3). Ein std::vector unterstützt einen Iterator mit wahlfreiem Zugriff, eine std::list einen bidirektionalen Iterator und eine std::forward_list einen Forward-Iterator. Der Aufruf std::iterator_traits<InputIterator>::iterator_category in der Funktion advance_ (4) bestimmt die unterstützte Iterator-Kategorie anhand des eingesetzten Iterators. Der abschließende Aufruf advance_impl(i, n, category) verwendet schließlich die am stärksten spezialisierte Überladung der Implementierungsfunktion advance_impl.

Um diese Abbildung zu visualisieren, habe ich den Implementierungsfunktionen advance_impl eine kurze Nachricht hinzugefügt.

Was sind die Vorteile einer so fein abgestimmten advance-Implementierung?

• Typsicherheit: Der Compiler entscheidet, welche Version von advance _impl verwendet wird. Folglich lässt sich eine Implementierung, die einen bidirektionalen Iterator erfordert, nicht mit einem Forward-Iterator aufrufen. Rückwärts iterieren mit einem Forward-Iterator ist undefiniertes Verhalten.
• Performanz: Einen Forward-Iterator oder einen bidirektionalen Iterator n Positionen weiter zu setzen, erfordert n Inkrementoperationen. Seine Komplexität ist daher linear. Diese Beobachtung gilt nicht für einen Iterator mit wahlfreiem Zugriff: Eine Zeigerarithmetik wie i += n (5) ist eine konstante Operation.

Wie geht's weiter?

In meinem nächsten Artikel verbinde ich den dynamischen Polymorphismus (Objektorientierung) mit dem statischen Polymorphismus (Templates) und führe eine ziemlich anspruchsvolle Technik ein: type erasure.

Die Zukunft von Modernes C++

Der folgende Artikel über type erasure wird vorerst mein letzter Artikel über Templates sein. Wer alle vorherigen Artikel lesen möchte, kann mein Inhaltsverzeichnis oder meine Kategorie Templates nutzen. Danach schreibe ich weitere Artikel zu C++20 und werde einen Blick in die Zukunft von C++23 werfen. Wer eine interessante Beitragsidee hast, sendet mir bitte eine E-Mail: Rainer.Grimm@modernescpp.de. ()