Appel récursif d'une fonction modèle (C++)

Question

Je suis en train d'écrire une classe de matrice mathématique pour me familiariser avec les nouvelles fonctionnalités de c++11, la déclaration de base est la suivante :

template <typename Type, int kNumRows, int kNumCols>
class Matrix { ... };

La classe dispose d'une fonction membre qui renvoie l'un de ses mineurs (qui est ensuite utilisé pour calculer le déterminant des matrices NxN).

Matrix<Type, kNumRows - 1, kNumCols - 1> minor(const int row, const int col) {
  static_assert(kNumRows > 2, "");
  static_assert(kNumCols > 2, "");

  ...
}

J'ai ensuite créé une fonction non membre pour calculer le déterminant de n'importe quelle matrice carrée :

template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
  switch (kSize) {
  case 2:
    return 0; // For now unimportant
  case 3:
    // Recursively call the determinant function on a minor matrix
    return determinant(matrix.minor(0, 0));
  }
  ...
}

Dans main(), je crée une matrice 3x3 et j'appelle determinant sur celui-ci. Il ne sera pas compilé. Le compilateur passe effectivement au cas 3, en créant une matrice mineure et en appelant determinant sur celui-ci. Il entre ensuite dans case 3 à nouveau, ce qui entraîne un static_assert en essayant de créer un mineur 1x1.

La question est simple : ai-je raté quelque chose ? Est-ce que le fait d'appeler une fonction template comme celle-ci de manière récursive n'est tout simplement pas autorisé ? S'agit-il d'une erreur du compilateur (j'en doute) ?

Par souci d'exhaustivité : J'utilise Clang++.

Answer 1

Le compilateur génère tous les chemins de code, même s'ils ne sont pas tous visités pendant l'exécution (et peuvent même être supprimés lors d'une étape d'optimisation). En conséquence, determinant<Type, kSize - 1, kSize - 1> est toujours instancié, même pour les kSize < 3.

Vous devez spécialiser partiellement votre fonction pour éviter cela, vous devez surcharger votre fonction determinant fonctionner de manière appropriée :

template <typename Type>
Type determinant(const Matrix<Type, 2, 2>& matrix) {
  ...
}

Cela fait de la switch dans votre fonction est d'ailleurs redondante.

Answer 2

Les modèles déterminent ce qu'il faut faire au moment de la compilation, mais une switch détermine ce qu'il faut faire au moment de l'exécution. Le compilateur génère du code, ou au moins vérifie la validité, pour tous les cas de commutation, même si le cas correct est "évident" au moment de la compilation.

Au lieu d'utiliser switch essayez de surcharger le déterminant :

template <typename Type>
Type determinant(const Matrix<Type, 1, 1>& matrix) {
    return matrix(0,0);
}

template <typename Type>
Type determinant(const Matrix<Type, 2, 2>& matrix) {
    return 0; // (incorrect math)
}

template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
    return determinant(matrix.minor(0,0)); // (incorrect math)
}

Answer 3

Vous devez effectuer le changement au moment de la compilation en utilisant la spécialisation des modèles :

template <typename Type, int kSize>
struct Determinate {
    Type operator()(const Matrix<Type, kSize, kSize>& matrix) const {
        // Recursively call the determinant function on a minor matrix
        return Determinate<Type, kSize-1>{}(matrix.minor(0, 0));
    }
};
template <typename Type>
struct Determinate<Type, 2> {
    Type operator()(const Matrix<Type, kSize, kSize>& matrix) const {
        return 0; // For now unimportant
    }
};
template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
    return Determinate<Type, kSize>{}(matrix);
}