Statischer Polymorphismus

Bislang waren die Matrizen mit dem zugehörigen Speicher fest verbunden. Es ist vielfach aber auch sinnvoll, eine Matrix als Teil einer anderen Matrix zu betrachten wie z.B. bei Blockmatrizen. Diese Matrizen tragen keine Verantwortung für das Belegen oder Freigeben des zugehörigen Speichers, sie dienen nur als Betrachter eines Ausschnittes.

In der Informatik gibt es hier das MVC-Pattern, wobei MVC für model, viewer und controller steht. Hier wäre die bisherige Matrix-Klasse das model und der Betrachter eines Ausschnitts ein viewer und, falls dieser auch Änderungen zulässt, ein controller.

So könnte eine entsprechende Klasse aussehen. In ihrem Konstruktur erhält sie neben der Dimensionierung einen Zeiger auf das erste Element und die üblichen Inkremente:

template<typename T>
struct MatrixView {
   const std::size_t m; /* number of rows */
   const std::size_t n; /* number of columns */
   const std::size_t incRow;
   const std::size_t incCol;
   T* data;

   MatrixView(std::size_t m, std::size_t n,
            T* data,
            std::size_t incRow, std::size_t incCol) :
         m(m), n(n),
         data(data),
         incRow(incRow), incCol(incCol) {
   }

   const T& operator()(std::size_t i, std::size_t j) const {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }

   T& operator()(std::size_t i, std::size_t j) {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }
};

Im folgenden Beispiel entspricht B dem folgenden Ausschnitt aus A:

\[\left( \begin{array}{c c c} a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,2} & a_{4,3} & a_{4,4} \end{array}\right)\]

int main() {
   Matrix<double> A(7, 8, StorageOrder::ColMajor);
   init_matrix(A); std::printf("A =\n"); print_matrix(A);
   MatrixView<double> B(3, 3, &A(2, 2), A.incRow, A.incCol);
   std::printf("B =\n"); print_matrix(B);
}

Leider funktioniert die bisherige print_matrix-Funktion nicht für die neu eingeführte MatrixView-Klasse:

$shell> g++ -Wall -std=gnu++11 -o matrix_class12 matrix_class12.cpp
matrix_class12.cpp: In function 'int main()':
matrix_class12.cpp:89:40: error: no matching function for call to 'print_matrix(MatrixView&)'
    std::printf("B =\n"); print_matrix(B);
                                        ^
