Failure to create C++ arrays recursively
Try this:
#include <iostream>
#include <array>
using namespace std;
// the function contains its body just because looks like
// you want to implement some other logic there
template <typename T>
void fn(array<T, 2ul>& data) {
const size_t Size = 2;
const size_t begin{0};
const size_t end{Size-1};
const size_t leftUpper{(begin+end)/2};
const size_t rightLower{leftUpper+1};
array<T, end+1-rightLower> right;
cout << "Right: " << end+1-rightLower << endl;
}
template <typename T>
void fn(array<T, 1ul>& data) {
}
template <typename T>
void fn(array<T, 1ul>& data) {
const size_t Size = 1;
const size_t begin{0};
const size_t end{Size-1};
const size_t leftUpper{(begin+end)/2};
const size_t rightLower{leftUpper+1};
array<T, end+1-rightLower> right;
cout << "Right: " << end+1-rightLower << endl;
}
template <typename T, size_t Size>
void fn(array<T, Size>& data) {
const size_t begin{0};
const size_t end{Size-1};
const size_t leftUpper{(begin+end)/2};
const size_t rightLower{leftUpper+1};
if (data.size() > 1 ) {
array<T, end+1-rightLower> right;
cout << "Right: " << end+1-rightLower << endl;
fn(right);
}
}
int main() {
array<int, 5> test;
fn(test);
}
You code is not compiled conditionally. if
s do not work like you expect when you do template magic. One more example is here
First of all, let us understand where the problem comes from.
The error you get
/usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/array: In instantiation of ‘struct std::array<int, 2305843009213693952>’:
GuessNumber.cpp:15:9: recursively required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 2]’
GuessNumber.cpp:15:9: required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 5]’
tells you that you first instantiate fn
with Size=5
(because you call it in the main
), and this recursively instantiates fn
with Size=2
. Unfortunately the compiler does not show the full recursion, otherwise you would see that the recursion does not end here.
If you use in the program an array of size 2
array<int, 2> test;
you will see an additional level of recursion, in the error message:
GuessNumber.cpp:15:9: recursively required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 1]’
GuessNumber.cpp:15:9: required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 2]’
GuessNumber.cpp:21:11: required from here
which again, tells you that the instantiation of fn
with Size=2
triggers the intantation of fn
with Size=1
. But the recursion does not end here. Try with
array<int, 1> test;
and you will finally see what is happpening:
/usr/include/c++/10.1.0/array: In instantiation of ‘struct std::__array_traits<int, 9223372036854775808>’:
/usr/include/c++/10.1.0/array:110:56: required from ‘struct std::array<int, 9223372036854775808>’
GuessNumber.cpp:13:33: required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 0]’
GuessNumber.cpp:15:9: required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 1]’
GuessNumber.cpp:21:11: required from here
When Size=1
, the compiler fully generates fn
, including the code in the braces if (data.size() > 1)
. Even if this condition is always false, still the code is parsed and compiled. This means that, inside the never-executed-code, you instantiate fn
with Size=0
. But then, you have an overflow in the variable end
, which attains a large value. Then the code after if
instantiates an std::array
with the exceedingly large size.
To fix this, you need to stop the compiler from generating code when Size=0
.
This can be done in several ways.
With c++17 you have a very convenient if constexpr
. If the condition of if constexpr
is not true, the code is not instatiated at all, ending then the template recursion. So you can substitute
if (data.size() > 1 ) {
with
if constexpr (Size > 1 ) {
And compile with std=c++17
. Notice that I changed the condition to Size > 1
because the data
variable is not constexpr
, hence you cannot use it at compile time.
If you do not have c++17, you can use SFINAE instead.
#include <iostream>
#include <array>
#include <type_traits>
using namespace std;
template <typename T, size_t Size>
typename std::enable_if<(Size == 0)>::type fn(array<T, Size>& data) { }
template <typename T, size_t Size>
typename std::enable_if<(Size > 0)>::type fn(array<T, Size>& data) {
const size_t begin{0};
const size_t end{Size-1}; // 1
const size_t leftUpper{(begin+end)/2}; // 0
const size_t rightLower{leftUpper+1}; // 1
if (data.size() > 1 ) {
array<T, end+1-rightLower> right; // 1
cout << "Right: " << end+1-rightLower << endl;
fn(right);
}
}
int main() {
array<int, 5> test;
fn(test);
}
The two approaches are perfectly equivalent, see here.