функция рекурсивного шаблона приводит к отрицательному размеру массива при инициализации

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)
{
...
}

У меня есть несколько функций, которые работают таким образом.

Теперь сообщение об ошибке, которое я получаю, чрезвычайно сложно, так как использование шаблонов превратило то, что в противном случае было бы в трассировку стека во время компиляции. Вот что я думаю происходит:

Мой матричный класс хранит свои данные тремя способами: 2d-массив указателей, 1d-массив строк и 1d-массив столбцов (строки и столбцы являются внутренними классами, объявленными в матрице, функцией и функцией как обертки для 1d-массивов указателей). , Все эти указатели указывают на данные 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

Если кто-то может предложить какую-либо помощь в этом вопросе, я был бы очень признателен.

0

arrays c++negative-number recursion templates

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Особый случай для 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);
}

2