matrix_class12.cpp:74:6: note: candidate: template void print_matrix(const Matrix&)
 void print_matrix(const Matrix& A) {
      ^
matrix_class12.cpp:74:6: note:   template argument deduction/substitution failed:
matrix_class12.cpp:89:40: note:   'MatrixView' is not derived from 'const Matrix'
    std::printf("B =\n"); print_matrix(B);
                                        ^

Das Problem ist, dass die print_matrix-Funktion darauf besteht, dass ihr Matrix-Parameter eine Instantiierung einer Matrix-Klasse ist. Da C++ erst jedoch beim Einsetzen der Typparameter bei einer Instantiierung überprüft, ob das Resultat korrekt ist, können wir den Parameter allgemeiner formulieren:

template<typename Matrix>
void print_matrix(const Matrix& A) {
   for (std::size_t i = 0; i < A.m; ++i) {
      std::printf("  ");
      for (std::size_t j = 0; j < A.n; ++j) {
         /* be careful here, printf is not polymorph */
         std::printf(" %4.1lf", (double) A(i, j));
      }
      std::printf("\n");
   }
}

Diese Template-Funktion akzeptiert jetzt zunächst einen beliebigen Datentyp für Matrix. Es wird nur erwartet, dass der resultierende Programmtext nach dem Einsetzen korrekt ist. Konkret bedeutet das hier, dass

A.m und A.n existieren und mit std::size_t vergleichbar sind und
A(i, j) zulässig ist, d.h. ein entsprechender Operator muss existieren und etwas zurückliefern, das in double konvertierbar ist.

Dies sind die sogenannten Template-Abhängigkeiten. Bislang gibt es in C++ kein Sprachmittel, die geforderten Eigenschaften eines Typparameters in allgemeiner Form zu beschreiben, wenn von einer Konkretisierung des Typs (wie zuvor auf Matrix<T>) abgesehen wird.

Entsprechend ist print_matrix polymorph, da es für nicht für einen konkreten Datentyp verwendet werden kann, sondern für alle Datentypen, die die Template-Abhängigkeiten erfüllen. Da bereits der Übersetzer zur Übersetzzeit die richtige Ausprägung erzeugt und auswählt, wird hier vom statischen Polymorphismus gesprochen.

Sei folgendes Testprogramm gegeben, das auch ein Element von B verändert:

int main() {
   Matrix<double> A(7, 8, StorageOrder::ColMajor);
   MatrixView<double> B(3, 3, &A(2, 2), A.incRow, A.incCol);

   init_matrix(A);
   B(1, 1) = 0;
   std::printf("A =\n"); print_matrix(A);
   std::printf("B =\n"); print_matrix(B);
}

Dann sieht das Resultat so aus:

$shell> g++ -Wall -std=gnu++11 -o matrix_class13 matrix_class13.cpp
$shell> matrix_class13
A =
    1.0  9.0 17.0 25.0 33.0 41.0 49.0 57.0
    2.0 10.0 18.0 26.0 34.0 42.0 50.0 58.0
    3.0 11.0 19.0 27.0 35.0 43.0 51.0 59.0
    4.0 12.0 20.0  0.0 36.0 44.0 52.0 60.0
    5.0 13.0 21.0 29.0 37.0 45.0 53.0 61.0
    6.0 14.0 22.0 30.0 38.0 46.0 54.0 62.0
    7.0 15.0 23.0 31.0 39.0 47.0 55.0 63.0
B =
   19.0 27.0 35.0
   20.0  0.0 36.0
   21.0 29.0 37.0

Aufgaben

Was passiert, wenn bei print_matrix statt eine der Matrix-Variablen ein völlig anderer Datentyp angegeben wird, etwa eine 1?
Kann ein MatrixView-Klasse sich auf eine andere MatrixView-Klasse beziehen?
Passen Sie die init_matrix-Funktion so an, dass sie ebenfalls für eine MatrixView-Instanz funktioniert.

Da zu einer MatrixView-Instanz nur wenige Komponenten gehören, lohnt es sich, einen Kopierkonstruktor anzubieten:

        MatrixView(const MatrixView& other) :
           /* ... */ {
           /* ... */
        }
        

Sie können das testen, indem Sie eine weitere MatrixView-Klasse entsprechend initialisieren:

        MatrixView<double> C = B;
        std::printf("C =\n"); print_matrix(C);
        

Schreiben Sie eine Template-Funktion create_view, die eine beliebige Matrix erhält (also Matrix oder MatrixView) und einen Ausschnitt als MatrixView zurückliefert. Als Parameter sind die Indizes für das erste Element und die Zahl der Zeilen und Spalten anzugeben: So könnte ein Aufruf aussehen:
```
        MatrixView<double> D(create_view(A, 1, 4, 3, 2));
        std::printf("D =\n"); print_matrix(D);
        
```
Wenn Sie die Deklaration für create_view hinschreiben möchten, erhalten Sie aber das Problem, den Elementtyp benennen zu müssen, obwohl Sie nur den Matrix-Typ als Template-Parameter haben. Hierfür gibt es mehrere Lösungsmöglichkeiten in C++. Der klassische Weg führt über hilfreiche Typdeklarationen innerhalb von struct Matrix und struct MatrixView:
```
        template<typename T>
        struct /* Matrix or MatrixView */ {
           /* ... */
           typedef T Element;
        };
        
```
Danach kann mit Matrix::Element auf den Elementtyp zurückgegriffen werden für beliebige Template-Parameter Matrix, die sich an diese Konvention halten. Es gibt da nur noch ein kleines Problem. Da die Grammatik von C++ mehrere Konflikte hat, muss die syntaktische Analyse bei C++ immer wissen, ob es sich bei einem Namen um einen Typ oder um etwas anderes handelt. Bei der syntaktischen Analyse von Templates ist aber der Template-Parameter noch nicht bekannt, so dass der Übersetzer nicht erraten kann, dass es sich bei Matrix::Element um einen Typen handelt. Deswegen muss der Übersetzer hier unterstützt werden, indem davor das Schlüsselwort typename verwendet wird, also typename Matrix::Element verwendet wird.

Zusätzlich wäre noch ein Aufruf von assert sinnvoll, um sicherzugehen, dass die Teilmatrix sich auf einen Ausschnitt der Ausgangsmatrix beschränkt.
Welche Konstruktoren werden an welcher Stelle aufgerufen? Gehen Sie der Sache auf den Grund, indem Sie temporär die Konstruktoren mit Kontrollausgaben versehen.

Vorlage

session9/matrix_class13.cpp

#include <cstddef> /* needed for std::size_t */
#include <cstdio> /* needed for printf */
#include <cassert> /* needed for assert */

enum class StorageOrder {ColMajor, RowMajor};

template<typename T>
struct Matrix {
   const std::size_t m; /* number of rows */
   const std::size_t n; /* number of columns */
   const std::size_t incRow;
   const std::size_t incCol;
   T* data;

   Matrix(std::size_t m, std::size_t n, StorageOrder order) :
         m(m), n(n),
         incRow(order == StorageOrder::ColMajor? 1: n),
         incCol(order == StorageOrder::RowMajor? 1: m),
         data(new T[m*n]) {
   }

   ~Matrix() {
      delete[] data;
   }

   const T& operator()(std::size_t i, std::size_t j) const {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }

   T& operator()(std::size_t i, std::size_t j) {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }
};

template<typename T>
struct MatrixView {
   const std::size_t m; /* number of rows */
   const std::size_t n; /* number of columns */
   const std::size_t incRow;
   const std::size_t incCol;
   T* data;

   MatrixView(std::size_t m, std::size_t n,
            T* data,
            std::size_t incRow, std::size_t incCol) :
         m(m), n(n),
         incRow(incRow), incCol(incCol),
         data(data) {
   }

   const T& operator()(std::size_t i, std::size_t j) const {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }

   T& operator()(std::size_t i, std::size_t j) {
      assert(i < m && j < n);
      return data[i*incRow + j*incCol];
   }
};

template<typename T>
void init_matrix(Matrix<T>& A) {
   for (std::size_t i = 0; i < A.m; ++i) {
      for (std::size_t j = 0; j < A.n; ++j) {
         A(i, j) = j * A.n + i + 1;
      }
   }
}

template<typename Matrix>
void print_matrix(const Matrix& A) {
   for (std::size_t i = 0; i < A.m; ++i) {
      std::printf("  ");
      for (std::size_t j = 0; j < A.n; ++j) {
         /* be careful here, printf is not polymorph */
         std::printf(" %4.1lf", (double) A(i, j));
      }
      std::printf("\n");
   }
}

int main() {
   Matrix<double> A(7, 8, StorageOrder::ColMajor);
   MatrixView<double> B(3, 3, &A(2, 2), A.incRow, A.incCol);

   init_matrix(A);
   B(1, 1) = 0;
   std::printf("A =\n"); print_matrix(A);
   std::printf("B =\n"); print_matrix(B);
}