How to write CPP template functions that is recursive on argument array length

Question

Say I want to write a function arrfill<N> that fills an array of length N. Below is the template implementation I tried.

template<typename T>
bool arrfill(T arr[0], T v){;}

template<size_t N, typename T>
void arrfill(T arr[N], T v){
    arr[0] = v;
    arrfill<N-1>(arr+1, v);
}

int main(int argc, char const *argv[])
{
    bool barr[4];
    arrfill<4>(barr, true);
}

However, this won't compile as the template instantiation will not terminate at the case when N is 0 and will exceed its maximum depth.

It seems like the compilers won't take the array size in the signature as the argument type. I wonder what's the proper way for specifying that?

FYI, `std::array` has a `fill` function. `std::fill` works on arrays as well as any other iterator-compatible (or range-compatible for `std::ranges::fill` in C++20) type. — chris, Apr 21 '21 at 02:58

Yakk - Adam Nevraumont · Accepted Answer · 2021-04-21T16:11:45.123

You are bitten by argument decay.

Argument decay means that int arr[N] is fancy talk for int* arr. The N is utterly ignored.

On top of that, arrfill<N-1> is a call to a template function whose first argument is a size_t (or compatible). Your T arr[0] is an overload that takes as its first template argument a type. So it cannot be selected.

To work around argument decay, you should take arrays by reference.

template<typename T>
bool arrfill(T (&arr)[1], T v){arr[0]=v;}

template<size_t N, typename T>
void arrfill(T (&arr)[N], T v){
  arr[0] = v;
  arrfill(*reinterpret_cast<T(*)[N-1]>(arr+1), v);
}

Sadly, this is undefined behavior; I am casting parts of an array into arrays of type it isn't. This happens to be undefined behavior which every single C++ compiler I have ever used consumes and does "the right thing", but it is still undefined behavior. And we should avoid that unless we have a strong reason not to; while clean and clear, clean code is not (in my opinion) a good reason to do UB. UB can come back to bite us 10 years from now when compilers update, and I don't want to maintain this code every compiler update and ensure it still works.

So really, use packs and folding.

template<size_t N, typename T,std::size_t...Is>
void arrfill(T (&arr)[N], T v,std::index_sequence<Is...>){
  ((void)(arr[Is]=v),...);
}
template<size_t N, typename T>
void arrfill(T (&arr)[N], T v){
  arrfill(arr, v, std::make_index_sequence<N>{});
}

or just use std::fill_n.

template<size_t N, typename T>
void arrfill(T (&arr)[N], T v){
  std::fill_n( std::begin(arr), N, v );
}

if you really, really must use recursion

template<size_t N, typename T>
void arrfill(T* arr, T v){
  if constexpr(N==0) {
    return;
  } else {
    arr[0] = v;
    arrfill<N-1>(arr+1, v);
  }
}

does it. In c++11 we can't use if constexpr. So we do something else.

template<typename T>
void arrfill(std::integral_constant<std::size_t, 0>, T* arr, T const& v){
}

template<size_t N, typename T>
void arrfill(std::integral_constant<std::size_t, N>, T* arr, T const& v){
  arr[0] = v;
  arrfill(std::integral_constant<std::size_t, N-1>{}, arr+1, v);
}

template<size_t N, typename T>
void arrfill(T(&arr)[N], T const& v){
  arrFill(std::integral_constant<std::size_t, N>{}, arr, v);
}

this lets us select the 0 case using overloading. We also deduce N automatically.

score 1 · Answer 2 · answered Apr 21 '21 at 02:55

I came out with a solution by defining a new class encoding the length information. But I wonder whether it's the most elegant way.

template<size_t N>
struct intClass{};

template<typename T>
bool arrfill(T arr[0], T v, intClass<0>){;}

template<size_t N, typename T>
void arrfill(T arr[N], T v, intClass<N>){
    arr[0] = v;
    arrfill(arr+1, v, intClass<N-1>());
}

template<size_t N, typename T>
void arrfill(T arr[N], T v){
    arrfill(arr,v, intClass<N>());
}

How to write CPP template functions that is recursive on argument array length

2 Answers2