I'm using C++ with g++ (version 13.2.1), and I am making a function Determinant<m> that accepts std::array<std::array<int,m>,m> as an argument type and returns the determinant of that matrix.
The following is the code I have written.
Determinant:
template <int m>
int Determinant(std::array<std::array<int,m>,m> arr){
if(m == 2){
return arr[0][0]*arr[1][1] - arr[0][1]*arr[1][0];
}else if(m >2){
int ans = 0;
for(int i =0;i < m;i++){
ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
}
return ans;
}else{
return -1;
}
}
slc : returns a slice(not really a slice, just removes a row and column)
template <int m, int n>
std::array<std::array<int,(n-1)>,(m-1)> slc(std::array<std::array<int,n>,m> arr, int i,int j){
std::array<std::array<int,(n-1)>,(m-1)> ans;
for(int x = 0;x < m;x ++){
for (int y = 0;y < n;y++){
if(y == i || x == j){
continue;
}
ans[x- ( x>j ? 1:0) ][y- ( y>i ? 1:0) ] = arr[x][y];
}
}
return ans;
}
The error I am getting is attached here:
matrices.cpp: In instantiation of ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 0]’:
matrices.cpp:85:42: recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42: required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30: required from here
matrices.cpp:85:51: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
85 | ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
| ~~~~~~~~^~~~~~~~~~~
matrices.cpp:85:51: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
In file included from matrices.cpp:2:
/usr/include/c++/13/array: In instantiation of ‘struct std::__array_traits<std::array<int, 18446744073709551615>, 18446744073709551615>’:
matrices.cpp:85:42: recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42: required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30: required from here
/usr/include/c++/13/array:55:13: error: size ‘18446744073709551615’ of array exceeds maximum object size ‘9223372036854775807’
55 | using _Type = _Tp[_Nm];
| ^~~~~
/usr/include/c++/13/array: In instantiation of ‘struct std::__array_traits<int, 18446744073709551615>’:
/usr/include/c++/13/array:109:55: recursively required from ‘struct std::array<int, 18446744073709551615>’
matrices.cpp:85:42: recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42: required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30: required from here
/usr/include/c++/13/array:55:13: error: size ‘18446744073709551615’ of array exceeds maximum object size ‘9223372036854775807’
matrices.cpp: In instantiation of ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 0]’:
matrices.cpp:85:42: recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42: required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30: required from here
matrices.cpp:85:51: error: could not convert ‘slc<0, 0>(arr, i, 0)’ from ‘array<array<[...],4294967295>,4294967295>’ to ‘array<array<[...],18446744073709551615>,18446744073709551615>’
85 | ans += arr[0][i]*Determinant<m-1>(slc<m,m>( arr,i,0 ))*(i%2 ? 1:-1);
| ~~~~~~~~^~~~~~~~~~~
| |
| array<array<[...],4294967295>,4294967295>
matrices.cpp: In instantiation of ‘std::array<std::array<int, (n - 1)>, (m - 1)> slc(std::array<std::array<int, n>, m>, int, int) [with unsigned int m = 0; unsigned int n = 0]’:
matrices.cpp:85:42: recursively required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 2]’
matrices.cpp:85:42: required from ‘int Determinant(std::array<std::array<int, m>, m>) [with int m = 3]’
matrices.cpp:98:30: required from here
matrices.cpp:6:43: warning: size of ‘ans’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
6 | std::array<std::array<int,(n-1)>,(m-1)> ans;
| ^~~
matrices.cpp:15:10: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
15 | return ans;
| ^~~
matrices.cpp:15:10: warning: size of ‘<anonymous>’ 18446744039349813252 bytes exceeds maximum object size 9223372036854775807 [-Wlarger-than=]
Any insight would be greatly appreciated.
First of all, deduction shouldn't be possible if there is a type mismatch. int m is not the same type as m in std::array<int, m>, so you should be using:
template <std::size_t m>
Secondly, there is infinite recursion in template instantiations because you're not using if constexpr, just a regular if statement.
In if (m == 2){, the code block is not discarded if the condition is false, it just becomes dead code.
The same applies to the else branch.
Therefore, Determinant<2> instantiates Determinant<1>, then Determinant<0>, and then Determinant<-1> which is where you get a compiler error.
To fix this, use if constexpr:
template <std::size_t m>
int Determinant(std::array<std::array<int, m>, m> arr) {
if constexpr (m == 0) {
return -1;
} else if constexpr (m == 1) {
return arr[0][0];
} else if constexpr (m == 2) {
return arr[0][0] * arr[1][1] - arr[0][1] * arr[1][0];
} else {
int ans = 0;
for (std::size_t i = 0; i < m; i++) {
ans += arr[0][i] * Determinant<m-1>(slc<m, m>(arr, i, 0)) * (i % 2 ? 1 : -1);
}
return ans;
}
}