Idiome in der Softwareentwicklung: Das Iterator-Protokoll

Soll ein benutzerdefinierter Datentyp MyType in einer Range-based for-Schleife verwendet werden, muss MyType das Iterator Protocol implementieren.

Wie muss ein benutzerdefinierter Datentyp beschaffen sein, damit er in einer Range-based for-Schleife verwendet werden kann? Dieser Frage gehe ich im Folgenden auf den Grund.

Anforderungen an eine Range-based for-Schleife

Ich möchte mit einem einfachen Experiment beginnen und ein std::array in C++ Insights verwenden. Hier ist ein simples Beispiel:

// iteratorProtocol.cpp

#include <array>

int main() {
   
    std::array<int, 5> myArr{1, 2, 3, 4, 5};
    for (auto a: myArr) a;
  
}

C++ Insights erzeugt daraus den folgenden Code:

#include <array>

int main()
{
  std::array<int, 5> myArr = {{1, 2, 3, 4, 5}};
  {
    std::array<int, 5> & __range1 = myArr;
    int * __begin1 = __range1.begin();
    int * __end1 = __range1.end();
    for(; __begin1 != __end1; ++__begin1) {
      int a = *__begin1;
      a;
    }
    
  }
  return 0;
}

Allgemeiner formuliert: Soll eine Range-based for-Schleife verwendet werden (for(range_declaration : range_expression)), erstellt der Compiler den folgenden Code:

{
  auto && __range = range_expression ;
  auto __begin = begin_expr;      
  auto __end = end_expr;          
  for (;__begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement
  }
}

• begin_expr und end_expr: geben ein Iterator-Objekt zurück
• Iterator-Objekt:
• operator++: Erhöht den Iterator
• operator*: Dereferenzierung des Iterators und Zugriff auf das aktuelle Element
• operator!=: Vergleichen des Iterators mit einem anderen Iterator

begin_expr und end_expr rufen die entscheidenden Funktionen begin und end in der range_expression auf. begin und end können entweder Mitgliedsfunktionen oder freie Funktionen der range_expression sein.

Nun wende ich die Theorie an und erstelle einen Zahlengenerator.

Ein Generator

Die erste Implementierung unterstützt das Iterator-Protokoll.

Das Iterator-Protokoll

Die folgende Klasse Generator unterstützt das elementare Iterator-Protokoll.

// iterator.cpp

#include <iostream>

class Generator {
    int begin_{};
    int end_{};

public:
    Generator(int begin, int end) : begin_{begin}, end_{end} {}

    class Iterator {
        int value_{};
    public:
        explicit Iterator(int pos) : value_{pos} {}

        int operator*() const { return value_; }           // (3)

        Iterator& operator++() {                           // (4)
            ++value_;
            return *this;
        }

        bool operator!=(const Iterator& other) const {      // (5)
            return value_ != other.value_;
        }
    };

    Iterator begin() const { return Iterator{begin_}; }     // (1)
    Iterator end() const { return Iterator{end_}; }         // (2)
};

int main() {

   std::cout << '\n';
    
   Generator gen{100, 110};
   for (auto v : gen) std::cout << v << " ";

   std::cout << "\n\n";

}

Die Klasse Generator hat Mitgliedsfunktionen begin und end (Zeilen 1 und 2), die Iterator-Objekte zurückgeben, die mit begin_ und end_ initialisiert sind. begin_ und end_ stehen für den Bereich der erzeugten Zahlen. Lasse mich die innere Klasse Iterator analysieren, die die erzeugten Zahlen kontrolliert.

• operator* gibt den aktuellen Wert zurück
• operator++ erhöht den aktuellen Wert
• operator!= vergleicht den aktuellen Wert mit der end_-Marke.

Damit ergibt sich folgende Ausgabe des Programms:

Ich möchte den Iterator, der von begin() und end() zurückgegeben wird, verallgemeinern und ihn zu einem Forward-Iterator machen. Danach kann die Klasse Generator in den meisten Algorithmen der Standard Template Library verwendet werden. Zum Beispiel unterstützen die assoziativen Container einen Forward-Iterator.

