递归模板函数内的无限循环

Question

我正在为一个大学项目编写自己的库，其中包含模板 classes：向量和矩阵。除了这些模板classes，还有向量和矩阵的相关模板函数。教授明确告诉我们，将矩阵定义为一维数组，其中元素按列排序（效率/优化的原因）。 “矩阵”模板 class 有 3 个模板参数：矩阵允许的数据类型、行数、列数。

template <class T, unsigned int M, unsigned int N>
class Matrix

话虽如此，我立即进入问题所在。我正在编写一个函数来计算任何维度 > 4 的矩阵的行列式，使用列的拉普拉斯规则（使用第一列）。我还编写了一个用于二维矩阵的函数（称为 D2MatrixDet）和一个用于三维矩阵的函数（称为 D3MatrixDet），经过测试和工作：

template <class T>
double D2MatrixDet(const Matrix<T, 2, 2>& _m)

template <class T>
double D3MatrixDet(const Matrix<T, 3, 3>& _m)

我要写的模板函数有两个模板参数：输入矩阵的数据类型，矩阵的维数（因为行列式是为方阵计算的，所以只需要一个维数即可）。它是一个递归函数；变量“结果”是在每一步将行列式保存在内存中的变量。下面是我写的代码。

template <class T, unsigned int D>
void DNMatrixDet(Matrix<T, D, D> _m, double result) //LaPlace Rule respect to the first column
{
    const unsigned int new_D = D - 1;
    Matrix<T, new_D, new_D> temp;

    if (D > 3)
    {
        for (unsigned int i = 0; i < _m.row; ++i)
        //Indicate the element to multiply
        {
            for (unsigned int j = _m.row, l = 0; j < _m.row * _m.column && l < pow(new_D, 2); ++j) 
            //Manage the element to be inserted in temp
            {
                bool invalid_row = false;

                for (unsigned int k = 1; k < _m.row && invalid_row == false; ++k) //Slide over row
                {
                    if (j == (i + k * _m.row))
                    {
                        invalid_row = true;
                    }
                }

                if (invalid_row == false)
                {
                    temp.components[l] = _m.components[j];
                    ++l;
                }
            }

            DNMatrixDet(temp, result);
            result += pow((-1), i) * _m.components[i] * result;
        }
    }
    else if (D == 3)
    {
        result += D3MatrixDet(_m);
    }
}

主要是，我使用 5 x 5 矩阵测试函数。当我尝试编译时，出现了几个错误，所有错误都非常相似，并且与矩阵的大小有关，矩阵的大小每一步都减一。这是当初始矩阵大小为 5 时（LA 是库的名称，Test.cpp 是包含 main 的文件）：

LA.h: In instantiation of 'void LA::DNMatrixDet(LA::Matrix<T, M, M>, double) [with T = double; 
unsigned int D = 5]':
Test.cpp:437:33:   required from here
LA.h:668:34: error: no matching function for call to 'D3MatrixDet(LA::Matrix<double, 5, 5>&)'
             result += D3MatrixDet(_m);
                       ~~~~~~~~~~~^~~~
In file included from Test.cpp:1:
LA.h:619:12: note: candidate: 'template<class T> double LA::D3MatrixDet(const LA::Matrix<T, 3, 3>&)'
     double D3MatrixDet(const Matrix<T, 3, 3>& _m)
            ^~~~~~~~~~~
LA.h:619:12: note:   template argument deduction/substitution failed:
In file included from Test.cpp:1:
LA.h:668:34: note:   template argument '5' does not match '3'
             result += D3MatrixDet(_m);
                       ~~~~~~~~~~~^~~~

这是当尺寸变成4时：

LA.h: In instantiation of 'void LA::DNMatrixDet(LA::Matrix<T, M, M>, double) [with T = double; 
unsigned int D = 4]':
LA.h:662:28:   required from 'void LA::DNMatrixDet(LA::Matrix<T, M, M>, double) [with T = double; 
unsigned int D = 5]'
Test.cpp:437:33:   required from here
LA.h:668:34: error: no matching function for call to 'D3MatrixDet(LA::Matrix<double, 4, 4>&)'
In file included from Test.cpp:1:
LA.h:619:12: note: candidate: 'template<class T> double LA::D3MatrixDet(const LA::Matrix<T, 3, 3>&)'
     double D3MatrixDet(const Matrix<T, 3, 3>& _m)
            ^~~~~~~~~~~
LA.h:619:12: note:   template argument deduction/substitution failed:
In file included from Test.cpp:1:
LA.h:668:34: note:   template argument '4' does not match '3'
             result += D3MatrixDet(_m);
                       ~~~~~~~~~~~^~~~

