c++ - 递归模板函数在初始化时导致负数组大小

Question

我正在研究一个支持各种矩阵数学运算的矩阵类。 Matrix 类具有三个模板参数:

template<typename T, int rows, int columns>
class Matrix
{
   ...
};

这工作正常。然而，由于许多操作(例如反转矩阵和取其行列式)仅适用于方阵(其中行 == 列)，我选择让这些函数不是成员函数来控制模板参数，并且只允许对方阵进行这些操作矩阵:

template<typename T, int rc>
const Matrix<T, rc, rc> inverse (const Matrix<T, rc, rc>& src)
{
    ...
}

我有几个以这种方式运行的函数。

现在，我收到的错误消息非常复杂，因为模板的使用将运行时堆栈跟踪变成了编译时堆栈跟踪。这是我认为正在发生的事情:

• 我的矩阵类以三种方式存储其数据:一个二维指针数组、一个一维行数组和一个一维列数组(行和列是在矩阵中声明的内部类，函数和函数作为包装器对于一维指针数组)。所有这些指针都指向 Matrix 数据。这允许对整个行和列进行操作。

• 我遇到的错误来自这些数组的声明，以及用于初始化行和列的构造函数中的一些其他临时数组。错误信息是:

  [错误] 数组大小为负。

• 堆栈跟踪非常大，但它多次通过函数 subMatrix。其中许多函数以递归的迂回形式相互调用。

• subMatrix 获取一个具有 m 行和 n 列的矩阵，并返回一个具有 m-1< 的新矩阵 行和 n-1 列(删除一行和一列以创建子矩阵)。

• 我已确保在我的代码中绝不会在小于 2 x 2 的矩阵上调用此函数，但我怀疑编译器未检测到这一点。

• 另一个函数 determinant 计算方阵的行列式。此函数对于大于 2 x 2 的矩阵是递归的。在此函数的递归部分，它调用 subMatrix，创建一个较小的矩阵，直到矩阵达到 2 x 2 的大小。

• 我怀疑我的问题是由于编译器在 determinant 中看到递归并推断 subMatrix 在逐渐变小的矩阵上调用并不断推断直到达到一定大小的 -1，这会在声明新 = 时导致错误，较小的矩阵行和列(即使永远不会执行此代码)。

假设我已经准确分析了情况，我完全不知道如何解决这个问题。

这是我的代码的相关部分:

//matrix.h
template <typename T, int rows, int columns>

class Matrix
{
public:
    class Column;

    class Row;

private:

    T* m_data[rows][columns];  //errors on these lines.
    Row m_rows[rows];
    Column m_columns[columns];

//    ... much more in class

}

//matrix.cpp

template<typename T, int rows, int columns>
const Matrix<T, rows - 1, columns - 1> Matrix<T, rows, columns>::subMatrix(int row, int column) const
{
    Matrix<T, rows - 1, columns - 1> result;

    if (row > rows || column > columns)
    {
        std::cout << "death: bad bounds\n";
        return result;
    }

    for (int m = 1, mr = 1; m <= rows; m ++)
    {
        if (m == row)
        {
            continue;
        }

        for (int n = 1, nr = 1; n <= columns; n ++)
        {
            if (n == column)
            {
                continue;
            }

            result.at(mr, nr) = *(m_data[m - 1][n - 1]);

            nr ++;
        }

        mr ++;
    }

    return result;
}



template<typename T, int rc>
T minor(const Matrix<T, rc, rc>& src, int m, int n)
{
    return determinant(src.subMatrix(m, n));
}


template<typename T, int rc>
T cofactor(const Matrix<T, rc, rc>& src, int m, int n)
{
    return pow(-1, m + n) * minor(src, m, n);
}



template<typename T, int rc>
T determinant(const Matrix<T, rc, rc>& src)
{
    T det;

    if (rc == 2)
    {
        det = (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1));
        return det;
    }

    T temp;

    for (int n = 1; n <= rc; n ++)
    {
        temp = src.get(1, n) * cofactor(src, 1, n);
    }

    return det;
}

一切从这里开始:

int main(void)
{
    auto m1 = Matrix<int, 3, 3>().map(

     //lambda to fill the matrix with increasing values
     [](int,int,int) { static int n = 0; return ++n; }
    ); 

    int m2 = determinant(m1); //trace leads back to here

    std::cout << m1 << '\n' << m2;

    return 0;
}

这是完整的“堆栈跟踪”。不过，我怀疑这是否会有帮助。

C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   [ skipping 2 instantiation contexts ]

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Row':
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17:   required from 'class Matrix<int, -1, -1>'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here

C:\Users\noah dove\Documents\Devcpp\matrix.h:105:20: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   [ skipping 2 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Column':
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26:   required from 'class Matrix<int, -1, -1>'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:134:17: error: size of array is negative
In file included from C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:1:0:
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(T) [with T = int; int rows = -1; int columns = -1]':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:365:35:   required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:11:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:12:28: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(const Matrix<T, rows, columns>&) [with T = int; int rows = -1; int columns = -1; Matrix<T, rows, columns> = Matrix<int, -1, -1>]':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:370:10:   required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:38:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:39:28: error: size of array is negative

如果有人能在这件事上提供任何帮助，我将不胜感激。

Answer 1

rc == 2 的特殊情况不应该是代码中的运行时检查 - 它应该是部分特化，这将在编译时终止递归。沿着这些线的东西:

template <typename T, int rc>
struct DeterminantHelper {
  static T calculate(const Matrix<T, rc, rc>& src) {
    T det;
    for (int n = 1; n <= rc; n ++)
    {
        det = src.get(1, n) * cofactor(src, 1, n);
    }

    return det;
  }
};

template <typename T>
struct DeterminantHelper<T, 2> {
  static T calculate(const Matrix<T, 2, 2>& src) {
    return (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1));
  }
};

template<typename T, int rc>
T determinant(const Matrix<T, rc, rc>& src) {
  return DeterminantHelper<T, rc>::calculate(src);
}