Ein Forward-Iterator

Der folgende verbesserte Generator besitzt eine innere Klasse Iterator, die ein Forward-Iterator ist.

// forwardIterator.cpp

#include <iostream>
#include <numeric>

class Generator {
    int begin_{};
    int end_{};

 public:
    Generator(int begin, int end) : begin_{begin}, end_{end} {}

    class Iterator {
        using iterator_category = std::forward_iterator_tag;    // (1)
        using difference_type   = std::ptrdiff_t;
        using value_type        = int;
        using pointer           = int*;
        using reference         = int&;
        int value_{};
     public:
        explicit Iterator(int pos) : value_{pos} {}

        value_type operator*() const { return value_; }
        pointer operator->() { return &value_; }                // (2)         

        Iterator& operator++() {                           
            ++value_;
            return *this;
        }
        Iterator operator++(int) {                              // (3)
            Iterator tmp = *this; 
            ++(*this); 
            return tmp; 
        }
                                                                // (4)
        friend bool operator==(const Iterator& fir, const Iterator& sec) {      
            return fir.value_ == sec.value_;
        }
        friend bool operator!=(const Iterator& fir, const Iterator& sec) {      
            return fir.value_ != sec.value_;
        }
    };

    Iterator begin() const { return Iterator{begin_}; }     
    Iterator end() const { return Iterator{end_}; }         
};

int main() {

    std::cout << '\n';
    
    Generator gen{1, 11};
    for (auto v : gen) std::cout << v << " ";                  // (5)

    std::cout << "\n\n";
                                                               // (6)
    std::cout << "sum:  " << std::accumulate(std::begin(gen), std::end(gen), 0);

    std::cout << "\n\n";
                                                                // (7)
    std::cout << "prod: " << std::accumulate(gen.begin(), gen.end(), 1, 
                                             [](int fir, int sec){ return fir * sec; });

    std::cout << "\n\n";

}

Zunächst braucht Iterator ein paar Aliase, die ich in den folgenden Deklarationen der Mitgliedsfunktionen verwende. Zusätzlich zur vorherigen Iterator-Implementierung im Programm iterator.cpp unterstützt der aktuelle Iterator die folgenden Mitgliedsfunktionen: den Pfeil-Operator (operator-> in Zeile 2), den Post-Inkrement-Operator (operator++(int) in Zeile 3) und den Gleichheitsoperator (operator== in Zeile 4).

Jetzt lässt sich der verbesserte Generator in einer Range-based for-Schleife (Zeile 5) verwenden, aber auch im STL-Algorithmus std::accumulate. Der Code in Zeile 6 berechnet die Summe aller Zahlen von 1 bis 10; in Zeile 7 folgt eine ähnliche Aufgabe: hier wird eine Zahl von 1 bis 11 multipliziert. Im ersten Fall wähle ich das neutrale Element 0 für die Summierung, im zweiten Fall das neutrale Element 1 für die Multiplikation.

Es gibt einen feinen Unterschied zwischen dem ersten und dem zweiten Aufruf von std::accumulate. Der erste Aufruf verwendet die Nicht-Mitgliedsfunktionen std::begin und std::end des Generators: std::accumulate(std::begin(gen), std::end(gen), 0), aber der zweite Aufruf verwendet direkt die Mitgliedsfunktionen begin() und end() des Generators, die ich implementiert habe.

Damit ergibt sich nun folgende Ausgabe des Programms:

Wie geht’s weiter?

In meinem nächsten Artikel werde ich den kovarianten Rückgabetyp vorstellen. Der kovariante Rückgabetyp einer Mitgliedsfunktion ermöglicht es einer übergeordneten Mitgliedsfunktion, einen engeren Typ zurückzugeben. Das ist besonders nützlich, wenn das Entwurfsmuster Prototype implementiert werden soll. (map)