等等。它一直下降，直到从 4294967295 开始（我发现这是 32 位“unsigned int”的上限）并继续下降，直到达到模板实例的最大数量（= 900）。

在每次迭代中，编译器总是检查用于计算a 3 x 3 的行列式的函数，即使该函数仅在输入矩阵为a 3 x 3 时执行。那么它为什么要检查一些东西理论上永远不会发生？

我仔细检查了我写的东西的数学逻辑好几次，甚至在写在纸上的矩阵的帮助下，慢慢地执行了第一步。我相信并希望它是正确的。我很确定问题与使用模板和递归函数有关。

对于这个很长的问题，我深表歉意，我试图以最好的方式解释它。我希望我已经很好地解释了问题。

编辑：通过在 DNMatrixDet 函数的开头定义“if constexpr”解决了问题。编译成功。我只需要修复算法，但这超出了 post 的范围。以下是做出更改的代表：

template <class T, unsigned int M, unsigned int N>
class Matrix
{
    public:

    T components[M * N];
    unsigned int row = M;
    unsigned int column = N;

    Matrix()
    {
        for (unsigned int i = 0; i < M * N; ++i)
        {
            components[i] = 1;
        }
    }
    Matrix(T* _c)
    {
        for (unsigned int i = 0; i < M * N; ++i, ++_c)
        {
            components[i] = *_c;
        }
    }
    friend std::ostream& operator<<(std::ostream& output, const Matrix& _m)
    {
        output << _m.row << " x " << _m.column << " matrix:" << std::endl;

        for (unsigned int i = 0; i < _m.row; ++i)
        {
            for (unsigned int j = 0; j < _m.column; ++j)
            {
                if (j == _m.column -1)
                {
                    output << _m.components[i + j*_m.row];
                }
                else
                {
                    output << _m.components[i + j*_m.row] << "\t";
                }
            }

            output << std::endl;
        }

        return output;
    }
};
template <class T>
double D3MatrixDet(const Matrix<T, 3, 3>& _m)
{
    double result = _m.components[0] * _m.components[4] * _m.components[8] + 
                    _m.components[3] * _m.components[7] * _m.components[2] +
                    _m.components[6] * _m.components[1] * _m.components[5] -
                    (_m.components[6] * _m.components[4] * _m.components[2] +
                     _m.components[3] * _m.components[1] * _m.components[8] +
                     _m.components[0] * _m.components[7] * _m.components[5]);

    return result;
}
template <class T, unsigned int D>
void DNMatrixDet(Matrix<T, D, D> _m, double result)
{
    Matrix<T, D - 1, D - 1> temp;

    if constexpr (D > 3)
    {
        for (unsigned int i = 0; i < D; ++i)
        {
            for (unsigned int j = D, l = 0; j < D * D && l < (D - 1) * (D - 1); ++j)
            {
                bool invalid_row = false;

                for (unsigned int k = 1; k < D && invalid_row == false; ++k)
                {
                    if (j == (i + k * D))
                    {
                        invalid_row = true;
                    }
                }

                if (invalid_row == false)
                {
                    temp.components[l] = _m.components[j];
                    ++l;
                }
            }

            DNMatrixDet(temp, result);
            result += i & 1 ? -1 : 1 * _m.components[i] * result;
        }
    }
    else if (D == 3)
    {
        result += D3MatrixDet(_m);
    }
}

int main()
{
    double m_start[25] = {4, 9, 3, 20, 7, 10, 9, 50, 81, 7, 20, 1, 36, 98, 4, 20, 1, 8, 5, 93, 47, 21, 49, 36, 92};
    Matrix<double, 5, 5> m = Matrix<double, 5, 5> (m_start);
    double m_det = 0;
    DNMatrixDet(m, m_det);
    std::cout << "m is " << m << std::endl;
    std::cout << "Det of m is " << m_det << std::endl;

    return 0;
}

Answer 1

当您将类型 Matrix<T, 5, 5> 作为参数 _m 传递时，尾随的 else 分支包含代码 result += D3MatrixDet(_m);。编译器仍将尝试编译它并注意到它找不到匹配的构造函数。

由于我们在 compile-time 处知道是否采用此分支，因此我们可以使用 if constexpr 来指示编译器。由于我们在一个模板中，如果它被丢弃，编译器将不再检查这个分支。

所以让我们把if (D > 3)改成if constexpr (D > 3)。

递归模板函数内的无限循环

Infinite loop inside recursive template function

c++

recursion

templates

matrix

linear-algebra